栈:吃进去吐出来 对列：吃进去拉出来
数据结构中的栈具有后进先出的特性，而内存中的栈是一个内存空间，只不过这个内存空间具与数据结构的栈具有相同的特性。
栈和队列基本操作
栈中没有迭代器，因为不需要遍历元素。
栈里面肯定有，push/pop/top操作，而且三个操作的时间复杂度是---->O(1) 我们要添加一个操作是 获取最小值的操作------>O(1) 对于一个普通的栈，要获取它的最小的元素，它的时间复杂度就不一定是O(1),因为只有把元素放在栈顶位置才能取
用一个栈，一次性压入两个元素，比如我要压入2，此时栈空，那么这个2也就是栈中最小值，我们规定第一次压入的2代表栈中的数据，而第二次我们再把2压入代表栈中最小元素。 如果此时再来了一个数是1，那么我门先拿这个数与栈顶元素也就是栈中最小值进行比较，小，那么我们再压入两次1，两个1代表的意思跟上面的2一样 如果此时再来一个3，我们拿3与栈顶元素也就是栈中最小值进行比较，大，那么我们第一次压入栈中数据元素3，第二次压入1，也就是始终保持物理上的栈顶元素是最小的，但是理论上的栈顶元素是物理上的栈顶元素的下一个元素。
用两个栈，一个放数据，另外一个放最小值
最小栈实现
给两个序列，一个是弹出的序列，另外一个是压入的序列，看看弹出序列是否匹配压入序列
入栈: 如果栈是空的或者栈顶元素不等于出栈序列的当前元素出栈，如果栈顶元素等于出栈序列，出栈。 class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { //入栈序列和出栈序列的个数都不一样，那么肯定不匹配 if(pushV.size() != popV.size()) return false; stack<int>s; size_t inIdx=0; //标记入栈元素 size_t outIdx=0; //标记待出栈元素 while(outIdx < popV.size()) { while(s.empty()|| s.top() != popV[outIdx]) { if(inIdx < pushV.size()) s.push(pushV[inIdx++]); else return false ; } s.pop(); ++outIdx; } return true; } };必须用到栈 stack<int>s;用来保存所遇到的数字
依次取表达式种的每一项，for (size_t i = 0; i < tokens.size(); ++i)
每一项是有可能是数字或者操作符，需要判断一下if (!("+" == str || "-" == str || "*" == str || "/" == str))
如果是数字，每项都是字符串，所以需要atoi转化一下，再入栈s.push(atoi(str.c_str()));
取操作符，到栈中取当前操作符的左右操作数
int right = s.top(); s.pop(); int left = s.top(); s.pop();选择是什么类型的运算，并进行元素后再次入栈
switch (str[0]) { case'+': s.push(left + right); break; case'-': s.push(left - right); break; case'*': s.push(left * right); break; case'/': //题目中说了右操作数不会为0 s.push(left / right); break; }结果就在栈顶位置，return s.top();
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> s; for (size_t i = 0; i < tokens.size(); ++i){ string& str = tokens[i]; if (!("+" == str || "-" == str || "*" == str || "/" == str)){ //数字 s.push(atoi(str.c_str())); } else{ //操作符 int right = s.top(); s.pop(); int left = s.top(); s.pop(); switch (str[0]) { case'+': s.push(left + right); break; case'-': s.push(left - right); break; case'*': s.push(left * right); break; case'/': s.push(left / right); break; } } } return s.top(); } };