1. 题目：155.最小栈
思路分析：
从解释那段代码调用，我们可以知道MinStack是一个很普通的栈，就多一个函数而已。所以就可以在MinStack的属性里加一个stack，再加一个可以时刻记录栈内最小值的容器就可以。
思路1：两个栈实现最小栈
设计两个栈，一个正常栈（s1），一个用于记录正常栈每次push或者pop后的最小值（minS）。要获得MinStack的最小值，只需要访问minS的top就可以。
代码实现：
class MinStack { public: MinStack() {} void push(int val) { s1.push(val); if(minS.empty()||val<minS.top()) minS.push(val); else minS.push(minS.top()); } void pop() { s1.pop(); minS.pop(); } int top() { return s1.top(); } int getMin() { return minS.top(); } private: stack<int> s1; stack<int> minS; };
2.题目: JZ31 栈的压入、弹出序列
思路分析：
平时我们做这样的选择题是怎么做的？自己是不是要模拟实现一下。所以这里我们也同样可以来模拟实现一下，看匹不匹配。
思路1：模拟实现
- 模拟实现，判断栈的出入顺序匹不匹配，肯定要有个栈s1。
- 再来过程，pushV把数据push到栈里，每次push后，栈顶元素与序列popV头元素（或者指针元素）对比，若相等，两个都头删（栈头删，popV指针后移），再比较，直到不相等，然后再接着pushV进栈（vector没有头删，所以用指针记录好些）。
- 结果判断：可以判断popV的指针位置，也可以判断栈s1是否已经pop完了。
- 代码实现：
class Solution { public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // write code here stack<int> s; int j=0; for(int i=0;i<pushV.size();i++) { s.push(pushV[i]); while(!s.empty()) { if(s.top()==popV[j]) { s.pop(); j++; } else break; } } return j==popV.size(); } };
3.题目: 150.逆波兰表达式求值
思路分析：
这题的要求就是计算逆波兰表达式的值，也叫后缀表达式（运算符放到后面），计算规则很简单，主要是设计一些判断。
运算规则：符号前两个数字，通过这个运算符计算后再次存入，直到把最后一个运算符运算结束。
思路1：暴力
遍历tokens，是数字就按顺序存在容器里，遇到运算符，就取出最近插入的两个数字计算，注意前面的减后面的（减法和除法注意），然后再把计算结果返回到容器里。直到遍历完。
代码实现：
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> s; for(int i=0;i<tokens.size();i++) { if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/") { if(tokens[i]=="+") { int k=s.top(); s.pop(); k+=s.top(); s.pop(); s.push(k); } else if(tokens[i]=="-") { int k=s.top(); s.pop(); k=s.top()-k; s.pop(); s.push(k); } else if(tokens[i]=="*") { int k=s.top(); s.pop(); k*=s.top(); s.pop(); s.push(k); } else if(tokens[i]=="/") { int k=s.top(); s.pop(); k =s.top()/k; s.pop(); s.push(k); } } else s.push(stoi(tokens[i])); } return s.top(); } };
4.题目：232.用栈实现队列
思路分析：
用栈来实现队列，要从先进后出变到先进先出。
思路1：两个栈
其实只是需要一个辅助栈就可以了。正常栈push进数据，再要pop或者返回top的时候，几把数据push到辅助栈里，然后辅助栈pop、top都可以。
代码实现：
class MyQueue { public: void push(int x) { s1.push(x); } int pop() { if (s2.empty()) while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } int k = s2.top(); s2.pop(); return k; } int peek() { if (s2.empty()) while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } return s2.top(); } bool empty() { return s1.empty() && s2.empty(); } stack<int> s1; //正常栈 stack<int> s2; //辅助栈 };
5.题目：225.用队列实现栈
思路分析：
这种题主要是设计，思路方面比较明确的。用队列实现栈。
思路1：一个队列实现
一个队列思路就是：一个元素进去，要保证它是在front位置，怎么保证，把前面的所有元素再一次push进队列就可以。
代码实现：
class MyStack { public: queue<int> q; /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { int n = q.size(); q.push(x); for (int i = 0; i < n; i++) { q.push(q.front()); q.pop(); } } /** Removes the element on top of the stack and returns that element. */ int pop() { int r = q.front(); q.pop(); return r; } /** Get the top element. */ int top() { int r = q.front(); return r; } /** Returns whether the stack is empty. */ bool empty() { return q.empty(); } }; 作者：力扣官方题解 来源：力扣（LeetCode）
思路2：两个队列：入栈O(n),出栈O(1)
入栈O(n),出栈O(1): 这就说明在push时候导元素。一个栈保持空队列，每次push就往里push，再把另一个栈顺序的队列的元素全部导到这个刚push一个的元素里。然后交换两个队列，push队列依旧是空，顺序队列依旧顺序和栈要求顺序一样（pop、front就是后进的元素）
代码实现：
class MyStack { public: queue<int> queue1; queue<int> queue2; /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { queue2.push(x); while (!queue1.empty()) { queue2.push(queue1.front()); queue1.pop(); } swap(queue1, queue2); } /** Removes the element on top of the stack and returns that element. */ int pop() { int r = queue1.front(); queue1.pop(); return r; } /** Get the top element. */ int top() { int r = queue1.front(); return r; } /** Returns whether the stack is empty. */ bool empty() { return queue1.empty(); } }; 作者：力扣官方题解 来源：力扣（LeetCode）
思路3：两个队列：入栈O(1),出栈O(n)
入栈O(1),出栈O(n): 这就说明pop处导元素。一个队列只是push进，不做其他处理。只有到了pop时候，就把这个队列的元素除了最后进的元素外，其他全部push到第二个队列。再次pop的话，就用第二个队列做同样的操作。top的话只需要看哪个队列不为空，返回最后一个元素就可以。
代码实现：
class MyStack { public: void push(int x) { q1.push(x); } int pop() { int k; if (!q1.empty()) { while (q1.size() > 1) { q2.push(q1.front()); q1.pop(); } k = q1.front(); q1.pop(); } else { while (q2.size() > 1) { q1.push(q2.front()); q2.pop(); } k = q2.front(); q2.pop(); } return k; } int top() { if (!q1.empty()) return q1.back(); else return q2.back(); } bool empty() { return q1.empty() && q2.empty(); } queue<int> q1; queue<int> q2; };
