Use queues to implement the following operations on the stack:

  • Push (x) — element X is pushed
  • Pop () — Removes the top element of the stack
  • Top () — Gets the top element on the stack
  • Empty () — Returns whether the stack is empty

Note:

  • You can only use the basic operations of the queue — i.epush to back.peek/pop from front.size, andis emptyThese operations are legal.
  • Your language may not support queues. You can use a list or a deque to simulate a queue, as long as it’s standard queue operations.
  • You can assume that all operations are valid (for example, no pop or top operations are called on an empty stack).

Answer key

class MyStack {

    private Queue<Integer> queue;
    private Queue<Integer> reverseQueue;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue = new LinkedList<>();
        reverseQueue = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        reverseQueue.offer(x);
        while (!queue.isEmpty()) {
            reverseQueue.offer(queue.poll());
        }
        Queue temp = queue;
        queue = reverseQueue;
        reverseQueue = temp;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        return queue.poll();
    }

    /**
     * Get the top element.
     */
    public int top() {
        return queue.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue.isEmpty();
    }
}
Copy the code

With two unidirectional queues, each push adds the value to reverseQueue, pushes all the elements in the queue into reverseQueue, and then swaps the reverseQueue and queue.

1. Reverse Sequeue :[1] Queue:[] reverseQueue:[] Queue:[1] 2. Reverse Sequeue :[2] Queue:[1] 2.2 ReverseQueue :[2,1] queue:[] 2.3 reverseQueue:[] queue:[2,1] 3. push(3) 2.1 reverseQueue[3] queue:[2,1] 2.2 ReverseQueue :[3,2,1] queue:[] 2.3 reverseQueue:[] queue:[3,2,1] 4. top() 3 5. pop() 3Copy the code