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.

    Example:

    1. MyStack stack = new MyStack();
    3. stack.push(1);
    4. stack.push(2);  
    5. stack.top();   // returns 2
    6. stack.pop();   // returns 2
    7. stack.empty(); // returns false

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

    题意

    使用队列Queue来实现栈Stack。要求只能使用队列的add/offer、remove/poll、peek、size、isEmpty方法。

    思路

    可使用双队列或单队列，直接上代码。

    代码实现 - 双队列

    1. class MyStack {
    3.     private Queue<Integer> q1, q2;
    4.     private int top;
    6.     /** Initialize your data structure here. */
    7.     public MyStack() {
    8.         q1 = new LinkedList<>();
    9.         q2 = new LinkedList<>();
    10.     }
    12.     /** Push element x onto stack. */
    13.     public void push(int x) {
    14.         q1.offer(x);
    15.         top = x;
    16.     }
    18.     /** Removes the element on top of the stack and returns that element. */
    19.     public int pop() {
    20.         while (q1.size() > 1) {
    21.             top = q1.poll();
    22.             q2.offer(top);
    23.         }
    24.         int res = q1.poll();
    25.         Queue<Integer> temp = q1;
    26.         q1 = q2;
    27.         q2 = temp;
    29.         return res;
    30.     }
    32.     /** Get the top element. */
    33.     public int top() {
    34.         return top;
    35.     }
    37.     /** Returns whether the stack is empty. */
    38.     public boolean empty() {
    39.         return q1.isEmpty();
    40.     }
    41. }

    代码实现 - 单队列

    1. class MyStack {
    3.     private Queue<Integer> q;
    5.     /** Initialize your data structure here. */
    6.     public MyStack() {
    7.         q = new LinkedList<>();
    8.     }
    10.     /** Push element x onto stack. */
    11.     public void push(int x) {
    12.         int size = q.size();
    13.         q.offer(x);
    14.         while (size != 0) {
    15.             q.offer(q.poll());
    16.             size--;
    17.         }
    18.     }
    20.     /** Removes the element on top of the stack and returns that element. */
    21.     public int pop() {
    22.         return q.poll();
    23.     }
    25.     /** Get the top element. */
    26.     public int top() {
    27.         return q.peek();
    28.     }
    30.     /** Returns whether the stack is empty. */
    31.     public boolean empty() {
    32.         return q.isEmpty();
    33.     }
    34. }