一、最小栈：
具体题目：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack(),初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。
题目剖析：
1、必须有常规栈的基本操作 2、提供或者栈中元素中最小值的操作，并且时间复杂度文为O（1）。
初级思路
思路一：使用俩个栈，一个保存元素，一个保存最小值。（datastack保存每次入栈的元素 ，minstack保存栈中的最小值）
入栈push（data）
>>每次将datastack中保存一份
>>minstack为空 || data<=栈中的最小值，data也要往minstack中放一份
出栈
>>datastack和minstack栈顶元素相等时，minstack需要出栈一个元素
>>datastack每次都需要一个元素出栈
思路二：使用一个栈，但是栈中每次压入两个元素，一个是当前元素，一个是更新的最小值。
struck Elem { int data; int min; }
具体代码实现
//方法一： class MinStack { public: MinStack() { //不需要实现，编译器会自动构造 } void push(int val) { //不管咋样都需要将元素压入_elem中 _elem.push(val); //为空或者x小于min栈中的栈顶元素压入min栈 if(_min.empty()||val<=_min.top()) _min.push(val); } void pop() { //如果——elem中的元素与_min中相等的时候，将min中的元素弹出 if(_min.top()==_elem.top()) _min.pop(); _elem.pop(); } int top() { return _elem.top(); } int getMin() { return _min.top(); } std::stack<int>_elem;//保存所有元素 std::stack<int>_min;//保存最小值 };
//方法二： class MinStack { public: struct elem{ int data; int min; };//定义一个结构体保存元素和最小值 MinStack() { } void push(int val) { elem e{val,val}; //更新最小值 if(!s.empty()&&val>getMin()){ e.min = getMin(); } //将元素压栈 s.push(e); } void pop() { if(!s.empty()) s.pop(); } int top() { return s.top().data; } int getMin() { return s.top().min; } std::stack<elem>s; };
二、逆波兰表达式
前提： 前缀表达式:操作符在两个操作数之前，比如+ a b
中缀表达式:操作符在两个操作数中间，比如a + b
后缀表达式:操作符在两个操作数之后，比如ab +
具体题目：
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
注意：有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。 表达式中不含除零运算 。
输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。
题目剖析：
而逆波兰表达式是后缀表达式，它的作用是可以让计算机非常简单的计算四则混合运算。
解释:不同运算符优先级不同，比如加减乘除的优先级，带括号的优先级都可以进行改变，对于计算机来说，能否将表达式中的（）去掉，然后让计算机按照运算符出现的先后顺序进行运算即可。
简答思路：
遍 历tokens,拿到每个元素之后:如果该元素是数字:入栈，如果该元素是运算符—要进行该种运算: 需要从栈中取出两个操作数，进行该种运算。
注意:
从栈中取出的第一个数字是该运算符的右操作数
从栈中取出的第二个数字是该运算符的左操作数
计算完成之后将该结果压栈, 当将tokens遍历结束之后，计算就结束了 最终的结果就在栈顶
使用引用：放的是string对象，否则要调一遍拷贝构造函数;atoi：将字符串转化为单个字符，传参是char*类型的，所以要先使用s.c_str()进行转化;注意要考虑负数，要不会和减法相互矛盾，把负数当做运算符进行处理了，所以不能用e[0]，直接使用字符串进行比较即可。
具体代码实现
class Solution { public: stack<int>s; int evalRPN(vector<string>& tokens) { for(auto& e:tokens){ if(!(("+"==e)||("-"==e)||("*"==e)||("/"==e))){ //数字，压栈 //将字符串转化为单个字符压栈 s.push(atoi(e.c_str())); } else{ //符号就取出来运算，取俩个元素，一个放右，一个放左 int right =s.top(); s.pop(); int left = s.top(); s.pop(); switch(e[0]){ case '+': s.push(right+left); break; case '-': s.push(left - right); break; case '*': s.push(left * right); break; case '/': // 题目说明了不存在除数为0的情况 s.push(left / right); break; } } } return s.top(); } };
栈的压入和弹出
具体题目：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
题目剖析：
就是模拟实现第二个序列是否为第一个序列的弹出顺序，关键就是找到第二个序列中的第一个元素和第一个序列的关系。
初级思路：
元素入栈，栈顶元素和出栈元素比较，栈顶元素和出栈元素比较，不同就一直入栈（循环）,使用俩个指针标记入栈元素和出栈元素。相等就出栈，然后指向出栈的指针向后移动一位。
具体代码实现:
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { int outidx = 0; int indix = 0; std::stack<int>s; //只要出栈的元素没有走完，循环继续 while(outidx<popV.size()){ //入栈元素为空或者不等于出栈元素，就压栈 while(s.empty()||s.top()!=popV[outidx]){ if(indix<pushV.size()){ s.push(pushV[indix]); indix++;//控制压栈的元素向后移动一位 } else //这里就是压栈元素都压完了还没找到，所以为false return false; } //相等了，需要出栈，控制出栈的指针向后移动一位 s.pop(); outidx++; } //所有的出栈元素都走完了，说明入栈元素也完了，符合，返回true return true; } };
用栈模拟实现队列
具体题目：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：题目链接
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false
题目剖析：
众所周知，栈是先进后出的，而对列是先进先出的，用栈实现队列就像使用俩个被子倒水一样.
初级思路：
将一个栈当作输入栈，用于压入 push\texttt{push}push 传入的数据；另一个栈当作输出栈，用于 pop操作。每次 pop 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
具体代码实现：
class MyQueue { private: stack<int> inStack, outStack; void in2out() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: MyQueue() {} void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { in2out(); } int x = outStack.top(); outStack.pop(); return x; } int peek() { if (outStack.empty()) { in2out(); } return outStack.top(); } bool empty() { return inStack.empty() && outStack.empty(); } };
