Stack详解(含动画演示)

Stack详解

基于JDK8

1、栈数据结构动画演示

从动画中可以看出，栈这种数据结构 只能从同一头进，从同一头出。
比较正式的说法叫： 后进先出（LIFO, Last In First Out）。

2、Stack的继承体系

public class Stack<E> extends Vector<E>

可以看到JDK提供的 Stack 是利用 Vector实现的。所以Stack 类也是线程安全的。

3、Stack的push (入栈)方法

public E push(E item) {// 调用 addElement 方法将 item 添加到 Vector 的末尾addElement(item);// 返回被添加的元素 itemreturn item;
}

public synchronized void addElement(E obj) {// 修改计数器增加，用于记录 Vector 被修改的次数modCount++;// 确保 Vector 有足够的容量来容纳新元素ensureCapacityHelper(elementCount + 1);// 将新元素添加到 elementData 数组的 elementCount 位置elementData[elementCount++] = obj;
}

private void ensureCapacityHelper(int minCapacity) {// 检查是否需要扩容，如果当前容量小于 minCapacity 则进行扩容if (minCapacity - elementData.length > 0)grow(minCapacity);
}

protected Object[] elementData;private void grow(int minCapacity) {// 当前数组的容量int oldCapacity = elementData.length;// 新的容量，如果 capacityIncrement 大于 0 则按此增量扩容，否则容量翻倍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);
}

上面只有push方法是Stack提供的，其余方法都是Vector类提供的。

4、Stack的pop (出栈)方法

public synchronized E pop() {E obj;int len = size();// 获取栈顶元素obj = peek();// 移除栈顶元素removeElementAt(len - 1);// 返回被移除的栈顶元素return obj;
}

public synchronized E peek() {int len = size();// 如果栈为空，抛出 EmptyStackException 异常if (len == 0)throw new EmptyStackException();// 返回栈顶元素（位于 elementData 数组的最后一个有效位置）return elementAt(len - 1);
}

public synchronized void removeElementAt(int index) {// 增加修改计数器modCount++;// 如果索引超出当前元素数量，抛出 ArrayIndexOutOfBoundsException 异常if (index >= elementCount) {throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);}// 如果索引为负数，抛出 ArrayIndexOutOfBoundsException 异常else if (index < 0) {throw new ArrayIndexOutOfBoundsException(index);}// 计算需要移动的元素个数int j = elementCount - index - 1;// 如果有需要移动的元素if (j > 0) {// 将 elementData 数组中 index + 1 到 elementCount - 1 的元素左移一位System.arraycopy(elementData, index + 1, elementData, index, j);}// 减少元素数量elementCount--;// 将最后一个元素设为 null 以便垃圾回收elementData[elementCount] = null;
}

pop (出栈)方法利用到了peek(获取栈顶元素)方法。

5、Stack是如何利用Vector实现栈数据结构的？

上面已经用动画演示了栈数据结构的特点：栈这种数据结构 只能从同一头进，从同一头出。

栈的主要操作包括以下几种：

• 压栈（push）：将元素添加到栈的顶部。
• 出栈（pop）：移除并返回栈顶元素。
• 查看栈顶元素（peek）：返回栈顶元素但不移除它。

Stack 类通过继承 Vector，并添加自己的方法，实现了这些操作。
push 方法
push 方法将元素压入栈顶。它实际上调用了 Vector 的 addElement 方法，将元素添加到 Vector 的末尾。

pop 方法
pop 方法移除并返回栈顶元素。它先调用 peek 方法获取栈顶元素，然后调用 removeElementAt 方法移除该元素。

peek 方法
peek 方法返回栈顶元素但不移除它。它直接访问 Vector 的最后一个元素。

Vector和ArrayList类似，底层都是使用Object数组来存储元素的。Stack通过操作数组的末尾，比如push只把元素添加到数组的末尾，pop只移除数组末尾的元素。

6、自己实现栈(不借助JDK提供的集合)

主要利用Object 数组和Arrays.copyOf方法

