3. 栈的压入弹出序列
题目链接：栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
题干：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 0<=pushV.length == popV.length <=1000
- -1000<=pushV[i]<=1000
- pushV 的所有数字均不相同
示例1
输入：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
解释：可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列，返回true
示例2
输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false
解释：由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false
题目分析：
对于这种题目，我们要想暴力穷举的话，那复杂度确实有点过于高了，所以现在有个想法就是能不能模拟一下栈的操作，并且与弹出序列对比
首先创建一个栈，然后遍历pushV中的数据，并压栈，然后判断栈顶的数据与popV中的当前数据是否相等，如果相等就出栈，否则就继续入栈，如果遍历完pushV之后，栈是空的，那么说明popV序列是可得的，返回true，否则返回false。
代码实现：
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> st; int i = 0; for(auto& e : pushV) { st.push(e); while(!st.empty() && (st.top() == popV[i])) { st.pop(); ++i; } } return st.empty(); } };
4. 栈实现队列
题目链接：232. 用栈实现队列 - 力扣（LeetCode）
题干：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
题目分析：
按照题目要求，使用两个栈来实现一个队列。栈和队列都是容器适配器，只是提供的适配接口不同而已，栈是LIFO，队列是FIFO，所以我们使用两个栈来实现队列只需要控制好进队列和出队列的方式即可。
这里使用两个栈，我们分别命名为st_push，st_pop，对于进队列的操作，我们就把值push到st_push栈中，出队列的操作我们就只出st_pop栈中的元素，然后在合适的时机将st_push栈中的元素转换到st_pop栈中。这里注意一下，每次转换的时候都一定要将push栈中所有元素转换到pop栈中，并且当pop栈为空时才能转换，否则数据顺序就乱了
代码实现：
class MyQueue { public: MyQueue() {//这里默认构造函数就不用实现了，因为在这里成员变量会走初始化列表，在初始化列表这里会自动调用成员变量类型的默认构造函数 } void push(int x) { st_push.push(x); } void conversion()//st_push ==> st_pop { if(st_pop.empty()) { while(!st_push.empty()) { st_pop.push(st_push.top()); st_push.pop(); } } } int pop() { conversion();//当pop栈为空时，从push栈中导入所有元素 int ret = st_pop.top(); st_pop.pop(); return ret; } int peek() { conversion(); return st_pop.top(); } bool empty() { return st_pop.empty() && st_push.empty(); } stack<int> st_push; stack<int> st_pop; };
5. 队列实现栈
题目链接：225. 用队列实现栈 - 力扣（LeetCode）
题干：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
题目分析：
和上一道题相同，我们只需要控制入栈和出栈的顺序即可
由于想出栈就得出队尾的元素，所以需要先把队列中其他元素都出了，才能出到队尾的元素，这时候出的元素就用另一个队列存放，入队列的顺序也是固定的，所以队列内元素的顺序还是不变的，所以再插入元素的时候在非空队列内继续插入即可
代码实现：
class MyStack { public: queue<int> q1; queue<int> q2; MyStack() {//这里默认构造函数就不用实现了，因为在这里成员变量会走初始化列表，在初始化列表这里会自动调用成员变量类型的默认构造函数 } void push(int x) {//这里在结构上保证必须有一个队列是空的 if (q1.empty()) q2.push(x); else q1.push(x); } int pop() {//在需要pop的时候将非空队列的前n个值转换到空队列中，然后pop非空队列 if (q2.empty()) { swap(q1, q2); } //此时q1为空，q2有值 int size = q2.size(); for (size_t i = 0; i < size - 1; ++i) { q1.push(q2.front()); q2.pop(); } int ret = q2.front(); q2.pop(); return ret; } int top() {//非空队列中的最后一个元素即是栈顶元素 if (q1.empty()) { return q2.back(); } else return q1.back(); } bool empty() { return q1.empty() && q2.empty(); } };
