用队列实现栈

一、题目

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-stack-using-queues
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路

我们用两个队列A、B来模拟栈。

1. 入栈：直接将元素添加进队列末尾
2. 出栈：将A队列中队尾元素以外的都挪到B队列中，使得栈顶元素能够被取出。在此之前，要将AB的引用交换，使得A始终保存在A中。
   
3. 返回栈顶元素：和出栈同理，只是返回的元素也得进入B队列。
4. 判断栈是否为空：如果AB同时为空，则为空栈。

三、代码

class MyStack {
        
    private Queue<Integer> A = new LinkedList<>();
    private Queue<Integer> B = new LinkedList<>();
    
    /** Initialize your data structure here. */
    public MyStack() {

    }

    /** Push element x onto stack. */
    public void push(int x) {
        // x 进A队列
        A.offer(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if (empty()){
            return -1;
        }
        // 把A中的元素挪移到B队列中
        while(A.size() > 1){
            Integer font = A.poll();
            B.offer(font);
        }
        // 把A队列中剩下的一个元素返回
        int ret = A.poll();
        swapAB();
        return ret;
    }
    private void swapAB(){
        Queue<Integer> tmp = A;
        A = B;
        B = tmp;
    }
    /** Get the top element. */
    public int top() {
        if (empty()){
            return -1;
        }
        // 把A中的元素挪移到B队列中
        while(A.size() > 1){
            Integer font = A.poll();
            B.offer(font);
        }
        // 把A队列中剩下的一个元素返回
        int ret = A.poll();
        B.offer(ret);
        swapAB();
        return ret;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

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