栈
栈（Stack）是一种遵循后进先出（LIFO，Last In First Out） 原则的线性数据结构，仅允许在一端（栈顶）进行插入和删除操作。以下从核心特性、Java 实现、经典算法题三个方面详解：
栈的核心特性
- 操作受限：仅允许在栈顶执行插入（
push）和删除（pop），不支持随机访问。 - LIFO 原则：最后入栈的元素最先出栈（类似叠盘子，只能从最上面取放）。
- 实现方式：
- 基于数组（顺序栈）：内存连续，需预先指定容量，可能溢出。
- 基于链表（链式栈）：内存不连续，动态扩容，无溢出问题。
- 时间复杂度：
push、pop、peek（查看栈顶元素）均为 O(1)。
Java 栈的实现（数组版 + 链表版）
1. 顺序栈（基于数组）
public class ArrayStack<T> {
private T[] stack; // 存储元素的数组
private int top; // 栈顶指针（指向栈顶元素的索引）
private int size; // 栈的容量
// 初始化栈
@SuppressWarnings("unchecked")
public ArrayStack(int capacity) {
size = capacity;
stack = (T[]) new Object[capacity];
top = -1; // 初始栈空，指针为-1
}
// 入栈
public void push(T value) {
if (isFull()) {
throw new RuntimeException("栈已满");
}
stack[++top] = value; // 指针先加1，再赋值
}
// 出栈（返回栈顶元素并删除）
public T pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return stack[top--]; // 返回元素后指针减1
}
// 查看栈顶元素（不删除）
public T peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return stack[top];
}
// 判断栈空
public boolean isEmpty() {
return top == -1;
}
// 判断栈满
public boolean isFull() {
return top == size - 1;
}
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>(5);
stack.push(1);
stack.push(2);
System.out.println(stack.peek()); // 输出：2
System.out.println(stack.pop()); // 输出：2
System.out.println(stack.isEmpty()); // 输出：false
}
}
2. 链式栈（基于链表）
public class LinkedStack<T> {
// 节点类
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
}
}
private Node<T> top; // 栈顶节点（头节点）
private int size; // 栈的大小
// 入栈（在链表头部插入节点）
public void push(T value) {
Node<T> newNode = new Node<>(value);
newNode.next = top; // 新节点指向原栈顶
top = newNode; // 更新栈顶为新节点
size++;
}
// 出栈（删除并返回头节点）
public T pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
T data = top.data;
top = top.next; // 栈顶指针后移
size--;
return data;
}
// 查看栈顶元素
public T peek() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int size() {
return size;
}
public static void main(String[] args) {
LinkedStack<String> stack = new LinkedStack<>();
stack.push("a");
stack.push("b");
System.out.println(stack.peek()); // 输出：b
System.out.println(stack.pop()); // 输出：b
System.out.println(stack.size()); // 输出：1
}
}
3. Java 内置栈（java.util.Stack）
实际开发中可直接使用 JDK 提供的 Stack 类（继承自 Vector，基于数组实现），但更推荐 Deque 接口的 ArrayDeque（性能更优）：
import java.util.ArrayDeque;
import java.util.Deque;
public class BuiltInStack {
public static void main(String[] args) {
// 推荐使用Deque作为栈（比Stack更高效）
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 入栈
stack.push(2);
System.out.println(stack.peek()); // 查看栈顶：2
System.out.println(stack.pop()); // 出栈：2
System.out.println(stack.isEmpty()); // false
}
}
栈的经典算法题（附解析）
1. 有效的括号（LeetCode 20）
题目：判断字符串中的括号 ()[]{} 是否匹配（左右括号类型一致且嵌套正确）。
思路：左括号入栈，右括号与栈顶匹配，不匹配则无效。
public boolean isValid(String s) {
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 if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
// 栈空则所有左括号都匹配，否则有多余左括号
return stack.isEmpty();
}
2. 最小栈（LeetCode 155）
题目：设计一个栈，支持 push、pop、top，并能在常数时间内检索到最小元素。
思路：用辅助栈存储当前最小值，与主栈同步操作。
class MinStack {
private Deque<Integer> mainStack;
private Deque<Integer> minStack; // 辅助栈，存储对应主栈状态的最小值
public MinStack() {
mainStack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
minStack.push(Integer.MAX_VALUE); // 初始最小值为最大整数
}
public void push(int val) {
mainStack.push(val);
// 辅助栈压入当前最小值（val与栈顶最小值的较小者）
minStack.push(Math.min(val, minStack.peek()));
}
public void pop() {
mainStack.pop();
minStack.pop(); // 同步弹出
}
public int top() {
return mainStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
3. 每日温度（LeetCode 739）
题目：给定温度数组，返回每个元素需要等待几天才会有更高的温度（若无则为 0）。
思路：单调栈（存储索引），栈内元素对应温度递减，遇到更高温度时计算天数。
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Deque<Integer> stack = new ArrayDeque<>(); // 存储温度的索引
for (int i = 0; i < temperatures.length; i++) {
// 当前温度 > 栈顶温度：弹出并计算天数
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prevIndex = stack.pop();
res[prevIndex] = i - prevIndex;
}
stack.push(i); // 当前索引入栈
}
return res; // 未弹出的索引对应res为0（默认值）
}
4. 逆波兰表达式求值（LeetCode 150）
题目：计算逆波兰表达式（后缀表达式）的值，如 ["2","1","+","3","*"] 结果为 9。
思路：数字入栈，遇到运算符则弹出两个数字计算，结果入栈。
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
if ("+".equals(token)) {
stack.push(stack.pop() + stack.pop());
} else if ("-".equals(token)) {
int b = stack.pop(), a = stack.pop(); // 注意顺序：a - b
stack.push(a - b);
} else if ("*".equals(token)) {
stack.push(stack.pop() * stack.pop());
} else if ("/".equals(token)) {
int b = stack.pop(), a = stack.pop(); // a / b
stack.push(a / b);
} else {
stack.push(Integer.parseInt(token)); // 数字入栈
}
}
return stack.pop();
}
5. 柱状图中最大的矩形（LeetCode 84）
题目：给定柱状图高度数组，求能勾勒出的最大矩形面积。
思路：单调栈（存储索引），找到每个柱子左右第一个更矮的柱子，计算以当前柱子为高的最大宽度。
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n]; // 左边界：第一个比当前矮的索引
int[] right = new int[n]; // 右边界：第一个比当前矮的索引
Deque<Integer> stack = new ArrayDeque<>();
// 计算左边界
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
stack.clear(); // 清空栈用于计算右边界
// 计算右边界
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
right[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
// 计算最大面积：height[i] * (right[i] - left[i] - 1)
int maxArea = 0;
for (int i = 0; i < n; i++) {
maxArea = Math.max(maxArea, heights[i] * (right[i] - left[i] - 1));
}
return maxArea;
}
总结
栈的核心是 LIFO 原则，其特性使其在以下场景中不可或缺：
- 括号匹配、表达式求值（语法解析）；
- 单调栈优化（解决 “找左右第一个更大 / 更小元素” 类问题）；
- 深度优先搜索（DFS）、回溯算法（递归本质是栈）。
掌握栈的实现原理和单调栈技巧，能高效解决各类线性结构的算法题。实际开发中，优先使用 ArrayDeque 作为栈（性能优于 Stack），避免线程安全的 Vector 带来的开销。
资料
数据结构之单调栈
单调栈解题模板
Leetcode 单调栈问题总结
[动画：什么是单调栈？](https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486327&idx=2&sn=12898a14bb5eca6508c9edb785b79d18&chksm=fa0e64f6cd79ede0cd08cf2059bc848b879918c2507b80d785409b49a9dbb6909b64dd146ff5&scene=21#wechat_redirect# 栈)
数据结构之单调栈
单调栈解题模板