LeetCode225 Implement Stack using Queues

Implement the following operations of a stack using queues. （Easy）

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

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, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

分析：

使用两个队列实现，其中一个队列为空，用来进行颠倒顺序和输出队尾元素。

入栈操作： 向非空队列内入队即可

出栈操作：将非空队列除队尾元素外的所有元素导入另一个空队列，剩余队尾元素即为待应该待出栈元素

top()操作： 同出栈，注意只需访问返回，不需要让其出队，即仍需将其导入另一队列

注意：两队列地位平等，均可能用作储存和转移工作

代码：

class Stack {
private:
    queue<int> q1,q2;
public:
    // Push element x onto stack.
    void push(int x) {
        if(!q1.empty()){
            q1.push(x);
        }
        else{
            q2.push(x);
        }
    }

    // Removes the element on top of the stack.
    void pop() {
        if(!q1.empty()){
            while(q1.size() > 1){
                q2.push(q1.front());
                q1.pop();
            }
            q1.pop();
        }else{
            while(q2.size() > 1){
                q1.push(q2.front());
                q2.pop();
            }
            q2.pop();
        }
    }

    // Get the top element.
    int top() {
        if(!q1.empty()){
            while(q1.size() > 1){
                q2.push(q1.front());
                q1.pop();
            }
            int ans = q1.front();
            q2.push(q1.front());
            q1.pop();
            return ans;
        }else{
            while(q2.size() > 1){
                q1.push(q2.front());
                q2.pop();
            }
            int ans = q2.front();
            q1.push(q2.front());
            q2.pop();
            return ans;
        }
    }

    // Return whether the stack is empty.
    bool empty() {
        if(q1.empty() && q2.empty()){
            return true;
        }
        return false;
    }
};