栈数据结构深度解析:核心原理、六大应用场景与Java代码实现

一、栈的基本概念

栈是一种后进先出（LIFO, Last In First Out）的线性数据结构，意味着最后加入的元素会首先被移除。仅允许在同一端（栈顶）进行插入（push）和删除（pop）操作。

· 核心操作：

• push：将元素压入栈顶。
• pop：弹出栈顶元素。
• peek：查看栈顶元素（不删除）。
• isEmpty：判断栈是否为空。
• size：获取栈中元素个数。

二、栈的应用场景

1. 函数调用栈

程序执行时，每次函数调用会将返回地址、参数、局部变量压入栈，函数执行完毕后，栈顶的元素被弹出，程序恢复到之前的状态继续执行。

2. 括号匹配

编写代码或处理文本时，经常需要检查括号是否正确配对。每当遇到左括号就将其压入栈中，而遇到右括号时，则检查栈顶是否有对应的左括号。如果整个过程结束后栈为空，则说明所有括号都正确配对。

3. 浏览器前进/后退

用两个栈分别存储“已访问”和“可前进”的页面，后退时从“已访问”栈弹出并压入“可前进”栈。

4. 撤销操作（Undo）

许多应用程序如文本编辑器、图形软件等提供的“撤销”功能，就是通过记录用户操作的历史压入栈中。用户每次执行新操作，该操作就被添加到栈顶；执行撤销时，从栈顶弹出最近的操作执行反向操作。

5. 表达式求值

使用两个栈分别存储运算符和操作数，按优先级计算（如中缀转后缀表达式）

6. 深度优先搜索（DFS）

用栈保存待访问节点，按深度优先顺序遍历图或树。

三、栈的实现思路

1. 基于数组实现

· 核心设计：

• 数组 elements 存储元素，top 指针指向栈顶索引。
• 初始化时 top = -1，表示空栈。
• push 时 top++，若数组满则扩容。
• pop 时返回 elements[top] 并 top--。

· 优缺点：

• 优点：内存连续，访问高效。
• 缺点：需预先分配空间，扩容成本高。

2. 基于链表实现

· 核心设计：

• 链表节点 Node 包含数据域和 next 指针。
• head 指针指向栈顶节点。
• push 时在链表头部插入新节点。
• pop 时删除头节点并返回数据。

· 优缺点：

• 优点：动态扩容，无需预设大小。
• 缺点：内存非连续，访问略慢。

四、Java代码实现

1. 基于数组的动态扩容栈

public class ArrayStack {

 ? ?// 栈顶指针
 ? ?private int top;
 ? ?// 数组 elements 存储元素
 ? ?private Object[] elements;
 ? ?// 默认容量
 ? ?private static final int DEFAULT_CAPACITY = 10;

 ? ?public ArrayStack() {
 ? ? ? ?elements = new Object[DEFAULT_CAPACITY];
 ? ? ? ?top = -1;
 ?  }
?
 ? ?/**
 ? ? * 向栈中压入一个新元素
 ? ? * 如果栈已满，则进行扩容操作
 ? ? *
 ? ? * @param data 要压入栈的新元素，类型为泛型T
 ? ? */
 ? ?public void push(T data) {
 ? ? ? ?// 检查栈是否已满
 ? ? ? ?if(top == elements.length - 1) {
 ? ? ? ? ? ?resize();
 ? ? ?  }
 ? ? ? ?// 将新元素压入栈中，注意先递增top再赋值，以确保新元素位于栈顶
 ? ? ? ?elements[++top] = data;
 ?  }
?
 ? ?/**
 ? ? * 从栈中弹出一个元素
 ? ? *
 ? ? * 此方法用于移除并返回栈顶的元素如果栈当前为空，则抛出运行时异常
 ? ? *
 ? ? * @return T 返回栈顶的元素
 ? ? * @throws RuntimeException 如果栈为空时调用此方法，将抛出此异常
 ? ? */
 ? ?public T pop() {
 ? ? ? ?// 检查栈是否为空，如果为空则抛出异常
 ? ? ? ?if (isEmpty()) {
 ? ? ? ? ? ?throw new RuntimeException("栈为空");
 ? ? ?  }
 ? ? ? ?// 返回栈顶元素，并将栈顶指针下移
 ? ? ? ?return (T) elements[top--];
 ?  }
?
 ? ?/**
 ? ? * 查看栈顶元素
 ? ? *
 ? ? * 此方法用于获取当前栈顶的元素，而不移除它
 ? ? * 如果栈为空，则抛出运行时异常
 ? ? *
 ? ? * @return 栈顶的元素
 ? ? * @throws RuntimeException 如果栈为空时调用此方法
 ? ? */
 ? ?public T peek() {
 ? ? ? ?if (isEmpty()) {
 ? ? ? ? ? ?throw new RuntimeException("栈为空");
 ? ? ?  }
 ? ? ? ?return (T) elements[top];
 ?  }
?
 ? ?/**
 ? ? * 列出栈中的所有元素
 ? ? *
 ? ? * 此方法首先检查栈是否为空如果为空，则打印消息并返回
 ? ? * 如果栈不为空，则遍历栈中的所有元素，从顶部开始，逐个向下打印每个元素的值
 ? ? * 这种遍历方式反映了栈后进先出的特点
 ? ? */
 ? ?public void list() {
 ? ? ? ?// 检查栈是否为空
 ? ? ? ?if (isEmpty()) {
 ? ? ? ? ? ?System.out.println("栈为空");
 ? ? ? ? ? ?return;
 ? ? ?  }
 ? ? ? ?// 遍历栈中的元素，从顶部开始
 ? ? ? ?for (int i = top; i >= 0 ; i--) {
 ? ? ? ? ? ?// 打印每个元素的位置和值
 ? ? ? ? ? ?System.out.printf("elements[%d] = %s\n", i, elements[i]);
 ? ? ?  }
 ?  }
?
 ? ?/**
 ? ? * 获取栈的元素数量
 ? ? *
 ? ? * 此方法返回栈中元素的数量通过返回top变量的值加1来实现
 ? ? * 这是因为top变量指向的是栈顶元素的位置，而栈中元素的数量比栈顶位置多1
 ? ? *
 ? ? * @return 栈中元素的数量
 ? ? */
 ? ?public int size() {
 ? ? ? ?return top + 1;
 ?  }
?
 ? ?/**
 ? ? * 扩容数组以适应更多的元素
 ? ? * 当数组达到其容量限制时，调用此方法将其容量扩大一倍
 ? ? * 这样做是为了确保数组可以继续存储更多的元素，而不需要频繁地进行重新分配
 ? ? */
 ? ?private void resize() {
 ? ? ? ?// 创建一个新的数组，长度为原数组的两倍
 ? ? ? ?Object[] newArray = new Object[elements.length * 2];
 ? ? ? ?// 将原数组中的所有元素复制到新数组中
 ? ? ? ?System.arraycopy(elements, 0, newArray, 0, elements.length);
 ? ? ? ?// 将原数组引用指向新数组，以便后续操作可以在扩容后的数组上进行
 ? ? ? ?elements = newArray;
 ?  }
?
 ? ?/**
 ? ? * 判断栈是否为空
 ? ? * @return 如果栈为空，则返回true；否则返回false
 ? ? */
 ? ?public boolean isEmpty() {
 ? ? ? ?return top == -1;
 ?  }
}

2. 基于链表的栈

public class LinkedStack {
?
 ? ?private static class Node {
 ? ? ? ?private T data;
 ? ? ? ?Node next;
 ? ? ? ?Node(T data) {
 ? ? ? ? ? ?this.data = data;
 ? ? ?  }
 ?  }
?
 ? ?// 栈顶节点
 ? ?private Node head;
 ? ?// 栈的大小
 ? ?private int size;
?
 ? ?/**
 ? ? * 向栈中压入一个新元素（头插法）
 ? ? *
 ? ? * @param data 要压入栈中的元素，类型为泛型T，表示该栈可以存储任意类型的数据
 ? ? */
 ? ?public void push(T data) {
 ? ? ? ?// 创建一个新的节点，包含要压入栈中的数据
 ? ? ? ?Node newNode = new Node<>(data);
 ? ? ? ?// 将新节点的next引用指向当前的栈顶节点，以保持栈的特性
 ? ? ? ?newNode.next = head;
 ? ? ? ?// 更新栈顶指针，将新节点设置为栈顶节点
 ? ? ? ?head = newNode;
 ? ? ? ?// 增加栈的大小计数，以跟踪栈中元素的数量
 ? ? ? ?size++;
 ?  }
?
 ? ?/**
 ? ? * 从栈中弹出一个元素
 ? ? *
 ? ? * 此方法首先检查栈是否为空如果栈为空，则抛出运行时异常，提示用户栈为空
 ? ? * 如果栈不为空，则获取当前栈顶元素的数据，更新栈顶指针（head）为下一个元素，
 ? ? * 并减少栈的大小最后，返回弹出的元素数据
 ? ? *
 ? ? * @return T 返回弹出的元素数据，类型为T
 ? ? * @throws RuntimeException 如果栈为空时调用此方法，抛出运行时异常
 ? ? */
 ? ?public T pop() {
 ? ? ? ?// 检查栈是否为空，如果为空则抛出异常
 ? ? ? ?if (isEmpty()) {
 ? ? ? ? ? ?throw new RuntimeException("栈为空");
 ? ? ?  }
 ? ? ? ?// 获取当前栈顶元素的数据
 ? ? ? ?T data = head.data;
 ? ? ? ?// 更新栈顶指针为下一个元素
 ? ? ? ?head = head.next;
 ? ? ? ?// 减少栈的大小
 ? ? ? ?size--;
 ? ? ? ?// 返回弹出的元素数据
 ? ? ? ?return data;
 ?  }
?
 ? ?/**
 ? ? * 打印栈中的所有元素
 ? ? *
 ? ? * 此方法首先检查栈是否为空如果为空，则输出提示信息"栈为空"并返回
 ? ? * 如果栈不为空，则遍历栈中的所有节点，并打印每个节点的数据
 ? ? */
 ? ?public void list() {
 ? ? ? ?// 检查栈是否为空
 ? ? ? ?if (isEmpty()) {
 ? ? ? ? ? ?System.out.println("栈为空");
 ? ? ? ? ? ?return;
 ? ? ?  }
 ? ? ? ?// 遍历栈中的每个节点，并打印节点的数据
 ? ? ? ?for (Node node = head; node != null; node = node.next) {
 ? ? ? ? ? ?System.out.println(node.data);
 ? ? ?  }
 ?  }
 ? ?/**
 ? ? * 查看栈顶元素
 ? ? *
 ? ? * 此方法用于返回当前栈的顶部元素而不移除它，如果栈为空，则抛出运行时异常
 ? ? *
 ? ? * @return 返回栈顶的元素
 ? ? * @throws RuntimeException 如果栈为空时调用此方法，将抛出此异常提示用户栈为空，无法获取元素
 ? ? */
 ? ?public T peek() {
 ? ? ? ?if (isEmpty()) {
 ? ? ? ? ? ?throw new RuntimeException("栈为空");
 ? ? ?  }
 ? ? ? ?return head.data;
 ?  }
?
 ? ?/**
 ? ? * 获取集合中的元素数量
 ? ? *
 ? ? * @return 集合的元素数量
 ? ? */
 ? ?public int size() {
 ? ? ? ?return size;
 ?  }
?
 ? ?/**
 ? ? * 判断栈是否为空
 ? ? *
 ? ? * 此方法用于检查栈是否为空，通过检查head属性是否为null来实现
 ? ? * 如果head为null，则表示栈为空，返回true；否则，返回false
 ? ? *
 ? ? * @return 如果栈为空，则返回true；否则返回false
 ? ? */
 ? ?public boolean isEmpty() {
 ? ? ? ?return head == null;
 ?  }
}

五、总结

· 栈的核心特性：后进先出，操作受限的线性表。

· 实现选择：高频访问用数组，动态大小用链表。

· 应用场景：与“最近相关性”相关的问题（如括号匹配、撤销操作）优先考虑栈。