代码随想录算法训练营第十天| 232.用栈实现队列 225. 用队列实现栈
232.用栈实现队列
卡哥建议：大家可以先看视频，了解一下模拟的过程，然后写代码会轻松很多。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html
做题思路：
记住栈和队列的原理，队列是先进先出，栈是先进后出。如果把1，2，3，放入队列，出来顺序还是 1，2，3；但是在栈中，放入顺序是 1，2，3，出来顺序是 3，2，1，所以可以考虑用两个栈，一个入的栈，一个出的栈。把入的栈中所有的元素弹出到出的栈里，再从出的栈中把元素弹出来。如果进栈和出栈都为空的话，说明模拟的队列为空了。
代码：
1 class MyQueue {
2 public:
3 stack<int> stIn; //入的栈
4 stack<int> stOut; //出的栈
5 /** Initialize your data structure here. */
6 MyQueue() {
7
8 }
9 /** Push element x to the back of queue. */
10 void push(int x) { //入栈
11 stIn.push(x);
12 }
13
14 /** Removes the element from in front of queue and returns that element. */
15 int pop() { //出栈
16 // 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
17 if (stOut.empty()) {
18 // 从stIn导入数据直到stIn为空
19 while(!stIn.empty()) {
20 stOut.push(stIn.top());
21 stIn.pop();
22 }
23 }
24 int result = stOut.top(); //出的栈的顶部元素就是队列的首部元素
25 stOut.pop(); //把出的栈的元素全部弹出
26 return result;
27 }
28
29 /** Get the front element. */
30 int peek() { //返回队列首部的元素。
31 int res = this->pop(); // 直接使用已有的pop函数，获取从出的栈中弹出的元素，比如，1，2，3
32 stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去，模拟队列，所以要再添加
33 return res;
34 }
35
36 /** Returns whether the queue is empty. */
37 bool empty() {
38 return stIn.empty() && stOut.empty();
39 }
40 };
225. 用队列实现栈
卡哥建议：可以大家惯性思维，以为还要两个队列来模拟栈，其实只用一个队列就可以模拟栈了。 建议大家掌握一个队列的方法，更简单一些，可以先看视频讲解
题目链接/文章讲解/视频讲解：https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
做题思路：
不用像上个题用两个队列来做，可以用一个队列，比如，入栈顺序是 1，2，3，出栈顺序是 3，2，1；入队顺序是1，2，3，把 1，2出队；再把1，2入队，此时再把3出队，同理，其他元素类似，就实现了像栈先把3弹出........。
代码：
1 class MyStack {
2 public:
3 queue<int> que;
4 /** Initialize your data structure here. */
5 MyStack() {
6
7 }
8 /** Push element x onto stack. */
9 void push(int x) {
10 que.push(x);
11 }
12 /** Removes the element on top of the stack and returns that element. */
13 int pop() {
14 int size = que.size();
15 size--;
16 while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
17 que.push(que.front()); //que.front是队列的出队位置
18 que.pop();
19 }
20 int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
21 que.pop();
22 return result;
23 }
24
25 /** Get the top element. */
26 int top() {
27 return que.back(); //back是队列的入队位置
28 }
29
30 /** Returns whether the stack is empty. */
31 bool empty() {
32 return que.empty();
33 }
34 };