class MyStack<T>{// 默认容量private final Integer defaultCapacity = 10;// 存储元素的数组private Object[] elementData;// 真正存储的元素个数private int elementCount;public MyStack() {this.elementData = new Object[10];}public void push(T element){// 元素个数大于默认容量就复制数组if(gtDefaultCapacity(elementCount + 1)){// 创建一个新的数组，长度为当前数组长度加1Object[] newElements = Arrays.copyOf(elementData, elementCount + 1);newElements[elementCount++] = element;elementData = newElements;}else {// 否则就直接添加元素到数组末尾this.elementData[elementCount++] = element;}}// 获取栈顶元素@SuppressWarnings(value = "unchecked")public T peek(){if(elementCount<=0){throw new RuntimeException("当前栈为空!");}return (T)elementData[elementCount-1];}// 删除栈顶元素@SuppressWarnings(value = "unchecked")public T pop(){if(elementCount<=0){throw new RuntimeException("当前栈为空!");}Object temp = elementData[elementCount - 1];elementData = Arrays.copyOf(elementData, elementCount - 1);elementCount--;return (T) temp;}// 判断是否大于默认容量private boolean gtDefaultCapacity(int length){return length > defaultCapacity;}// 获取栈大小public int size(){return elementCount;}// 判断栈是否为空public boolean isEmpty(){return elementCount <= 0;}@Overridepublic String toString() {StringBuilder builder = new StringBuilder();for (int i =elementCount - 1 ; i >= 0; i--) {builder.append(elementData[i].toString()).append("  ");}return builder.toString();}}

测试：

public static void main(String[] args) throws Exception {MyStack<String> myStack = new MyStack<>();myStack.push("秀逗");myStack.push("四眼");myStack.push("大黄");System.out.println(myStack.peek());  //  大黄System.out.println(myStack.pop());  // 大黄System.out.println(myStack.size()); // 2System.out.println(myStack.isEmpty()); // falseSystem.out.println(myStack);  // 四眼  秀逗System.out.println(myStack.pop()); //  四眼  System.out.println(myStack.pop());//  秀逗 System.out.println(myStack.pop()); // java.lang.RuntimeException: 当前栈为空!}

我们利用Object 数组和Arrays.copyOf方法实现了一个简单的栈，这个栈包含基本的 push、peek、pop、size、isEmpty方法，并模拟出栈顺序重写了 toString。

7、自己实现栈(借助JDK提供的集合)

上面我们自己利用Object 数组和Arrays.copyOf方法实现了简单的栈，我们默认设置了10的容量，如果超过10个元素，我们利用Arrays.copyOf完成数组的复制。 这样做是非常耗费性能的，并且我们自己实现的栈是非线程安全的。
下面我们利用JDK现有的集合来实现栈。

利用 ArrayDeque 实现高性能的非线程安全的栈。

class MyStack<T>{// 使用 ArrayDeque 作为底层数据结构来存储栈元素private ArrayDeque<T> arrayDeque;// 构造方法，初始化 ArrayDequepublic MyStack() {this.arrayDeque = new ArrayDeque<T>();}// 将元素压入栈顶，使用 addFirst 方法将元素添加到双端队列的头部public void push(T elementData){arrayDeque.addFirst(elementData);}public void peek(){arrayDeque.getFirst();}public T pop(){return arrayDeque.removeFirst();}public int size(){return arrayDeque.size();}public boolean isEmpty(){return arrayDeque.isEmpty();}@Overridepublic String toString() {StringBuilder builder = new StringBuilder();// 这里不需要反序迭代  因为我们的push是往头部添加元素 直接正序迭代就是出栈顺序Iterator<T> iterator = arrayDeque.iterator();while (iterator.hasNext()){builder.append(iterator.next().toString()).append("  ");}return builder.toString();}
}

利用 ConcurrentLinkedDeque实现高性能的线程安全的栈。

class MyStack<T>{private ConcurrentLinkedDeque<T> concurrentLinkedDeque;public MyStack() {this.concurrentLinkedDeque = new ConcurrentLinkedDeque<T>();}public void push(T elementData){concurrentLinkedDeque.addFirst(elementData);}public void peek(){concurrentLinkedDeque.getFirst();}public T pop(){return concurrentLinkedDeque.removeFirst();}public int size(){return concurrentLinkedDeque.size();}public boolean isEmpty(){return concurrentLinkedDeque.isEmpty();}@Overridepublic String toString() {StringBuilder builder = new StringBuilder();// 这里不需要反序迭代  因为我们的push是往头部添加元素 直接正序迭代就是出栈顺序Iterator<T> iterator = concurrentLinkedDeque.iterator();while (iterator.hasNext()){builder.append(iterator.next().toString()).append("  ");}return builder.toString();}
}

ConcurrentLinkedDeque 的高性能线程安全设计，涉及到乐观并发控制策略比如CAS，延迟回收，分段锁等机制。
后面总结并发编程知识的时候再详细分析下ConcurrentLinkedDeque 的设计。

8、栈的应用场景

栈虽然是一种后进先出（LIFO, Last In First Out）的数据结构，但是却有广泛的应用场景。
下面是几个常见的例子：

①、浏览器的前进、后退功能实现

可以用两个栈分别存储前进和后退的页面
代码示例：

import java.util.Stack;public class TestA {public static void main(String[] args) {Browser browser = new Browser();browser.visit("百度");browser.visit("谷歌");browser.back();  //  百度browser.forward();  // 谷歌}
}class Browser {// 保存前进页面的栈，用于实现前进功能private Stack<String> forwardStack;// 保存后退页面的栈，用于实现后退功能private Stack<String> backStack;// 当前浏览的页面private String currentPage;// 初始化前进栈、后退栈和当前页面public Browser() {this.forwardStack = new Stack<>();this.backStack = new Stack<>();// 初始化默认页面为 "Home"this.currentPage = "Home";}/*** 访问新页面* @param page 新访问的页面*/public void visit(String page) {if (page == null) {throw new RuntimeException("页面不能为空");}// 将当前页面加入后退栈，因为我们将访问新的页面backStack.push(currentPage);// 更新当前页面为新访问的页面currentPage = page;// 打印当前浏览页面System.out.println("当前浏览页面：" + currentPage);// 清空前进栈，因为访问新页面时前进栈失效forwardStack.clear();}/*** 前进到下一页面*/public void forward() {System.out.println("前进");// 如果前进栈不为空if (!forwardStack.isEmpty()) {// 将当前页面加入后退栈backStack.push(currentPage);// 从前进栈弹出页面作为当前页面currentPage = forwardStack.pop();// 打印当前浏览页面System.out.println("当前浏览页面：" + currentPage);} else {// 前进栈为空，无法前进System.out.println("当前无前进页面");}}/*** 后退到上一页面*/public void back() {System.out.println("后退");// 如果后退栈不为空if (!backStack.isEmpty()) {// 将当前页面加入前进栈forwardStack.push(currentPage);// 从后退栈弹出页面作为当前页面currentPage = backStack.pop();// 打印当前浏览页面System.out.println("当前浏览页面：" + currentPage);} else {// 后退栈为空，无法后退System.out.println("当前无后退页面");}}/*** 获取当前浏览的页面* @return 当前页面*/public String getCurrentPage() {return currentPage;}
}

运行结果：

当前浏览页面：百度
当前浏览页面：谷歌
后退
当前浏览页面：百度
前进
当前浏览页面：谷歌

动画示例

②、表达式求值 （实现简单计算器功能）

栈常用于表达式求值，如中缀表达式转后缀表达式（逆波兰表达式）和逆波兰表达式求值。

先了解几个表达式的基本概念：
一般来说，数学表达式的表示方法主要有以下三种：

中缀表达式 (Infix Notation)
前缀表达式 (Prefix Notation) 又叫 波兰式 (Polish Notation)
后缀表达式 (Postfix Notation) 又叫 逆波兰式 (Reverse Polish Notation)

特点比较：

• 中缀表达式 是我们日常使用的表达方式，运算符位于操作数之间，直观但需要括号来明确优先级，计算机实现较复杂。
• 前缀表达式（波兰式）运算符位于操作数之前，不需要括号来确定优先级，适合树结构计算，计算机实现简单但不直观。
• 后缀表达式（逆波兰式）运算符位于操作数之后，同样不需要括号来确定优先级，适合栈结构计算，计算机实现简单但不直观。

我们可以利用栈实现计算器功能 (实际上就是中缀表达式转后缀表达式,再利用栈实现后缀表达式的计算)：

import java.util.Scanner;
import java.util.Stack;public class TestA {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while (true) {System.out.print("请输入一个中缀表达式 (输入 'exit' 退出): ");String infixExpression = scanner.nextLine();if (infixExpression.equalsIgnoreCase("exit")) {break; // 输入 'exit' 退出循环}try {String postfixExpression = infixToPostfix(infixExpression);System.out.println("后缀表达式: " + postfixExpression);double result = evaluatePostfix(postfixExpression);if (result % 1 == 0) { // 判断结果是否为整数System.out.println("计算结果: " + (int) result); // 整数结果去掉小数部分} else {System.out.println("计算结果: " + result);}} catch (Exception e) {System.out.println("表达式无效: " + e.getMessage());}}scanner.close();}// 中缀表达式转后缀表达式public static String infixToPostfix(String infix) {Stack<Character> stack = new Stack<>();StringBuilder postfix = new StringBuilder();for (int i = 0; i < infix.length(); i++) {char ch = infix.charAt(i);if (Character.isDigit(ch)) {// 处理多位数字和小数while (i < infix.length() && (Character.isDigit(infix.charAt(i)) || infix.charAt(i) == '.')) {postfix.append(infix.charAt(i++));}postfix.append(' ');i--; // 调整索引，以便下一次循环从正确位置开始} else if (ch == '(') {stack.push(ch);} else if (ch == ')') {// 将栈中的元素弹出直到遇到 '('while (!stack.isEmpty() && stack.peek() != '(') {postfix.append(stack.pop()).append(' ');}stack.pop(); // 弹出 '('} else if (isOperator(ch)) {// 当栈不为空且当前运算符的优先级小于等于栈顶运算符的优先级时，弹出栈顶运算符并加入后缀表达式while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(ch)) {postfix.append(stack.pop()).append(' ');}stack.push(ch); // 将当前运算符入栈}}// 将栈中剩余的运算符全部加入后缀表达式while (!stack.isEmpty()) {postfix.append(stack.pop()).append(' ');}return postfix.toString().trim(); // 返回后缀表达式}// 计算后缀表达式public static double evaluatePostfix(String postfix) {Stack<Double> stack = new Stack<>();for (int i = 0; i < postfix.length(); i++) {char ch = postfix.charAt(i);if (Character.isDigit(ch)) {// 处理多位数字和小数StringBuilder number = new StringBuilder();while (i < postfix.length() && (Character.isDigit(postfix.charAt(i)) || postfix.charAt(i) == '.')) {number.append(postfix.charAt(i++));}stack.push(Double.parseDouble(number.toString())); // 将数字入栈i--; // 调整索引，以便下一次循环从正确位置开始} else if (isOperator(ch)) {double b = stack.pop();double a = stack.pop();// 根据运算符进行计算并将结果入栈switch (ch) {case '+': stack.push(a + b); break;case '-': stack.push(a - b); break;case '*': stack.push(a * b); break;case '/': stack.push(a / b); break;}}}return stack.pop(); // 返回计算结果}// 判断是否是运算符public static boolean isOperator(char ch) {return ch == '+' || ch == '-' || ch == '*' || ch == '/';}// 返回运算符优先级public static int precedence(char ch) {switch (ch) {case '+':case '-': return 1;case '*':case '/': return 2;}return -1; // 如果不是运算符，则返回 -1}
}

输入：3*(1+2)
输出：

后缀表达式: 3 1 2 + *
计算结果: 9

栈在计算后缀表达式结果时的步骤：

• 1.创建一个空栈，用于存储操作数。
• 2.从左到右遍历后缀表达式的每个字符。
• 3.如果当前字符是操作数（数字），则将其转换为对应的数值，并压入栈中。
• 4.如果当前字符是运算符（+、-、*、/）：
        从栈中弹出两个操作数，分别记为 a 和 b（注意：b 是栈顶元素，a 是次顶元素）。
        根据当前运算符进行计算：根据后缀表达式的特性，b 是操作符 a 的右操作数，a 是左操作数。
• 5.将计算结果压入栈中。
• 6.遍历完后缀表达式后，栈中剩余的唯一元素即为最终的计算结果。

计算过程动画演示：

③、语法解析

括号匹配

import java.util.Stack;public class TestA {public static void main(String[] args) {String s = "{[(1234)]}";// 调用isValid方法并输出结果，应该输出true，因为输入的括号字符串是有效的System.out.println(isValid(s)); // 输出: true}// 判断括号字符串是否有效的方法public static boolean isValid(String s) {// 创建一个栈来存放左括号Stack<Character> stack = new Stack<>();// 遍历输入的字符串中的每一个字符for (char c : s.toCharArray()) {// 如果是左括号，则压入栈中if (c == '(' || c == '{' || c == '[') {stack.push(c);} else if (c == ')' || c == '}' || c == ']') { // 只处理右括号// 如果是右括号且栈为空，说明没有匹配的左括号，返回falseif (stack.isEmpty()) return false;// 弹出栈顶的左括号char top = stack.pop();// 判断栈顶的左括号和当前的右括号是否匹配，如果不匹配，返回falseif (c == ')' && top != '(' || c == '}' && top != '{' || c == ']' && top != '[') {return false;}}}// 如果栈为空，说明所有的括号都匹配，返回true；否则返回falsereturn stack.isEmpty();}
}

④、栈排序

用一个栈对数据进行排序

import java.util.*;public class TestA {public static void main(String[] args) {// 创建一个LinkedList并添加一些整数元素List<Integer> intCollection = new ArrayList<>();intCollection.add(5);intCollection.add(6);intCollection.add(3);intCollection.add(1);intCollection.add(2);intCollection.add(4);// 输出排序前的整数集合System.out.println("整数集合排序前: " + intCollection);// 调用sortCollection方法对集合进行排序Collection<Integer> sortedIntCollection = sortCollection(intCollection);// 输出排序后的整数集合System.out.println("整数集合排序后: " + sortedIntCollection);}// 对集合进行排序的方法，使用泛型并要求元素实现Comparable接口public static <T extends Comparable<T>> Collection<T> sortCollection(Collection<T> collection) {// 创建一个栈用于排序Stack<T> stack = new Stack<>();// 将集合中的元素压入栈中for (T element : collection) {stack.push(element);}// 创建一个临时栈用于辅助排序Stack<T> tempStack = new Stack<>();// 当输入栈不为空时进行排序while (!stack.isEmpty()) {// 弹出输入栈的栈顶元素T temp = stack.pop();// 将临时栈中所有大于temp的元素弹出并压入输入栈while (!tempStack.isEmpty() && tempStack.peek().compareTo(temp) < 0) {stack.push(tempStack.pop());}// 将temp压入临时栈tempStack.push(temp);}// 将临时栈中的元素全部弹出并存入一个新集合Collection<T> sortedCollection = new LinkedList<>();while (!tempStack.isEmpty()) {sortedCollection.add(tempStack.pop());}return sortedCollection;}
}

⑤、实现特殊算法

深度优先搜索（DFS）
二叉树的非递归前序遍历

回溯算法
例如求解迷宫问题、N皇后问题等。
算法类的暂时先不在这边篇文章内写了。后续会单独再写一些相关的内容。