一、什么是栈？
栈（Stack）:是一种后进先出（LIFO，Last In First Out）的数据结构。
栈的核心特性
只能在一端操作（称为栈顶 top）
基本操作：
入栈（push）
出栈（pop）
查看栈顶（peek）
二、栈的逻辑结构 vs 物理结构
逻辑结构：
栈顶 ┌───┐ │ 3 │ ├───┤ │ 2 │ ├───┤ │ 1 │ └───┘ 栈底物理实现方式：
数组实现（顺序栈）
链表实现（链式栈）
三、手写一个顺序栈（数组实现）
1. 栈的基本结构
public class ArrayStack { private int[] data; // 存放元素 private int top; // 栈顶指针 private int capacity; public ArrayStack(int capacity) { this.capacity = capacity; data = new int[capacity]; top = -1; // 栈空 } }2. 入栈（push）
public void push(int value) { if (top == capacity - 1) { throw new RuntimeException("栈满，无法入栈"); } data[++top] = value; }关键点：
top == capacity - 1→ 栈满先
++top再赋值
3. 出栈（pop）
public int pop() { if (top == -1) { throw new RuntimeException("栈空，无法出栈"); } return data[top--]; }关键点：
先取值，再
top--
4. 查看栈顶（peek）
public int peek() { if (top == -1) { throw new RuntimeException("栈空"); } return data[top]; }5. 测试代码
public static void main(String[] args) { ArrayStack stack = new ArrayStack(5); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.pop()); // 3 System.out.println(stack.peek()); // 2 }四、链式栈（链表实现）
优势：不需要扩容，不受数组大小限制
1. 节点定义
class Node { int value; Node next; Node(int value) { this.value = value; } }2. 栈结构
public class LinkedStack { private Node top; public LinkedStack() { top = null; } }3. 入栈（头插法）
public void push(int value) { Node node = new Node(value); node.next = top; top = node; }4. 出栈
public int pop() { if (top == null) { throw new RuntimeException("栈空"); } int value = top.value; top = top.next; return value; }五、栈的经典应用 ①：括号匹配
问题描述
输入： "{[()]}" 输出： true解题思路
左括号 → 入栈
右括号 → 弹栈匹配
代码实现
public static boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { if (stack.isEmpty()) return false; char top = stack.pop(); if (c == ')' && top != '(') return false; if (c == ']' && top != '[') return false; if (c == '}' && top != '{') return false; } } return stack.isEmpty(); }六、栈的经典应用 ②：表达式求值（逆波兰）
示例
输入：["2","1","+","3","*"] 输出：9代码实现
public static int evalRPN(String[] tokens) { Deque<Integer> stack = new ArrayDeque<>(); for (String token : tokens) { if ("+-*/".contains(token)) { int b = stack.pop(); int a = stack.pop(); switch (token) { case "+": stack.push(a + b); break; case "-": stack.push(a - b); break; case "*": stack.push(a * b); break; case "/": stack.push(a / b); break; } } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); }七、栈在系统层面的真实应用
1. JVM 虚拟机栈
每个线程一个栈
栈帧包含：
局部变量表
操作数栈
返回地址
递归本质 = 不断入栈
2. 函数调用过程
void a() { b(); } void b() { c(); }调用顺序：
a 入栈 b 入栈 c 入栈 c 出栈 b 出栈 a 出栈八、栈常见面试问题总结
| 题型 | 关键词 |
|---|---|
| 括号匹配 | 栈 |
| 单调栈 | 下一个更大元素 |
| 表达式求值 | 操作数栈 |
| DFS / 回溯 | 系统栈 |
| 中序 → 后序 | 栈 |
九、总结一句话
栈的本质：延迟处理 + 最近优先
掌握栈，你会突然发现：
递归不再神秘
表达式计算有迹可循
很多“看起来复杂”的问题，本质只是一个栈
