[LeetCode] Implement Stack using Queues

待我称王封你为后i 2021-12-03 07:15 94阅读 0赞

[**Implement Stack using Queues**][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 may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
 *  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 -- which means only `push to back`, `pop from front`, `size`, and `is empty` operations are valid.

Credits:  
Special thanks to [@jianchao.li.fighter][jianchao.li.fighter] for adding this problem and all test cases.

水题。用两个队列来模拟。

1 class Stack {
     2 private:
     3     queue<int> que[2];
     4     int cur = 0;
     5     
     6 public:
     7     // Push element x onto stack.
     8     void push(int x) {
     9         que[cur].push(x);
    10     }
    11 
    12     // Removes the element on top of the stack.
    13     void pop(void) {
    14         while (que[cur].size() > 1) {
    15             que[1 - cur].push(que[cur].front());
    16             que[cur].pop();
    17         }
    18         que[cur].pop();
    19         cur = 1 - cur;
    20     }
    21 
    22     // Get the top element.
    23     int top(void) {
    24         while (que[cur].size() > 1) {
    25             que[1 - cur].push(que[cur].front());
    26             que[cur].pop();
    27         }
    28         int top = que[cur].front();
    29         que[1 - cur].push(que[cur].front());
    30         que[cur].pop();
    31         cur = 1 - cur;
    32         return top;
    33     }
    34 
    35     // Return whether the stack is empty.
    36     bool empty(void) {
    37         return que[cur].empty();
    38     }
    39 };

转载于:https://www.cnblogs.com/easonliu/p/4568492.html

[Implement Stack using Queues]: https://leetcode.com/problems/implement-stack-using-queues/
[jianchao.li.fighter]: https://leetcode.com/discuss/user/jianchao.li.fighter