LeetCode 225. Implement Stack using Queues

Implement the following operations of a stack using queues.

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).

题意：使用队列实现栈的如下操作：
push(x):元素x进栈
pop():移除栈顶元素
top()：取栈顶元素
empty():判断栈是否为空
Note：
要求只使用队列的基本操作--进队（offer），取队首元素（peek），移除队首元素（remove），队列大小（size），队列是否为空（isEmpty）
可以使用链表或双端队列模拟队列

思路：使用两个队列。用队列q1模拟栈。
当取栈顶元素时，将队列q1中除了队尾元素（即栈顶元素）外，全部加入队列q2中，然后移除队尾元素。再将q2赋值给q1

class MyStack {
    Queue<Integer> q1 = new LinkedList<Integer>(); 
    Queue<Integer> q2 = new LinkedList<Integer>();
    private int top;//使用top记录栈顶元素（即队尾元素）

    /** Initialize your data structure here. */
    public MyStack() {
        
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        q1.offer(x);
        top = x;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        while(q1.size() > 1){
            top = q1.remove();
            q2.offer(top);
        }
        int x = q1.remove();
        Queue<Integer> temp = new LinkedList<Integer>();
        q1 = q2;
        q2 = temp;
        return x;
    }
    
    /** Get the top element. */
    public int top() {
        return top;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q1.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();
 */

LeetCode 225. Implement Stack using Queues

推荐阅读