栈和队列都是操作受限的线性表，与普通线性表相比，栈是一种插入和删除位置受限的线性表。栈限制只能在线性表的尾部进行插入或者删除操作，因此栈遵循后进先出的原则。栈的后进先出的设计特点使它在程序设计中有着重要作用，可以应于解决表达式求值、 括号匹配、数制转换、函数调用、八皇后问题和迷宫问题求解等 。
栈的存储方式是顺序和链式存储皆可，但是顺序栈更加常见。
数组模拟顺序栈
直接上Java代码
class ArrayStack {
public int maxSize;
public int[] stack;
public int top = -1;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
//栈空
public boolean isEmpty() {
return top == -1;
}
//栈满
public boolean isFull() {
return top == maxSize - 1;
}
//入栈
public void push(int num) {
if (isFull()) {
System.out.println("栈满，无法入栈");
return;
}
top++;
stack[top] = num;
}
//出栈
public int pop() {
if (isEmpty()) {
throw new RuntimeException("空栈，无法出栈");
}
int val = stack[top];
top--;
return val;
}
//获取栈顶元素
public int peek() {
if (isEmpty()) {
throw new RuntimeException("空栈，无法获取栈顶元素");
}
return stack[top];
}
//遍历栈
public void list() {
if (isEmpty()) {
System.out.println("空栈，无法遍历");
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
测试代码和上述数组模拟栈的代码一起放在了这里
中缀表达式转后缀表达式
我们平常遇到的四则运算表达式是中缀表达式，比如a+(b-c)*d，还有前缀表达式和后缀表达式，前缀表达式又叫波兰表达式，后缀表达式又叫逆波兰表达式。了解他们对后面二叉树的前缀、中缀和后缀表达式的学习很有帮助。
它们之间可以相互转换，但一般是中缀转前缀或者后缀，其中中缀转后缀更常见，因为在处理后缀表达式时从左至右处理即可，而前缀表达式需要从右至左。
转换之前需要提醒：之所以不直接处理中缀字符串，而是先把中缀字符串转换为列表的原因主要是因为字符串处理多位数的运算不方便，如10+(2+3)*4-5这个表达式中的10实际是一个整体，但是字符串就不能很好处理，因此先把字符串中的每一个元素先存储在一个列表中。
- 步骤
1.把前缀表达式转换成前缀表达式列表
2.把前缀表达式列表转换成后缀表达式列表
3.后缀表达式运算 - 中缀转后缀规则
转换需要一个列表用于存储后缀表达式，下面统称结果列表；需要一个栈用于存储运算符和左括号，下面统称为栈。
遍历前缀表达式列表
1.如果遇到的是数值，数值直接添加到结果列表中
2.如果遇到的是左括号，左括号入栈
3.如果遇到的是右括号，依次把栈中的运算符取出放入到结果列表中，直到取出的是左括号（左括号不放入结果列表）
4.如果遇到的运算符，需要分以下几种情况4.1.如果当前栈为空，运算符入栈
4.2.如果当前栈不为空，且栈顶元素为左括号，运算符入栈
4.3.如果当前栈不为空，且栈顶元素为运算符，且它的优先级比当前运算符的优先级低，运算符入栈
4.4.如果当前栈不为空，且栈顶元素为运算符，且它的优先级比当前运算符的优先级高，栈顶运算符取出放入到后缀表达式列表中。并且继续让当前运算符重走第4步
5.遍历结束后，把栈中剩下的操组符依次取出添加到结果列表中
附Java实现过程，代码中用到了另外两个方法
- toArrayList 方法用于把前缀表达式字符串转换为字符串列表形式
- priority 方法用于自定义运算符优先级
它们的实现以及下方代码都可以在文末找到。
//转后缀表达式
public static List toSuffixExpeession(String expression) {
List list = toArrayList(expression);
//中缀表达式先转为列表：[15, +, (, 2, +, 3, ), *, 4, -, 5]
Stack<String> opStack = new Stack<String>();//操作符栈
ArrayList suffixList = new ArrayList();//用于存放后缀表达式列表
int length = list.size();
String item = "";//列表项
for (int i = 0; i < length; i++) {
item = list.get(i).toString();
//根据规则转换
if (item.matches("\\d+")) {
suffixList.add(item);
} else if (item.equals("(")) {
opStack.add(item);
} else if (item.equals(")")) {
//获取操作符栈的栈顶元素
String stackTop = "";
while (!(stackTop = opStack.pop()).equals("(")) {
suffixList.add(stackTop);
}
} else {//操作符
while (true) {
if (opStack.size() == 0) {
opStack.push(item);
break;
} else if (opStack.peek().equals("(")) {
opStack.push(item);
break;
} else if (priority(item) > priority(opStack.peek())) {
opStack.push(item);
break;
} else {
//当前运算符优先级小于运算符栈的栈顶运算符的优先级
suffixList.add(opStack.pop());
}
}
}
}
while (opStack.size() != 0) {
suffixList.add(opStack.pop());
}
return suffixList;
}
后缀表达式运算
得到后缀表达式之后，进行运算就很简单了，这里需要一个栈用于后缀表达式的计算。
- 运算规则：
1.遍历后缀表达式，遇到数值，数值入栈
2.遇到操作符，取出栈顶元素和次栈顶元素，结合该操作符进行运算，并把运算结果入栈。
3.遍历结束后，栈中剩下的那个元素就是最终的结果。
注意：因为从左向右遍历的缘故，在中缀转后缀表达式时，左边的数值先进入结果队列；而对后缀表达式运算是，也是左边的元素先入栈，因此数值和运算符的相对位置是 次栈顶元素 运算符 栈顶元素。以a-b为例，转换成后缀表达式为ab-，而对它遍历时a先入栈，b再入栈，所以栈顶元素b要放在运算符后。
附后缀表达式运算的Java代码
public static int calculate(List suffixList) {
Stack<String> numStack = new Stack<>();
int length = suffixList.size();
String item = "";
int num1;//栈顶元素
int num2;//次栈顶元素
int res;//存储中间计算数值
for (int i = 0; i < length; i++) {
item = suffixList.get(i).toString();
if (item.matches("\\d+")) {
//数字入栈
numStack.push(item);
} else {
//运算符：取出栈顶的两个元素进行运算，并把结果入栈
num1 = Integer.parseInt(numStack.pop());
num2 = Integer.parseInt(numStack.pop());
if (item.equals("+")) {
res = num2 + num1;
} else if (item.equals("-")) {
res = num2 - num1;
} else if (item.equals("*")) {
res = num2 * num1;
} else {
res = num2 - num1;
}
numStack.push(res + "");
}
}
//栈中最后剩下的元素就是最终结果
return Integer.parseInt(numStack.pop());
}
文中后缀表达式相关的代码都放在了本人 GitHub上。
声明：文中后缀表达式转换规则参考了[面试算法]中缀表达式转后缀表达式Python
