博文中会简要介绍Leetcode P0232题目分析及解题思路。

“Implement Queue using Stacks”是一道比较基础的设计题，题目要求最多使用两个栈结构来实现一个队列。

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

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, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

我们知道栈结构的特点是FILO而队列的特点是FIFO。直觉上来说我们得到一个存储了n个元素的栈后，可以通过将这个栈的前n-1个元素拿出放入另一个栈，然后再取出第n个元素作为队列头的元素，即可实现队列的特性。

除此之外，在放入另一个栈以后不难发现，新的栈中元素的出栈顺序就是队列的元素弹出顺序，所以在弹出第二个元素的时候不需要再取出前n个元素。也就是说我们维护的两个栈s1和s2，s1专门用于存储新元素，s2专门用于按队列特性弹出元素。一旦s2为空，就将s1中的元素弹入s2，否则就直接从s2弹出元素。

基本思路如上，更进一步地考虑优化top(·)函数。对于这个函数，我们不难发现，其实该函数并不需要修改栈内的元素，也就是说我们可以通过记录这个top值来达成函数的目的。我们在每次push执行的时候，如果当前成员变量top为空，则将元素赋值给类内的成员变量_top。显然若当前成员变量top为空，那么我们push的元素一定是队列的头元素，这样一来在执行top(·)函数时我们无需对栈进行操作来寻找队列头元素，从而节省了大量时间。

以下是Java的题解代码实现。

class MyQueue {
    
    private Integer top = null;
    // s1 holds the FILO sequence, however, s2 holds the FIFO sequence
    private Deque<Integer> s1, s2;
    /** Initialize your data structure here. */
    public MyQueue() {
        this.s1 = new LinkedList<>();
        this.s2 = new LinkedList<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        if (top == null)
            top = x;
        
        s1.offerFirst(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        Integer ret = null;
        if (!s2.isEmpty())
            ret = s2.pollFirst();
        
        if (s2.isEmpty()) {
            while (!s1.isEmpty()) {
                s2.offerFirst(s1.pollFirst());
            }
            
            if (ret == null)
                ret = s2.pollFirst();
        }
    
        top = s2.peekFirst();
        return ret;
    }
    
    /** Get the front element. */
    public int peek() {
        if (top != null)
            return top;
        
        return -1;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return (top == null);
    }
}

/**
 * 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();
 * boolean param_4 = obj.empty();
 */

以下是C++的题解代码实现。

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        top = -1;
        has_top = false;
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        if (!has_top) {
            top = x;
            has_top = true;
        }
            
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int ret = -1;
        _Pick(ret);
        
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
            
            _Pick(ret);
        }
        
        if (!s2.empty()) {
            top = s2.top();
            has_top = true;
        }
        
        return ret;
    }
    
    /** Get the front element. */
    int peek() {
        return top;
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return !has_top;
    }
    
private:
    int top;
    bool has_top;
    stack<int> s1, s2;
    
    void _Pick(int &val) {
        if (has_top && !s2.empty()) {
            val = s2.top();
            s2.pop();
            // The top element has been removed
            has_top = false;
        }
    }
};

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