从C语言到C++_18(stack和queue的常用函数+相关练习)力扣（上）：https://developer.aliyun.com/article/1521375
4. 栈和队列的相关OJ题
155. 最小栈 - 力扣（LeetCode）
难度中等
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。
int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-2^31 <= val <= 2^31 - 1pop、top和getMin操作总是在 非空栈 上调用push,pop,top, andgetMin最多被调用3 * 10^4次
class MinStack { public: MinStack() { } void push(int val) { } void pop() { } int top() { } int getMin() { } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
解析代码：
思路：使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，
与当前元素比较得出最小值将这个最小值插入辅助栈中；
当一个元素要出栈时，我们把辅助栈的栈顶一样元素也一并弹出；
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
给个图理解理解：
class MinStack { public: MinStack() { // 构造函数不用写，删掉也行 } void push(int val) { _st.push(val); if(_minst.empty() || val <= _minst.top())//要先判空 { _minst.push(val);//栈空或者值小于等于栈顶元素才入栈 } } void pop() { if(_st.top() == _minst.top()) { //题目说栈空 不会调用pop，top和getMin，所以不判空也行 _minst.pop();//两个栈元素相等就_minst.pop } _st.pop();//要先判断_minst要不要pop } int top() { return _st.top(); } int getMin() { return _minst.top(); } private: stack<int> _st;// 一个栈完成常规接口 stack<int> _minst; // 一个栈完成getMin }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
拓展：如果面试的时候问到这题，面试官问你如果要插入的元素中包含大量的重复数据的话，
比如100万个1，中间包含不一样的数，要怎么优化呢？
这就考察到引用计数了。我们的辅助栈可以存一个结构体一个存值，一个计数：
可以去写写，面试时也不一定要写，可能就是讲思路，主要是考察思维或不活跃。
剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）
946. 验证栈序列 - 力扣（LeetCode）
栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
ps（上面三题是一模一样的，血赚两题）
难度中等
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，
序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，
但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushed是popped的排列。
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { } };
解析代码：
遍历两个数组，模拟入栈和出栈操作，判断两个数组是否为有效的栈操作序列。
不求同年同月同日入栈，但求同年同月同日出栈：
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { if (pushed.size() != popped.size()) { return false; } stack<int> st; int popi = 0;//出栈序列的下标 for (const auto& e : pushed)//遍历入栈序列 { st.push(e);//不匹配就持续入，匹配就持续出 while (!st.empty() && st.top() == popped[popi]) { st.pop();//一样的话就出栈，++popi ++popi; } } //return popi == popped.size();//出栈序列全部匹配->true return st.empty();//st为空->true } };
牛客代码：
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { if (pushV.size() != popV.size()) { return false; } stack<int> st; int popi = 0; for(const auto& e : pushV) { st.push(e); while(!st.empty() && st.top() == popV[popi]) { st.pop(); ++popi; } } return st.empty(); } };
从C语言到C++_18(stack和queue的常用函数+相关练习)力扣（下）：https://developer.aliyun.com/article/1521384
