Java基础（栈）
·
Java 栈（Stack）
目录
一、栈的核心基础概念
1.1 什么是栈？
栈（Stack）是一种操作受限的线性数据结构，核心特性是后进先出（LIFO，Last In First Out），也就是最后存入的元素，会被最先取出。
我们可以用生活中最常见的场景类比：
- 叠盘子：我们只能从最顶部放盘子，也只能从最顶部取盘子，最后放的盘子永远第一个被拿走
- 枪械弹夹：最后压入的子弹，会被第一个射出
栈的操作被严格限制在栈顶（Top） 一端，栈底（Bottom）是固定不动的，无法直接操作栈底和中间的元素。
1.2 栈的5个核心操作
所有栈的实现都围绕这5个核心能力，也是面试必须记住的基础：
| 操作方法 | 核心作用 | 异常情况 |
|---|---|---|
push(E item) |
入栈：将元素压入栈顶 | 栈空间满时（固定容量栈）抛出异常 |
pop() |
出栈：删除并返回栈顶元素 | 空栈调用时抛出 EmptyStackException |
peek() |
查看栈顶：仅返回栈顶元素，不删除 | 空栈调用时抛出 EmptyStackException |
isEmpty() |
判断栈是否为空，返回布尔值 | 无异常 |
size() |
获取栈中元素的总个数 | 无异常 |
1.3 栈的核心应用场景
栈的后进先出特性，让它在程序开发中有着不可替代的作用，核心应用包括：
- JVM 虚拟机栈：Java 方法调用的底层就是基于栈实现，每个方法执行都会创建一个栈帧入栈，方法执行完毕栈帧出栈
- 括号匹配校验：LeetCode 高频题，判断
()[]{}格式是否合法 - 表达式求值：比如逆波兰表达式（后缀表达式）的计算
- 浏览器的后退功能、编辑器的撤销（Ctrl+Z）功能
- 二叉树的前/中/后序遍历、回溯算法的底层实现
二、Java 中栈的两种主流实现方式
Java 中栈的实现分为两类，日常开发优先使用第二种，面试两种都必须掌握。
2.1 传统实现：java.util.Stack 类
Stack 是 JDK 早期提供的栈实现，继承自 Vector 类，是线程安全的（所有方法都加了 synchronized 同步锁）。
完整代码示例
import java.util.Stack;
/**
* Stack 类基础使用演示
*/
public class StackBasicDemo {
public static void main(String[] args) {
// 1. 创建一个存储整数的栈
Stack<Integer> stack = new Stack<>();
// 2. 入栈操作 push()
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("入栈后的栈内容：" + stack); // 输出：[10, 20, 30]
// 3. 查看栈顶元素 peek() - 不删除元素
int topElement = stack.peek();
System.out.println("当前栈顶元素：" + topElement); // 输出：30
System.out.println("peek后栈内容：" + stack); // 输出：[10, 20, 30]
// 4. 出栈操作 pop() - 删除并返回栈顶元素
int popElement = stack.pop();
System.out.println("出栈的元素：" + popElement); // 输出：30
System.out.println("pop后栈内容：" + stack); // 输出：[10, 20]
// 5. 栈基础信息获取
System.out.println("栈是否为空：" + stack.isEmpty()); // 输出：false
System.out.println("栈中元素个数：" + stack.size()); // 输出：2
// 6. 循环清空栈（标准写法，避免空栈异常）
while (!stack.isEmpty()) {
System.out.println("依次出栈元素：" + stack.pop());
}
System.out.println("清空后栈是否为空：" + stack.isEmpty()); // 输出：true
}
}
Stack 类的致命缺点
JDK 官方文档明确说明：不推荐使用 Stack 类，优先使用 Deque 接口，原因如下：
- 性能差：继承自
Vector，所有方法都加了同步锁，单线程场景下有不必要的性能开销 - 设计缺陷：继承了
Vector，可以通过get(index)、set(index,value)直接操作栈中任意位置的元素，完全破坏了栈“只能操作栈顶”的封装特性 - 扩展性差：基于数组实现，扩容时需要数组拷贝，有额外的性能开销
2.2 官方推荐实现：Deque 接口 + ArrayDeque 实现
Deque 是双端队列接口，支持在两端同时进行插入、删除操作，完全可以模拟栈的“仅单端操作”特性，是 JDK 官方推荐的栈实现方案。
方法对应关系
Deque 中模拟栈的方法和 Stack 类完全兼容，无需修改代码习惯：
| 栈操作 | Deque 对应方法 | 作用 |
|---|---|---|
| 入栈 | push(E e) |
元素压入双端队列的头部（栈顶） |
| 出栈 | pop() |
从双端队列的头部删除并返回元素 |
| 查看栈顶 | peek() |
返回双端队列头部元素，不删除 |
| 判空 | isEmpty() |
同 Stack 类 |
| 获取大小 | size() |
同 Stack 类 |
完整代码示例
import java.util.ArrayDeque;
import java.util.Deque;
/**
* 官方推荐：Deque 实现栈的基础演示
*/
public class DequeStackDemo {
public static void main(String[] args) {
// 核心写法：用 Deque 接口声明，ArrayDeque 实现类实例化
Deque<String> stack = new ArrayDeque<>();
// 1. 入栈操作
stack.push("Java");
stack.push("Spring");
stack.push("MyBatis");
System.out.println("入栈后的栈内容：" + stack); // 输出：[MyBatis, Spring, Java]
// 2. 查看栈顶元素
System.out.println("栈顶元素：" + stack.peek()); // 输出：MyBatis
// 3. 出栈操作
System.out.println("出栈元素：" + stack.pop()); // 输出：MyBatis
System.out.println("出栈后栈内容：" + stack); // 输出：[Spring, Java]
// 4. 基础信息
System.out.println("栈是否为空：" + stack.isEmpty()); // 输出：false
System.out.println("栈元素个数：" + stack.size()); // 输出：2
// 标准循环遍历出栈
while (!stack.isEmpty()) {
System.out.println("依次出栈：" + stack.pop());
}
}
}
为什么推荐这种写法？
- 性能更优：
ArrayDeque基于数组实现，没有synchronized同步锁，单线程场景下性能远超 Stack 类 - 设计严谨：接口隔离，仅暴露栈相关的操作，不会破坏栈的封装特性
- 扩展性强：支持动态扩容，底层数组的扩容效率更高，同时也有
LinkedList链表实现可选 - 通用性强：Deque 接口同时支持栈和队列两种数据结构，学习成本低，适用场景更广
补充说明：
LinkedList也实现了 Deque 接口，也能用来实现栈，但优先使用 ArrayDeque。原因是 ArrayDeque 基于数组实现，缓存友好，访问效率更高；LinkedList 基于链表实现，每个元素都有额外的节点对象开销，内存占用更高。
三、手写实现栈：吃透底层原理
面试中经常会要求“手写一个栈”，核心是基于数组或链表实现，这里我们实现基于数组的泛型顺序栈，覆盖所有核心操作，同时支持动态扩容，帮你彻底理解栈的底层逻辑。
完整手写栈代码
/**
* 手写基于数组的泛型栈，支持动态扩容
* @param <E> 栈中存储的元素类型
*/
public class MyArrayStack<E> {
// 底层存储元素的数组
private Object[] elementData;
// 栈中当前元素个数
private int size;
// 栈的默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 栈的最大容量
private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
// 无参构造：使用默认容量初始化
public MyArrayStack() {
elementData = new Object[DEFAULT_CAPACITY];
size = 0;
}
// 有参构造：指定初始容量
public MyArrayStack(int initCapacity) {
if (initCapacity < 0) {
throw new IllegalArgumentException("初始容量不能为负数：" + initCapacity);
}
elementData = new Object[initCapacity];
size = 0;
}
/**
* 入栈操作
* @param item 要压入栈的元素
*/
public void push(E item) {
// 先判断是否需要扩容
ensureCapacity(size + 1);
// 元素放入栈顶，size+1
elementData[size++] = item;
}
/**
* 出栈操作：删除并返回栈顶元素
* @return 栈顶元素
*/
@SuppressWarnings("unchecked")
public E pop() {
// 空栈校验
if (size == 0) {
throw new EmptyStackException();
}
// 栈顶元素下标为 size-1
int index = --size;
E oldValue = (E) elementData[index];
// 置空，帮助GC回收，避免内存泄漏
elementData[index] = null;
return oldValue;
}
/**
* 查看栈顶元素：不删除
* @return 栈顶元素
*/
@SuppressWarnings("unchecked")
public E peek() {
if (size == 0) {
throw new EmptyStackException();
}
return (E) elementData[size - 1];
}
/**
* 判断栈是否为空
* @return 空返回true，非空返回false
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 获取栈中元素个数
* @return 元素个数
*/
public int size() {
return size;
}
/**
* 数组扩容校验：容量不足时自动扩容
* @param minCapacity 所需最小容量
*/
private void ensureCapacity(int minCapacity) {
// 如果当前数组容量不足，需要扩容
if (minCapacity > elementData.length) {
grow(minCapacity);
}
}
/**
* 核心扩容方法
* @param minCapacity 所需最小容量
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 默认扩容为原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 处理1.5倍扩容后仍不足的情况
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
// 处理超过最大容量的情况
if (newCapacity > MAX_CAPACITY) {
newCapacity = minCapacity > MAX_CAPACITY ? Integer.MAX_VALUE : MAX_CAPACITY;
}
// 数组拷贝，将原数组内容复制到新扩容的数组中
Object[] newElementData = new Object[newCapacity];
System.arraycopy(elementData, 0, newElementData, 0, size);
elementData = newElementData;
}
// 自定义空栈异常
static class EmptyStackException extends RuntimeException {
public EmptyStackException() {
super("栈为空，无法执行该操作");
}
}
// 测试方法
public static void main(String[] args) {
MyArrayStack<Integer> stack = new MyArrayStack<>();
// 入栈
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("栈大小：" + stack.size()); // 输出：3
System.out.println("栈顶元素：" + stack.peek()); // 输出：3
// 出栈
System.out.println("出栈元素：" + stack.pop()); // 输出：3
System.out.println("出栈后栈大小：" + stack.size()); // 输出：2
// 循环出栈
while (!stack.isEmpty()) {
System.out.println("依次出栈：" + stack.pop());
}
// 测试空栈异常
try {
stack.pop();
} catch (EmptyStackException e) {
System.out.println("异常捕获：" + e.getMessage());
}
}
}
四、栈的经典实战案例（面试高频）
4.1 有效的括号（LeetCode 20，面试必考题）
题目描述
给定一个只包括 (、)、{、}、[、] 的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 每个右括号都有一个对应的相同类型的左括号
解题思路
- 遇到左括号，就将对应的右括号压入栈中
- 遇到右括号，判断是否和栈顶元素一致，一致则出栈，不一致直接返回false
- 遍历结束后，栈必须为空，否则说明有未闭合的左括号
完整代码实现
import java.util.ArrayDeque;
import java.util.Deque;
public class ValidParentheses {
public boolean isValid(String s) {
// 字符串长度为奇数，直接不可能有效
if (s.length() % 2 != 0) {
return false;
}
Deque<Character> stack = new ArrayDeque<>();
// 遍历字符串中的每个字符
for (char c : s.toCharArray()) {
// 遇到左括号，压入对应的右括号
if (c == '(') {
stack.push(')');
} else if (c == '[') {
stack.push(']');
} else if (c == '{') {
stack.push('}');
} else {
// 遇到右括号：栈为空 或 与栈顶元素不一致，直接返回false
if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
}
// 遍历结束，栈必须为空才是有效字符串
return stack.isEmpty();
}
// 测试
public static void main(String[] args) {
ValidParentheses solution = new ValidParentheses();
System.out.println(solution.isValid("()[]{}")); // 输出：true
System.out.println(solution.isValid("(]")); // 输出：false
System.out.println(solution.isValid("({[]})")); // 输出：true
}
}
4.2 逆波兰表达式求值（LeetCode 150）
逆波兰表达式也叫后缀表达式，运算符写在操作数之后，是栈的经典应用场景，比如 ["2","1","+","3","*"] 对应的计算公式是 ((2+1)*3)=9。
完整代码实现
import java.util.ArrayDeque;
import java.util.Deque;
public class EvalRPN {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
// 遇到运算符，取出栈顶两个元素进行计算
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
// 注意：先出栈的是第二个操作数
int num2 = stack.pop();
int num1 = stack.pop();
int result = switch (token) {
case "+" -> num1 + num2;
case "-" -> num1 - num2;
case "*" -> num1 * num2;
case "/" -> num1 / num2;
default -> 0;
};
// 计算结果重新入栈
stack.push(result);
} else {
// 遇到数字，直接入栈
stack.push(Integer.parseInt(token));
}
}
// 最终栈中剩下的唯一元素就是计算结果
return stack.pop();
}
public static void main(String[] args) {
EvalRPN solution = new EvalRPN();
String[] tokens = {"2","1","+","3","*"};
System.out.println(solution.evalRPN(tokens)); // 输出：9
}
}
五、面试高频考点&避坑指南
5.1 面试高频考点
- 栈和队列的核心区别是什么？
- 栈：后进先出（LIFO），仅支持栈顶一端的插入和删除操作
- 队列：先进先出（FIFO），支持队尾插入、队头删除，两端操作
- 为什么 Java 官方不推荐使用 Stack 类？
- 继承自 Vector，同步锁带来不必要的性能开销
- 设计缺陷，继承了 Vector 的公共方法，可以直接操作中间元素，破坏栈的封装性
- 推荐使用 Deque 接口的 ArrayDeque 实现，性能更好、设计更严谨
- 栈的入栈、出栈操作时间复杂度是多少？
- 最优/平均时间复杂度：O(1)，仅操作栈顶元素，无遍历
- 最坏时间复杂度：O(n)，基于数组的栈扩容时，需要进行数组拷贝，时间复杂度为O(n)
- 手写栈的两种实现方式（数组/链表）
- 数组实现：顺序栈，需要处理扩容，缓存友好，访问效率高
- 链表实现：链式栈，无需扩容，内存利用率高，但是有节点额外开销
- JVM 中的栈内存和数据结构中的栈有什么关系？
- JVM 虚拟机栈的底层逻辑完全遵循数据结构栈的“后进先出”特性
- 每个方法执行时，都会创建一个栈帧压入虚拟机栈，方法执行完毕后栈帧出栈，和数据结构栈的操作完全一致
5.2 新手必看避坑指南
- 空栈操作异常：调用
pop()、peek()方法前，必须先用isEmpty()判断栈是否为空，否则会抛出空栈异常 - 破坏栈的封装性：使用 Stack 类时，不要调用父类 Vector 的
get()、set()、remove()方法，会完全破坏栈的结构特性 - 混淆栈的进出顺序：栈是后进先出，出栈顺序和入栈顺序相反，做算法题时一定要先画图理清顺序，避免逻辑错误
- 手写栈的内存泄漏：基于数组实现栈时，出栈操作要将数组对应位置置空，帮助 GC 回收对象，避免内存泄漏
六、总结
本文从基础原理到代码实现，再到面试实战，全面讲解了 Java 中的栈，核心内容可以用3句话总结：
- 栈的核心特性是后进先出（LIFO），所有操作都限制在栈顶，核心操作是
push、pop、peek、isEmpty、size - Java 开发中优先使用 Deque 接口 + ArrayDeque 实现栈，避免使用老旧的 Stack 类
- 栈的核心价值在于处理“有先后顺序、需要回溯”的场景，是 JVM 方法调用、括号匹配、表达式求值、回溯算法等场景的底层核心
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
11
0- 0
已为社区贡献23条内容
所有评论(0)