Programming Skills: Implement queue using stack

[題目]
https://leetcode.com/problems/implement-queue-using-stacks/description/

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.

就是叫你做一個queue出來，但implement的方面，要求你用stack來implement。換言之你push element必需要先push到一個stack中。但是pop東西卻要pop stack bottom的東西。請注意這個stack要遵守所有stack的操作規則，換言之你可不能想說既然程式是自己寫的，就偷看一下stack bottom。

[思路]
之前說過queue像隧道有雙開口，stack像瓶子只有單開口。這也就是說同樣是first in的東西，在stack中會被壓在其他東西下面導致只能last out。

好吧真是討厭，不過沒有做不出來的題目（只有好不好的方法而已ＸＤ）。直觀地想這題
push()：我們老實的push進stack。
pop() or peek()：我們把東西從瓶子(就是stack)裡倒出來，就可以拿到瓶底的東西了對吧！然後再把剩下的東西都放回去瓶子裡就完成啦。至於你把東西倒出來的時候，總要找個地方先擺著，所以我們再用一個stack2暫放即可。

小結：
push: push into stack1
pop: pop every thing from stack1, and push to stack2. The last element is your target.
peek : The first element you push into stack1 is the 'front of queue', use a variable to store it so you can peek it in O(1). Update it during the pop() procedure.

這個做法的代價是：
push() : O(1)
peek() : O(1)
pop() : O(N)

[好一點的思路]
上述提到pop()時你必須把stack1都倒出來才能取出bottom element，這是無可避免的事情，因為題目要求你push()時必須要塞進stack。但是停一秒，想想用來暫存的stack2長甚麼樣子

stack1: 1,2,3,4,5 <--this is top
stack2:
執行pop()時, 我們將stack1的東西倒到stack2
stack1:
stack2: 5,4,3,2,1

你發現了嗎，stack2中element的順序就是我們想要的。

因此改良的方法是
push: push into stack1
pop: If stack2 is empty, pop every thing from stack1 and push to stack2. The top element of stack2 is your target, pop it. If stack2 is not empty, just pop() stack2.
peek : return 'Top' of stack2.

這個做法的代價是：
push() : O(1)
peek() : O(1)
pop() : O(1)。因為每個element只被移動一次(from stack1 to stack2)，所以pop N個元素後，平均每次pop()的代價是O(1)。


class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> s1;
    stack<int> s2;
    
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.top());
                s1.pop();
            }
        }
        int front=s2.top();
        s2.pop();
        return front;
    }
    
    /** Get the front element. */
    int peek() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();        
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty() && s2.empty();
    }
};