类似问题：232. Implement Queue using Stacks

问题：

设计数据结构，使用queue实现stack。

实现以下功能：

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
 

Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.

　　

解法：单队列->实现队列

参考labuladong解析

 

 

重点在：

查栈顶元素top 和 出栈pop

使用额外变量，记录top元素：top_ele

循环queue内所有元素，剩下最后一个即为要求栈顶元素top

同时更新 top_ele 为倒数第二个元素。

 

参考代码：

 1 class MyStack {
 2 public:
 3     /** Initialize your data structure here. */
 4     MyStack() {
 5         
 6     }
 7     
 8     /** Push element x onto stack. */
 9     void push(int x) {
10         q.push(x);
11         top_ele = x;
12     }
13     
14     /** Removes the element on top of the stack and returns that element. */
15     int pop() {
16         int size = q.size();
17         while(size>2) {
18             q.push(q.front());
19             q.pop();
20             size--;
21         }
22         top_ele = q.front();
23         q.pop();
24         q.push(top_ele);
25         int res = q.front();
26         q.pop();
27         return res;
28     }
29     
30     /** Get the top element. */
31     int top() {
32         return top_ele;
33     }
34     
35     /** Returns whether the stack is empty. */
36     bool empty() {
37         return q.empty();
38     }
39 private:
40     queue<int> q;
41     int top_ele;
42 };
43 
44 /**
45  * Your MyStack object will be instantiated and called as such:
46  * MyStack* obj = new MyStack();
47  * obj->push(x);
48  * int param_2 = obj->pop();
49  * int param_3 = obj->top();
50  * bool param_4 = obj->empty();
51  */