LeetCode 232 Implement Queue using Stacks（用棧來實現隊列）（*）

LeetCode 232 Implement Queue using Stacks（用棧來實現隊列）（*）

翻譯

用棧來實現隊列的下列操作。

push(x) —— 將元素x寫入到隊列的尾部
pop() —— 從隊列首部移除元素
peek() —— 返回隊列首部元素
empty() —— 返回隊列是否為空

注意：

你必須使用一個只有標准操作的棧。

也就是說，只有push/pop/size/empty等操作是有效的。

棧可能不被原生支持，這取決於你所用的語言。

只要你只是用stack的標准操作，你可以用list或者deque（double-ended queue）來模擬棧。

你可以假設所有的操作都是有效的（例如，pop或peek操作不會被用在空隊列上）。

原文

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.

Notes:

You must use only standard operations of a stack 

-- which means only push to top, peek/pop from top, size, and is empty operations are valid.

Depending on your language, stack may not be supported natively. 

You may simulate a stack by using a list or deque (double-ended queue), 

as long as you use only standard operations of a stack.

You may assume that all operations are valid (for example, 

no pop or peek operations will be called on an empty queue).

分析

大家可以看到，我們一共需要寫4個函數，其實有兩個可以直接寫出來。

大家看著下文的代碼，首先定義兩個stack，可以回顧一下題目的第一句話：

Implement the following operations of a queue using stacks.

其實中文博大精深，英文同樣也是的，這裡很好的透露了是用多個stack來描寫一個queue。一個主攻、一個輔助，多好……

push的話，不論是棧還是隊列，都是從後面推上去，就一行；empty也是一樣的。

下面來看看如何取出第一個元素，對於隊列，我們peek的應該是最先進去的，但對於隊列，我們最先取出的確是最後進去的。

喔，我忘了，可能有童鞋不太了解棧和隊列的各種操作以及區別，可以看看我的這篇文章，非常詳細的解釋了它們。

【算法】7 分不清棧和隊列？一張圖給你完整體會

所以再看下面的代碼，如果棧中只有一個元素，那麼毫無疑問，就是它了。

如果有多個元素，首先將它們全部轉移到另一個棧中，這時候它的順序會反過來，然後留下一個元素。

這個部分就是pop和peek的關鍵了，peek的話只是取出這個數據出來，這個元素還是應該要保存起來的，所以我們也把它給了s2；而pop中則是直接給彈出了，這個數據也就不會進入s2。

當上面的操作完成之後，再將s2的數據全部轉移到s中，這時候剛剛被顛倒的數據又恢復了原先的順序。

在測試代碼的過程中，還額外寫了Queue的size，其實也只是一行而已，那就是求s的size。

這道題如果已經寫完看完了，可以繼續下面這道題喔：LeetCode 225 Implement Stack using Queues（用隊列來實現棧）（*）

Ok，這篇文章因為是我晚上在床上靠著枕頭寫的，所以寫的比較亂……之前四百多篇都是正兒八經坐著寫的。

代碼

class Queue {
public:
    stack s, s2;
    // Push element x to the back of queue.
    void push(int x) {
        s.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        if (s.size() == 1)
            s.pop();
        else {
            while (s.size() > 1) {
                s2.push(s.top());
                s.pop();
            }
            s.pop();
            while (s2.size() > 0) {
                s.push(s2.top());
                s2.pop();
            }
        }
    }

    // Get the front element.
    int peek(void) {
        if (s.size() == 1) return s.top();
        while (s.size() > 1) {
            s2.push(s.top());
            s.pop();
        }
        int temp = s.top();
        s2.push(s.top());
        s.pop();
        while (s2.size() > 0) {
            s.push(s2.top());
            s2.pop();
        }
        return temp;
    }

    // Return whether the queue is empty.
    bool empty(void) {
        return s.empty();
    }
};