摘要

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

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

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

LeetCode232 用隊列實現(xiàn)棧

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

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

完整題解代碼如下

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 會返回值，而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 用隊列實現(xiàn)棧

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

完整的題解代碼如下

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();
 */