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  for adding this problem and all test cases.

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

1 class Stack { 2 private: 3     queue
     
       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 };