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

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

Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack. boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue), as long as you use only a queue’s standard operations.

Follow-up: Can you implement the stack 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.

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

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

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

class MyStack {
    Integer _top = null;
    
    Queue<Integer> q1, q2;
    /** Initialize your data structure here. */
    public MyStack() {
        this.q1 = new LinkedList<>();
        this.q2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        _top = x;
        if (!q2.isEmpty())
            q2.offer(x);
        else
            q1.offer(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        Queue<Integer> src = !q1.isEmpty()? q1: q2;
        Queue<Integer> dst = q1.isEmpty()? q1: q2;
        int size = src.size();
        
        while (size > 2) {
            dst.offer(src.poll());
            --size;
        }
        
        _top = (size == 1)? null: src.poll();
        if (_top != null)
            dst.offer(_top);
        
        return src.poll();
    }
    
    /** Get the top element. */
    public int top() {
        if (_top != null)
            return _top;
        
        return -1;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return (_top == null);
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

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

class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        top_ = x;
        has_top = true;
        if (!q2.empty())
            q2.push(x);
        else
            q1.push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        queue<int> *src = q1.empty()? &q2: &q1;
        queue<int> *dst = q1.empty()? &q1: &q2;
        
        int size = src->size();
        while (size > 2) {
            dst->push(src->front());
            src->pop();
            --size;
        }
        
        if (size == 1)
            has_top = false;
        else {
            top_ = src->front();
            dst->push(src->front());
            src->pop();
        }
        
        int ret = src->front();
        src->pop();
        return ret;
    }
    
    /** Get the top element. */
    int top() {
        if (has_top)
            return top_;
        
        return -1;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return !has_top;
    }
    
private:
    int top_ = 0;
    bool has_top = false;
    queue<int> q1, q2;
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */