一文吃透栈（Stack）：从底层原理到经典算法实战

一、什么是栈？

栈（Stack）:是一种后进先出（LIFO，Last In First Out）的数据结构。

栈的核心特性

• 只能在一端操作（称为栈顶 top）

• 基本操作：

  • 入栈（push）

  • 出栈（pop）

  • 查看栈顶（peek）

二、栈的逻辑结构 vs 物理结构

逻辑结构：

栈顶 ┌───┐ │ 3 │ ├───┤ │ 2 │ ├───┤ │ 1 │ └───┘ 栈底

物理实现方式：

1. 数组实现（顺序栈）

2. 链表实现（链式栈）

三、手写一个顺序栈（数组实现）

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 出栈

八、栈常见面试问题总结

九、总结一句话

栈的本质：延迟处理 + 最近优先

掌握栈，你会突然发现：

• 递归不再神秘

• 表达式计算有迹可循

• 很多“看起来复杂”的问题，本质只是一个栈