232. Implement Queue using Stacks.md

232. Implement Queue using Stacks

思路

用两个栈实现队列。
设置两个栈stk1和stk2，基本思路是stk1用作input（入队）, stk2用作output（出队）。

入队：无脑入栈stk1即可； 出队：若stk2为空，那么先将stk1所有元素依次pop然后push进stk2，此时stk2栈顶元素就是最开始入队的元素，所以pop即可。

C++

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