用两个栈实现队列
队列先进先出，栈是后进先出，用两个栈实现队列即可
一个当作入队列，一个当作出队列，当出队列的栈为空时，把入队列的栈的内容全部装入出队列的栈
public class StackQueue {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node){
stack1.push(node);
}
public int pop(){
if(stack2.empty()){
while(!stack1.empty())
stack2.push(stack1.pop());
}
return stack2.pop();
}
最小栈的实现
一个栈保存正常数据，一个栈保存当前栈中的最小值，也就是改下push和pop，记得要更新当前栈中的最小值撒
最大栈和这个原理都一样的
class MinStack {
public:
/** initialize your data structure here. */
int min1;
stack<int> a, b;
MinStack() {
min1 = INT_MAX;
}
void push(int x) {
min1 = min(min1, x);
a.push(x);
b.push(min1);
}
void pop() {
a.pop();
b.pop();
if (b.empty())
min1 = INT_MAX;
else
min1 = b.top();
}
int top() {
return a.top();
}
int getMin() {
return b.top();
}
};
涉及求队列最大最小值相关，请参考单调队列和单调栈
栈题目
对于括号题目一般涉及栈。
解法是用stack, 然后每次入栈时，上下文清空，可以理解为入栈了一个空上下文。退栈时，把栈顶数据pop并merge到栈里上一个上下文。
比如726. 原子的数量 ，
给你一个字符串化学式 formula ，返回 每种原子的数量 。
原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。
如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。
例如，”H2O” 和 “H2O2” 是可行的，但 “H1O2” 这个表达是不可行的。 两个化学式连在一起可以构成新的化学式。
例如 “H2O2He3Mg4” 也是化学式。 由括号括起的化学式并佐以数字（可选择性添加）也是化学式。
例如 “(H2O2)” 和 “(H2O2)3” 是化学式。 返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。
那我们的上下文就可以是个counter, 每个原子的数量。
入栈时，加个空的counter, 退栈时，pop栈顶 并乘以数字 merge到新栈顶。
class Solution:
def countOfAtoms(self, formula: str) -> str:
stack = [collections.Counter()]
key = ""
i = 0
while i < len(formula):
if formula[i].isupper():
start = i
i += 1
while i < len(formula) and formula[i].islower():
i += 1
key = formula[start:i]
if i == len(formula) or not formula[i].isdigit():
stack[-1][key] += 1
elif formula[i].isdigit():
count = 0
while i < len(formula) and formula[i].isdigit():
count = count * 10 + int(formula[i])
i += 1
stack[-1][key] += count
elif formula[i] == "(":
# 入栈
stack.append(collections.Counter())
i += 1
elif formula[i] == ")":
# 当前退栈，并和栈里的context合2为一
counter = stack.pop()
ratio = 0
i += 1
while i < len(formula) and formula[i].isdigit():
ratio = ratio * 10 + int(formula[i])
i += 1
ratio = max(ratio, 1)
for k in counter.keys():
stack[-1][k] += counter[k] * ratio
# print(counter.items())
counter = stack[-1]
keys = counter.keys()
keys = sorted(keys)
res = ""
for k in keys:
res += k
if counter[k] > 1:
res += str(counter[k])
return res
类似题目: 394. 字符串解码
给定入栈顺序，求某个出栈顺序。