文章结构
- 栈是什么
- Java中的Stack源码分析
- 什么时候使用栈
- 应用实例：使用栈来解决表达式计算问题
1、栈是什么
栈是一种操作受限的线性表，只能在一端插入和删除数据，栈中的元素遵循先入后出，后入先出的原则。
用一个形象的比方就是我们平时叠盘子，从下往上一个一个的叠，然后取的时候从上往下一个一个的取。
栈示意图
2、Java中的Stack源码分析
Stack继承自Vector，Stack中数据存储是使用数组来实现的。下面我们一一分析Stack的初始化，入栈、出栈和扩容操作
2.1 Stack的初始化
Stack只有一个无参构造函数
/**
* Creates an empty Stack.
*/
public Stack() {
}
但是无参构造函数默认会去调用父类的无参构造函数，Vector的无参构造函数如下
public Vector() {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
最后我们看到Stack在Vector的构造函数中创建了一个大小为10的elementData数组用来存放添加的元素。
2.2 入栈操作
Stack的入栈操作方法
public E push(E item) {
addElement(item);
return item;
}
push()中调用父类Vector中的addElement()方法向elementData数组中添加元素，addElement()源码如下
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
其中ensureCapacityHelper(elementCount + 1)是用来判断是否需要对
elementData数组进行扩容的，我们放到后面的扩容里面去分析
2.3 出栈操作
Stack定义了pop()方法来返回栈顶元素
public synchronized E pop() {
E obj;
int len = size();
obj = peek();//获取栈顶元素
removeElementAt(len - 1);//删除栈顶元素
return obj;
}
获取栈顶元素,注意的时候在获取栈顶元素的时候，要先判断栈是否为空，如果栈为空的情况下去获取栈顶元素，会抛出EmptyStackException异常
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);//从elementData取栈顶元素
}
删除栈顶元素
public synchronized void removeElementAt(int index) {
modCount++;
/**
*下面的注释是我加的，栈中删除元素index==elementcount-1；这段代码不会执行
*/
// if (index >= elementCount) {
// throw new ArrayIndexOutOfBoundsException(index + " >= " +
// elementCount);
// } else if (index < 0) {
// throw new ArrayIndexOutOfBoundsException(index);
// }
// int j = elementCount - index - 1;
// if (j > 0) {
// System.arraycopy(elementData, index + 1, elementData, index, j);
// }
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
2.4 扩容
ensureCapacityHelper(elementCount + 1)调用传入需要的最小容量，然后拿最小容量和现在的elementData数组大小比较，如果需要的最小容量比elementData数组大，则调用grow(minCapacity)方法进行扩容
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
我们看一下grow()方法具体是怎么实现扩容的
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//计算扩容之后的大小
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//防止扩容超过数组的最大限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
capacityIncrement表示每次扩容的大小，默认是0，可以自己设置。如果capacityIncrement>0，则按照capacityIncrement的大小来扩容；如果capacityIncrement是0的时候，则执行newCapacity = oldCapacity +oldCapacity，也就是将elementData扩大一倍。但是我们要防止扩容之后的大小超过了数组的最大大小限制
顺序栈入栈和扩容示意图
3、什么时候使用栈
当我们需要这种先进后出，后进先出的操作特性的数据结构的时候，我们就可以想到使用栈。比如说，我们在用非递归方式去实现二叉树的遍历的时候，如中序遍历的非递归实现
private static void traverseMide2(StringBuilder builder, Node root) {
Stack<Node> stack = new Stack<>();//缓存要回溯的节点
Node temp = root;
while (temp != null || !stack.isEmpty()) {
while (temp != null) {
stack.push(temp);
temp = temp.left;
}
if (!stack.isEmpty()) {
temp = stack.pop();
builder.append(temp.value + ",");//打印节点
if (temp.right != null) {
temp = temp.right;
} else {
temp = null;
}
}
}
}
另外方法调用本身也是一种栈的形式
4、应用实例：使用栈来解决表达式计算问题
如何编写代码计算由括号和加减乘除组成的表达式，比方计算下面的表达式的值
2*5+30/(2+3)-10/2
分析
首先我们来看一下运算规则
- 从左向右运算
- 先计算括号里面的
- 再计算乘除法
- 再计算加减法
我们可以将括号作为一个子表达式，将计算过程分解为两类
- 加减乘除的运算实现
- 括号的运算实现
1. 加减乘除的运算实现
- 定义操作符的优先级：加和减优先级为10；乘和除优先级为20；（加减的优先级低于乘除的优先级）
- 使用两个栈来实现计算过程：一个栈用来保存操作数，一个栈用来保存操作符
- 计算过程：从左向右遍历表达式，
- 当遇到数字的时候，我们就直接压入操作数栈；
- 当遇到运算符的时候，我们就把运算符和运算符栈顶的元素进行比较：如果比运算符栈顶元素的优先级高，就将当前运算符入栈；如果比运算符栈顶元素的优先级低或者相同，则从运算符栈中取栈顶运算符，从操作数栈的栈顶取两个操作数进行计算，再把计算完的结果压入操作数栈，然后拿这个操作符继续和运算符栈顶元素比较。
计算过程演示
2. 括号的运算实现
- 定义括号的优先级：括号优先级为0；（低于加减乘除的优先级，这样不会破坏上面的计算过程）
- 遇到左括号：将括号添加到运算符栈顶
- 遇到右括号：计算栈中数据，直到操作符栈顶为左括号；将左括号出栈，继续遍历
代码实现
public class ExpressionCalculate {
public static int calculate(String expression) {
Stack<Integer> stackValue = new Stack<>();
Stack<Character> stackOperator = new Stack<>();
if (expression == null || expression.trim().length() == 0) {
return Integer.MIN_VALUE;
}
char[] array = expression.toCharArray();
for (int i = 0; i < array.length; i++) {
char ch = array[i];
if (ch >= '0' && ch <= '9') {
int value = ch - '0';
while (i + 1 < array.length && array[i + 1] >= '0' && array[i + 1] <= '9') {//获取操作数
value = value * 10 + array[i + 1] - '0';
i++;
}
stackValue.add(value);
} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
int level = getLevel(ch);
while (!stackOperator.isEmpty() && level <= getLevel(stackOperator.peek())) {//当前操作符比操作符栈顶的操作符级别低或者相等
calculate(stackValue, stackOperator);//执行计算：操作符栈顶元素出栈，从操作数
}
stackOperator.push(ch);//操作符入栈
} else if (ch == '(') {//将左括号入栈
stackOperator.push(ch);
} else if (ch == ')') {//右括号，将括号内的表达式计算完毕
while (!stackOperator.isEmpty() && stackOperator.peek() != '(') {
calculate(stackValue, stackOperator);
}
stackOperator.pop();//括号计算完之后，左括号出栈
}
}
while (!stackOperator.isEmpty()) {//表达式已结束，将栈中所有数据计算完毕
calculate(stackValue, stackOperator);
}
return stackValue.pop();
}
private static void calculate(Stack<Integer> stackValue, Stack<Character> stackOperator) {
int num2 = stackValue.pop();
char operator = stackOperator.pop();
int num1 = stackValue.pop();
switch (operator) {
case '+':
num2 = num1 + num2;
break;
case '-':
num2 = num1 - num2;
break;
case '*':
num2 = num1 * num2;
break;
case '/':
num2 = num1 / num2;
break;
}
stackValue.push(num2);
}
/**
* 获取操作符级别
*/
private static int getLevel(char ch) {
switch (ch) {
case '+':
case '-':
return 10;
case '*':
case '/':
return 20;
case '(':
case '）':
return 0;
}
return -1;
}
}
完整的源码和测试用例请查看github之ExpressionCalculate和ExpressionCalculateTest
说明
文中图片来源：极客时间，王争《数据结构与算法之美》
