LeetCode 225 Implement Stack using Queues 用队列实现栈

1、两个队列实现，始终保持一个队列为空即可

 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         if(que1.empty())
11         {
12             que1.push(x);
13             while(!que2.empty())
14             {
15                 int val=que2.front();
16                 que2.pop();
17                 que1.push(val);
18             }
19         }
20         else
21         {
22             que2.push(x);
23             while(!que1.empty())
24             {
25                 int val=que1.front();
26                 que1.pop();
27                 que2.push(val);
28             }
29         }
30     }
31     
32     /** Removes the element on top of the stack and returns that element. */
33     int pop() {
34         if(que1.empty())
35         {
36             int val=que2.front();
37             que2.pop();
38             return val;
39         }
40         if(que2.empty())
41         {
42             int val=que1.front();
43             que1.pop();
44             return val;
45         }        
46     }
47     
48     /** Get the top element. */
49     int top() {
50         if(que1.empty())
51             return que2.front();
52         if(que2.empty())
53             return que1.front();
54     }
55     
56     /** Returns whether the stack is empty. */
57     bool empty() {
58         return que1.empty()&&que2.empty();
59     }
60 private:
61     queue<int> que1;
62     queue<int> que2;
63 };
64 
65 /**
66  * Your MyStack object will be instantiated and called as such:
67  * MyStack obj = new MyStack();
68  * obj.push(x);
69  * int param_2 = obj.pop();
70  * int param_3 = obj.top();
71  * bool param_4 = obj.empty();
72  */

2、一个队列实现栈

 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         que.push(x);
11         for(int i=0;i<que.size()-1;++i)
12         {
13             que.push(que.front());
14             que.pop();
15         }
16     }
17     
18     /** Removes the element on top of the stack and returns that element. */
19     int pop() {
20         int val=que.front();
21         que.pop();
22         return val;
23     }
24     
25     /** Get the top element. */
26     int top() {
27         return que.front();
28     }
29     
30     /** Returns whether the stack is empty. */
31     bool empty() {
32         return que.empty();
33     }
34 private:
35     queue<int> que;
36 };
37 
38 /**
39  * Your MyStack object will be instantiated and called as such:
40  * MyStack obj = new MyStack();
41  * obj.push(x);
42  * int param_2 = obj.pop();
43  * int param_3 = obj.top();
44  * bool param_4 = obj.empty();
45  */