Leetcode225. 用队列实现栈 && LeetCode232. 用栈实现队列

用栈实现队列和用队列实现栈的思想不一样。

（1）用栈实现队列将定义两个栈，其中一个是输入栈，一个是输出栈。关键是弹出元素的实现，通过这个两个栈实现先入先出。如果输出栈为空时，要将输入栈中的所有元素压入输出栈。然后从输出栈弹出元素。判空条件是：输入输出栈都为空。

（2）用队列实现栈将定义两个队列。其中一个队列只起到备份前一个队列部分元素作用。关键依旧是弹出元素的实现，通过队列1弹出最后一个元素，队列2备份队列1的最后一个元素之前所有元素，然后当队列1弹出最后一个元素后，再将队列2的备份更新到队列1中。判空的条件是：队列1为空。

代码

 1 class MyQueue {
 2 public:
 3     /** Initialize your data structure here. */
 4     stack<int>stIn;
 5     stack<int>stOut;
 6     MyQueue() {
 7 
 8     }
 9     
10     /** Push element x to the back of queue. */
11     void push(int x) {
12         stIn.push(x);
13     }
14     
15     /** Removes the element from in front of queue and returns that element. */
16     int pop() {
17         if(stOut.empty()){
18             while(!stIn.empty()){
19                 stOut.push(stIn.top());
20                 stIn.pop();
21             }
22         }
23         int res = stOut.top();
24         stOut.pop();
25         return res;
26         
27     }
28     
29     /** Get the front element. */
30     int peek() {
31          if(stOut.empty()){
32             while(!stIn.empty()){
33                 stOut.push(stIn.top());
34                 stIn.pop();
35             }
36         }
37         return  stOut.top();
38         // int res = this->pop();
39         // stOut.push(res);
40         // return res;
41     }
42     
43     /** Returns whether the queue is empty. */
44     bool empty() {
45         // if(stIn.empty() && stOut.empty()) return true;
46         // else return false;
47         return stIn.empty() && stOut.empty();
48     }
49 };
50 
51 /**
52  * Your MyQueue object will be instantiated and called as such:
53  * MyQueue* obj = new MyQueue();
54  * obj->push(x);
55  * int param_2 = obj->pop();
56  * int param_3 = obj->peek();
57  * bool param_4 = obj->empty();
58  */

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