232.md

【中规中矩】232. 用栈实现队列

解题思路

解法1：比较naive的实现就是每次push元素之前都要把输出栈stk2的元素重新搬回输入栈stk1，然后再栈后push。pop的时候，把所有元素都搬入到输出栈，从栈尾pop（peek跟pop类似，只是不会把尾部元素pop掉而已）。时间复杂度为O(N)

解法2：观察到解法1中有大量不必要的搬来搬去，每个元素只需要入栈stk1, stk2各一次就够了。当需要pop的时候，如果stk2里面有元素，说明之前从stk1种搬来的元素还没pop完，直接O(1) pop，如果为空了，需要一次O(N)操作把所有输入栈里的元素用movInToOut从输入栈搬到输出栈。虽然是O(N)但是考虑到搬一次可以够后面N次pop O(1)时间用，所以平均pop时间还是O(1)。push就更简单直接O(1)时间push到输入栈即可。peek跟pop类似，只是不会把尾部元素pop掉而已。此种实现可以所有栈操作O(1)平均时间。

代码

// O(N) time
class MyQueue1 {
public:
    /** Initialize your data structure here. */
    MyQueue1() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        while (!stk2.empty()) {
            stk1.push(stk2.top());
            stk2.pop();
        }

        stk1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }


        int res = stk2.top();
        stk2.pop();
        return res;
    }
    
    /** Get the front element. */
    int peek() {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }

        return stk2.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stk1.empty() && stk2.empty();
    }

private:
    stack<int> stk1;
    stack<int> stk2;
};


// O(1) amortized time
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stk1.push(x);
    }
    

    void moveInToOut() {
        if (!stk2.empty()) {
            return;
        }

        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        moveInToOut();
        int res = stk2.top();
        stk2.pop();
        return res;
    }
    
    /** Get the front element. */
    int peek() {
        moveInToOut();
        return stk2.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stk1.empty() && stk2.empty();
    }

private:
    stack<int> stk1;
    stack<int> stk2;
};