摘要

• 用棧實(shí)現(xiàn)隊(duì)列，用隊(duì)列實(shí)現(xiàn)棧，雖然可能沒有什么實(shí)際應(yīng)用價(jià)值，但是對(duì)于熟悉棧和隊(duì)列的結(jié)構(gòu)以及基本操作是很有意義的。
  • 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
  • 通過讓隊(duì)列循環(huán)來實(shí)現(xiàn)棧

今日學(xué)習(xí)的視頻和文章

• 代碼隨想錄 棧和隊(duì)列的基礎(chǔ)
• C++Primer 棧和隊(duì)列部分
• 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)C++語言版（第二版）棧和隊(duì)列部分

LeetCode232 用隊(duì)列實(shí)現(xiàn)棧

232. 用棧實(shí)現(xiàn)隊(duì)列 - 力扣（Leetcode）

• 今天的題目比較簡(jiǎn)單，棧是后進(jìn)先出，而隊(duì)列是先進(jìn)先出，用棧實(shí)現(xiàn)隊(duì)列的關(guān)鍵就在于如何將后進(jìn)先出轉(zhuǎn)化為先進(jìn)先出。
  • 如果我們只用一個(gè)棧，能不能做到先進(jìn)先出呢？由于題目要求只能使用棧的標(biāo)準(zhǔn)操作，而彈出先進(jìn)的元素（即棧底的元素）前必須彈出在其之后的所有元素，所以我們應(yīng)該用另一塊內(nèi)存空間來保留這部分元素。而這部分元素的彈出順序是遵循棧的后進(jìn)先出的，由對(duì)稱性的想法，這另一個(gè)用來保存元素的空間也可以是棧的結(jié)構(gòu)。
  • 例如，這里元素1，2，3入棧，【或】表示棧底
    • 棧in：【1，2，3 ；棧out：【
    • 此時(shí)，根據(jù)隊(duì)列的先進(jìn)先出，我們要彈出1，將2，3保留在另一個(gè)棧中
    • 棧in：【1；棧out：【3，2，
    • 為了代碼邏輯更加簡(jiǎn)潔，我們可以統(tǒng)一將棧1的元素都push進(jìn)棧2中，而不是判斷棧1是否還剩余1個(gè)元素
    • 棧in：【；棧out：【3，2，1
    • 此時(shí)在讓棧2的棧頂元素出棧即可
    • 棧in：【；棧out：【3，2
  • 再插入元素到用棧實(shí)現(xiàn)的隊(duì)列中的邏輯與元素出隊(duì)列的邏輯是對(duì)稱的，銜接上面的例子，我們要插入元素4，元素4是后進(jìn)的，所以對(duì)于出棧來說它應(yīng)該位于棧底：棧out【4，3，2
    • 棧in：【；棧out：【3，2
    • 此時(shí)，將棧out的元素push回棧in中
    • 棧in：【2，3；棧out：【
    • 然后再將元素4 push進(jìn)棧in中
    • 棧in：【2，3，4；棧out：【
    • 這樣就完成了元素4進(jìn)入用棧實(shí)現(xiàn)的隊(duì)列的操作

完整題解代碼如下

class MyQueue {
private:
    stack<int> in;
    stack<int> out;
public:
    MyQueue() {

    }
    
    void push(int x) {
        while (!out.empty()) {
            in.push(out.top());
            out.pop();
        }
        in.push(x);
    }
    
    int pop() {
        while (!in.empty()) {
            out.push(in.top());
            in.pop();
        }
        int temp = out.top();
        out.pop();// 要注意這里的 pop 會(huì)返回值，而C++STL的棧的pop是不返回值的
        return temp;
    }
    
    int peek() {
        while (!in.empty()) {
            out.push(in.top());
            in.pop();
        }
        return out.top();
    }
    
    bool empty() {
        return in.empty() && out.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

LeetCode225 用隊(duì)列實(shí)現(xiàn)棧

• 初見題目時(shí)的想法：既然用兩個(gè)棧能實(shí)現(xiàn)隊(duì)列，那對(duì)稱地來想，是不是能用兩個(gè)隊(duì)列來實(shí)現(xiàn)棧呢？
• 這里用【表示隊(duì)列頭，用】表示隊(duì)列尾
  • 假設(shè)元素1，2，3進(jìn)入由隊(duì)列實(shí)現(xiàn)的棧，那么根據(jù)后進(jìn)先出，此時(shí)應(yīng)該彈出的是元素3
  • 隊(duì)列1：【1，2，3】；隊(duì)列2：【】
  • 如果我們簡(jiǎn)單去類比用兩個(gè)棧實(shí)現(xiàn)隊(duì)列，想用兩個(gè)隊(duì)列實(shí)現(xiàn)棧的話
  • 隊(duì)列1：【】；隊(duì)列2：【1，2，3】
  • 上面的隊(duì)列2再pop，還是彈出元素1而不是元素3。
  • 因?yàn)殛?duì)列是先進(jìn)先出，即使我們模仿棧實(shí)現(xiàn)隊(duì)列的思路，把要彈出的元素之前的元素保留在另一個(gè)隊(duì)列中，也無法實(shí)現(xiàn)棧。因?yàn)樵跅５暮筮M(jìn)先出，我們可以通過兩個(gè)棧顛倒元素的彈出順序；但是隊(duì)列的彈出順序就是我們將元素放入隊(duì)列的順序。
• 然后，我注意到，兩個(gè)棧實(shí)現(xiàn)隊(duì)列中，有一個(gè)地方被簡(jiǎn)化了邏輯：
  • ”為了代碼邏輯更加簡(jiǎn)潔，我們可以統(tǒng)一將棧1的元素都push進(jìn)棧2中，而不是判斷棧1是否還剩余1個(gè)元素“
  • 實(shí)際上，我們只需要判斷隊(duì)列是否出隊(duì)到只剩隊(duì)尾元素（即最后一個(gè)進(jìn)入隊(duì)列的元素），然后在按順序保存隊(duì)列的其他元素時(shí)讓隊(duì)尾元素出隊(duì)即可。
  • 這樣一來，實(shí)際上我們可以只用一個(gè)隊(duì)列來實(shí)現(xiàn)棧，即讓隊(duì)首元素出隊(duì)后再入隊(duì)，直到我們遍歷到原來的隊(duì)尾元素，讓其出隊(duì)而不再入隊(duì)即可。
    • 例子：【1，2，3】-> 【2，3，1】-> 【3，1，2】-> 【1，2】
  • 那么如何push元素到由隊(duì)列實(shí)現(xiàn)的棧中呢？我們?cè)谏厦鎸?shí)現(xiàn)的出棧操作中，是固定彈出隊(duì)尾元素的，所以我們直接將元素push到隊(duì)列中就好了。

完整的題解代碼如下

class MyStack {
private:
    queue<int> q;
public:
    MyStack() {

    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int count = 0;
        while (count < q.size() - 1) {
            q.push(q.front());
            q.pop();
            count++;
        }
        int temp = q.front();
        q.pop();
        return temp;
    }
    
    int top() {
        int temp = pop();
        push(temp);
        return temp;
    }
    
    bool empty() {
        return q.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */