写这篇文章之前我先说个真实感受。我在面试候选人的时候只要问一句“栈和队列有什么区别”十个人里至少有五个能答上“先进后出、先进先出”但你再追问一句“栈这玩意儿在JVM里是怎么工作的IDE里那个调用栈到底在看什么”能答上来的人就少了一大半。不是大家不懂是很多人把栈当成了一个“考试名词”背完定义就扔了根本没把它跟真实的编程场景挂上钩。这篇文章不打算只给你贴一份课本上的伪代码而是站在“一个真正写过代码、调过崩溃、被递归爆栈折磨过的人”的角度把栈这个数据结构从原理讲到源码从数组版讲到链表版从C语言版讲到Java版再顺手把面试最爱考的那几道栈相关的题也拆了。内容偏实操建议你手里放着一个IDE看到代码片段就自己动手敲一遍光看不写永远学不会数据结构。1. 先搞清楚栈是什么后进先出这四个字背后的设计逻辑1.1 从一摞盘子说起栈的直觉模型栈Stack本质上是一种线性表但它比普通线性表多了一个很严格的限制所有的插入和删除操作都只能发生在表的“同一端”这一端叫栈顶Top另一端叫栈底Bottom。操作方式只有两种往栈顶压入一个元素Push以及从栈顶弹出一个元素Pop。后放进去的元素最先被取出来这就是所谓的“后进先出”LIFOLast In First Out。如果你端起一摞盘子你永远只能先把最上面那个盘子拿走想拿最底下的必须把上面的全搬走。往这摞盘子上再放一个新盘子它也一定是在最顶端。栈这个抽象模型本质上就是在模拟这种“只从一头进出”的物理直觉。我第一次学栈的时候觉得这玩意儿太简单了不就是一个“限制版的数组”吗后来代码写多了才意识到恰恰是这个“限制”让它变成了计算机世界里最优雅、最高效的结构之一。为什么这么说因为栈的所有操作都发生在栈顶所以无论栈里现在有多少个元素Push和Pop的时间复杂度都是O(1)跟数据规模无关。这是很多其他数据结构做不到的特性。1.2 栈的核心操作与设计约定不管用哪种语言、哪种底层结构实现栈这五个操作是跑不掉的push(element)将元素压入栈顶。pop()弹出栈顶元素并在栈中移除该元素。peek()/top()返回栈顶元素但不移除它。isEmpty()判断栈是否为空。size()返回栈中元素的个数。这五个方法的设计是有讲究的。pop和peek要分开是因为实际业务里你经常只想看栈顶是啥但不想改变它的状态而push和pop的组合则构成了栈最核心的“状态变更”能力。还有一个很容易忽略的约定对空栈执行pop()或peek()是栈操作中最经典的异常场景后面我会专门讲这个坑。在深入源码之前我想先明确指出一个通用设计要点栈底元素的进出顺序是固定的——先进入的元素永远压在下面只有等它上面的所有元素全部弹出之后才能轮到它。这个特性决定了栈非常适合处理“嵌套结构”和“回溯操作”比如函数调用、括号匹配、表达式求值、撤销重做全都依赖这个特性。2. 用C语言亲手实现一个栈数组版与链表版的完整源码很多教材喜欢直接用高级语言实现栈但我个人强烈建议你先用C语言写一遍。原因很简单C语言会逼着你手动管理内存、手动维护指针和下标能让你真正看到栈的“肉”是什么。用Java写栈自动扩容、自动回收很多细节都被隐藏了写完脑子里还是空的。2.1 顺序栈基于动态数组的实现顺序栈的底层是一个数组加一个“栈顶指针”。这里的栈顶指针有两种约定一种是指向栈顶元素本身初始为-1另一种是指向栈顶元素的下一个空位初始为0。我习惯用前一种后面代码也按这个来。先定义结构体#include stdio.h #include stdlib.h #include stdbool.h #define INIT_CAPACITY 4 typedef struct { int *data; // 动态数组 int top; // 栈顶元素的下标空栈时为 -1 int capacity; // 当前容量 } Stack; // 初始化 Stack* stack_create() { Stack *s (Stack*)malloc(sizeof(Stack)); if (!s) return NULL; s-data (int*)malloc(sizeof(int) * INIT_CAPACITY); if (!s-data) { free(s); return NULL; } s-top -1; s-capacity INIT_CAPACITY; return s; } // 判断是否为空 bool stack_is_empty(Stack *s) { return s-top -1; } // 扩容容量翻倍 static bool stack_resize(Stack *s) { int new_capacity s-capacity * 2; int *new_data (int*)realloc(s-data, sizeof(int) * new_capacity); if (!new_data) return false; s-data new_data; s-capacity new_capacity; return true; } // 压栈 bool stack_push(Stack *s, int value) { if (s-top 1 s-capacity) { if (!stack_resize(s)) return false; } s-data[s-top] value; return true; } // 出栈 bool stack_pop(Stack *s, int *out_value) { if (stack_is_empty(s)) return false; if (out_value) *out_value s-data[s-top]; s-top--; return true; } // 查看栈顶 bool stack_peek(Stack *s, int *out_value) { if (stack_is_empty(s)) return false; *out_value s-data[s-top]; return true; } // 销毁 void stack_destroy(Stack *s) { if (s) { free(s-data); free(s); } }这里面有几个容易被忽略的细节第一扩容策略。我选择的是“容量翻倍”而不是“容量1”。如果每次push都只多分配一个int那么插入n个元素的整体代价是O(n^2)而翻倍扩容的整体代价是O(n)均摊下来每次push还是O(1)。这也是Java ArrayList、C vector通用的扩容策略。扩容的时机要放在写入元素之前而且扩容后原来的数据要原封不动保底在相同位置top不用变。第二pop之后要不要缩容教材通常不讲实际写代码时你会发现如果只push不pop内存占用会一直上涨如果频繁push/pop反复扩容缩容又会造成性能抖动。我的经验是只有当“元素个数小于容量的四分之一”时才缩容一次容量缩减为原来的一半这样可以避免在某个阈值附近来回震荡。这个技巧叫“缩容懒惰策略”面试时如果主动提出来会是个加分项。第三pop操作要不要真的把旧位置的数据清掉对于int这类基础类型无所谓但如果栈里存的是指针或对象引用建议把弹出的位置置空否则会有“内存泄漏”的隐患——栈本身还在引用这个对象垃圾回收器或内存分配器就没办法释放它。2.2 链式栈基于单链表的实现链式栈的思路是让链表的头节点作为栈顶每次push就头插一个新节点每次pop就删掉头节点。时间复杂度和顺序栈一样是O(1)但不需要考虑扩容内存按需分配。typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *top; // 栈顶指针 int size; // 元素个数 } LinkedStack; LinkedStack* lstack_create() { LinkedStack *s (LinkedStack*)malloc(sizeof(LinkedStack)); if (!s) return NULL; s-top NULL; s-size 0; return s; } void lstack_push(LinkedStack *s, int value) { Node *node (Node*)malloc(sizeof(Node)); node-data value; node-next s-top; // 新节点指向原来的栈顶 s-top node; // 新节点成为栈顶 s-size; } bool lstack_pop(LinkedStack *s, int *out_value) { if (s-size 0) return false; Node *to_delete s-top; if (out_value) *out_value to_delete-data; s-top to_delete-next; free(to_delete); s-size--; return true; } bool lstack_peek(LinkedStack *s, int *out_value) { if (s-size 0) return false; *out_value s-top-data; return true; } void lstack_destroy(LinkedStack *s) { while (s-top) { Node *to_delete s-top; s-top to_delete-next; free(to_delete); } free(s); }注意链式栈的头插法非常巧妙因为栈只允许在栈顶操作而链表头节点的插入和删除都是O(1)所以不需要尾指针不需要遍历到链表尾部天然匹配栈的语义。你一定要记住“头插法对应push头删法对应pop”这句话。2.3 两种实现怎么选一张表说清楚维度顺序栈数组版链式栈链表版内存分配连续内存预分配可扩容离散内存按需分配访问速度高缓存友好略低节点有指针开销扩容需要扩容均摊O(1)不需要扩容每次push都malloc内存碎片少多空间占用容量可能大于元素数每个节点额外存一个next指针适用场景栈大小可预估、追求性能元素数量难以预估、频繁创建销毁栈实际项目里90%的场景用顺序栈就够了。链式栈最大的价值在于“不需要预先知道大小”以及“可以很方便地实现多个栈共享空间”这种特殊需求。我自己写代码时默认选择顺序栈只有当“栈的个数非常多、每个栈大小波动很大”时才考虑链式栈。3. Java视角下的栈为什么不推荐用Stack类3.1 从JDK源码看Stack类的设计缺陷Java在JDK 1.0就提供了一个java.util.Stack类但如果你去读它的源码会发现它的实现方式相当“原始”它直接继承了Vector类而Vector本身是一个线程安全的动态数组所有方法都加了synchronized。public class StackE extends VectorE { public E push(E item) { addElement(item); return item; } public synchronized E pop() { E obj; int len size(); obj peek(); removeElementAt(len - 1); return obj; } public synchronized E peek() { int len size(); if (len 0) throw new EmptyStackException(); return elementAt(len - 1); } public boolean empty() { return size() 0; } }这里有几个很尴尬的问题Stack继承Vector意味着它继承了add(int index, E element)、remove(int index)、get(int index)这些随机访问方法。这就坏了——栈的抽象语义是“只允许从栈顶操作”但通过父类方法你完全可以从中间插入、删除、随机访问。这个设计破坏了封装也破坏了你对栈这个数据结构的信任。所有方法都加了synchronized这在单线程场景下是纯粹的性能开销。Java官方后来也承认这个类设计得不算成功。更麻烦的是Vector的扩容机制默认是“如果容量的增量没指定就扩容为原来的两倍”这个策略本身没什么问题但放在一个已经过时的集合类里怎么看都别扭。所以Java官方推荐的做法是使用Deque接口的实现类比如ArrayDeque。ArrayDeque底层是循环数组不允许多线程并发单线程下性能远好于Stack而且它明确实现了栈语义的方法push()、pop()、peek()。这几种方法在Deque接口里都有定义用起来跟Stack几乎一模一样。DequeInteger stack new ArrayDeque(); stack.push(1); stack.push(2); int top stack.pop(); // 2注意不要用LinkedList来做栈。LinkedList虽然也实现了Deque接口但它每个节点有额外的指针和对象头开销内存占用和访问速度都不如ArrayDeque。规则很简单Java里做栈单线程默认ArrayDeque多线程用ConcurrentLinkedDeque或者加锁。3.2 手写一个线程安全的栈很多人面试Java岗会碰到“手写一个线程安全的栈”这个题。简单朴素的答案是给方法加synchronized也就是把ArrayDeque包一层public class SafeStackT { private final DequeT stack new ArrayDeque(); public synchronized void push(T item) { stack.push(item); } public synchronized T pop() { if (stack.isEmpty()) { throw new IllegalStateException(stack is empty); } return stack.pop(); } public synchronized T peek() { if (stack.isEmpty()) { throw new IllegalStateException(stack is empty); } return stack.peek(); } public synchronized boolean isEmpty() { return stack.isEmpty(); } }但这样做有一个问题isEmpty()和pop()是分开的两个方法如果调用方先判空再pop两个步骤之间有其他线程插入依然会出问题。真正的线程安全栈要么把“判空弹出”合并成一个原子操作要么直接提供tryPop()这样的方法。public synchronized T tryPop() { if (stack.isEmpty()) { return null; // 或者抛出异常取决于业务 } return stack.pop(); }这个话题还可以往深了聊如果追求高并发可以换成ConcurrentLinkedDeque它是无锁并发队列基于CAS实现如果追求更极端的性能可以自己用链表实现一个无锁栈如Treiber算法核心思想是用AtomicReference保存栈顶指针CAS循环修改。不过我再强调一句日常业务开发真的需要无锁栈的场景极少不要为了炫技而引入复杂性。3.3 说说“Java堆和栈的区别”这个高频面试题热词里“java中堆和栈的区别”搜索量常年居高不下这里顺手把这个概念一并讲透。注意JVM里的“栈”和数据结构的“栈”不是一个概念但两者又有对应关系。JVM的运行时数据区中每个线程都有一块私有的“虚拟机栈”JVM Stack它里面存放的是一个个“栈帧”Stack Frame每个栈帧对应一次方法调用。方法开始执行时就压入一个栈帧方法返回时就弹出这个栈帧。栈帧内部包括局部变量表、操作数栈、动态链接、方法返回地址等信息。这套机制完美复用了数据结构“栈”的先进后出原则先调用的方法后返回后调用的方法先返回。而JVM的“堆”Heap就是另一回事了它是所有线程共享的一大块内存用来存放对象实例和数组。你在代码里new出来的对象绝大多数都在堆里分配。栈帧里的局部变量存的是引用引用指向堆里的对象基本类型变量有些直接存在栈帧的局部变量表里。所以面试里说的“堆和栈的区别”本质上就是在问栈是线程私有的堆是线程共享的。栈存“调用状态”和“局部变量”堆存“对象实例”。栈的生命周期跟线程一样线程结束栈就释放堆的生命周期由垃圾回收器管理。栈内存不足抛出StackOverflowError堆内存不足抛出OutOfMemoryError: Java heap space。理解了这一层你再去看IDE里报错时显示的“调用栈”Call Stack就明白那其实就是一层层方法调用的栈帧信息从当前正在执行的方法一路往上直到main方法。这也是“栈”这个数据结构在真实系统里最壮观的应用场景。4. 栈的经典应用场景这些代码背后都在用栈4.1 函数调用与递归程序运行背后的无名英雄任何一门语言函数调用都离不开栈。拿一个简单的例子来说int add(int a, int b) { return a b; } int main() { int x 1; int y 2; int z add(x, y); return z; }当main方法执行到add(x, y)时JVM或操作系统的线程栈会为add方法创建一个新的栈帧压入当前线程的虚拟机栈里。栈帧里记录了形参a、b的值、局部变量、返回地址。当add计算完返回时这个栈帧被弹出程序继续回到main方法下一条指令执行也就是int z ...这一句。递归之所以天然适合用栈来理解是因为每一层递归调用都会产生一个新的栈帧。比如经典的阶乘int factorial(int n) { if (n 1) return 1; return n * factorial(n - 1); }调用factorial(3)时栈帧依次压入factorial(3)、factorial(2)、factorial(1)。计算到factorial(1)返回1之后栈帧才依次弹出factorial(2)算出2factorial(3)算出6。整个过程就是后进先出最后一次调用最先返回。4.2 带栈的括号匹配面试常考的代码题括号匹配是我认为最能展示栈这个数据结构的经典题。题目很简单给一个只包含()[]{}的字符串判断括号是否成对且嵌套正确。核心思想是遍历字符串遇到左括号就压入栈遇到右括号就弹出栈顶元素检查是否匹配。如果遍历结束后栈为空说明所有左括号都有对应的右括号匹配成功如果中途发现栈顶元素与当前右括号不匹配或者弹出时栈已经是空的直接返回失败。public boolean isValid(String s) { DequeCharacter stack new ArrayDeque(); MapCharacter, Character map Map.of( ), (, ], [, }, { ); for (char c : s.toCharArray()) { if (c ( || c [ || c {) { stack.push(c); } else { if (stack.isEmpty() || stack.pop() ! map.get(c)) { return false; } } } return stack.isEmpty(); }很多人在这一步会踩一个坑用if (c ) stack.peek() ! ()这种方式时忘了先判断栈是否为空。如果第一个字符就是)对空栈执行peek()或pop()直接抛异常。我在面试里见过太多候选人倒在这个细节上代码逻辑没问题但没处理边界条件。栈的操作首先要考虑空栈情况其次才是匹配逻辑。4.3 表达式求值中缀转后缀与后缀计算计算机处理数学表达式最喜欢的是后缀表达式逆波兰表达式因为不需要考虑运算符优先级和括号。比如中缀表达式3 4 * 2对应的后缀表达式是3 4 2 * 。后缀表达式的计算规则是遇到数字就入栈遇到运算符就弹出两个数字计算再把结果压回栈里。public int evalRPN(String[] tokens) { DequeInteger stack new ArrayDeque(); for (String token : tokens) { if (isNumber(token)) { stack.push(Integer.parseInt(token)); } else { int b stack.pop(); int a stack.pop(); switch (token) { case - stack.push(a b); case - - stack.push(a - b); case * - stack.push(a * b); case / - stack.push(a / b); } } } return stack.pop(); }注意从栈里弹出的两个数字第一个弹出来的是b第二个是a。如果你做减法或除法时把顺序搞反了结果就会错。这种“弹出顺序”的细节是栈类算法题里最容易出错的地方我当年笔试就栽过一次。至于中缀转后缀核心算法是遇到数字直接输出遇到运算符如果栈顶运算符优先级高于或等于当前运算符就不断弹出遇到左括号压栈遇到右括号弹出直到左括号。整个过程依然靠栈来维护“等待处理的运算符”。4.4 撤销重做、浏览器的前进后退栈无处不在这些应用场景你每天都在用但可能没意识到它们就是栈编辑器的CtrlZ每做一次操作就压入一个栈帧撤销就是弹出最近的操作并执行逆操作重做又是另一个栈。浏览器的后退按钮每访问一个页面就压入“前进栈”点击后退就弹出当前页面、压入“后退栈”。代码编辑器的大括号高亮本质上就是括号匹配的变体。我把这些场景列出来是想说明栈不是数据结构课本上的一纸空谈它是系统设计里最常用的“历史记录”模型。凡是存在“先后顺序”且需要“逆序回溯”的地方都可以考虑使用栈。5. 从实现走向实战高频面试题剖析与避坑指北5.1 用两个栈实现一个队列这是一道经典面试题而且包含了“用栈模拟另一种数据结构”的思考路径。队列是先进先出FIFO栈是后进先出LIFO。两个栈配合可以实现先进先出的效果。思路是入队offer直接压入stackIn。出队poll如果stackOut不为空直接从stackOut弹出如果stackOut为空先把stackIn里的所有元素依次弹出并压入stackOut再从stackOut弹出。以入队1、2、3为例。加入stackIn后stackIn从栈底到栈顶是[1,2,3]。出队时把stackIn里的元素全部倒入stackOut现在stackOut从栈底到栈顶是[3,2,1]栈顶是1。弹出1正好是先进入队列的元素。下一次出队时stackOut栈顶是2直接弹出。这就是“一次倒灌多次使用”的精髓。class MyQueue { private final DequeInteger in new ArrayDeque(); private final DequeInteger out new ArrayDeque(); public void push(int x) { in.push(x); } public int pop() { if (out.isEmpty()) { while (!in.isEmpty()) { out.push(in.pop()); } } return out.pop(); } }这里的关键性能点是不要每次pop()都倒灌只有stackOut为空时才需要倒灌。均摊下来每个元素最多被“移动”两次整体时间复杂度还是O(1)。这种“懒加载”思路在真实业务里也很有用不是每次请求都重组数据而是等到真正需要的时候才做一次批量整理。5.2 最小栈O(1)时间找到栈中最小值题目要求设计一个栈支持push、pop、top、getMin四个操作并且getMin要在O(1)时间内完成。最直接的想法是每次push时遍历一遍找最小值但这样getMin就成了O(n)。更优雅的解法是“辅助栈”维护两个栈一个正常存数据一个用来存“当前栈内最小值的轨迹”。每次push时把当前元素和辅助栈栈顶比较把较小值压入辅助栈pop时两个栈同时弹出保证辅助栈栈顶永远是当前栈内的最小值。class MinStack { private final DequeInteger stack new ArrayDeque(); private final DequeInteger minStack new ArrayDeque(); public void push(int val) { stack.push(val); if (minStack.isEmpty() || val minStack.peek()) { minStack.push(val); } else { minStack.push(minStack.peek()); } } public void pop() { stack.pop(); minStack.pop(); } public int getMin() { return minStack.peek(); } }注意我用了val minStack.peek()这里是小于等于。为什么如果等于最小值时也压入辅助栈pop时两个栈依然同步不会出现靠“相等判断”丢失记录的问题。你如果写当连续push两个相同的最小值时pop掉一个后辅助栈顶就没有这个最小值了当前栈里其实还有一个最小值但getMin会给出错误答案。这个细节无数面试者在这里翻车。5.3 递归为什么会导致栈溢出这个问题的本质你已经理解了每一次方法调用都会创建一个栈帧栈帧里存放局部变量、操作数栈、返回地址等信息。如果递归深度太大栈帧数量暴增而每个线程的虚拟机栈容量是有限的通常默认1MB左右取决于JVM参数-Xss设置栈帧把栈空间占满后再想压入新的栈帧就会抛StackOverflowError。解决办法通常有几个方向把递归改成迭代。比如递归版的斐波那契改成循环本质上就是用一个显式的栈来模拟系统栈。改用尾递归。有些语言能优化尾递归不会增加栈帧但Java目前还没有这个能力。增大栈空间-Xss2m这样设置能缓解但不能根治只适用于“递归深度偶尔超限”的场景。从数据结构角度讲递归和显式栈本来就是等价的凡是能递归解决的问题一定能用栈改成迭代反之亦然。理解了这一步你对栈的理解就真正上了一个台阶。5.4 栈的常见问题速查表问题现象可能原因排查方式与建议StackOverflowError递归深度过大或死循环递归检查递归终止条件改用迭代或显式栈必要时调整-XssEmptyStackException/NoSuchElementException对空栈执行pop/peek操作前先isEmpty()判断或设计tryPop返回默认值内存占用持续上涨顺序栈扩容后不缩容或链式栈频繁创建节点未释放缩容采用“四分之一触发”策略注意释放链表节点IDE里调用栈看不清不知道如何分析调用栈信息找到栈顶就是当前执行位置逐层往下是调用来源链栈数据被意外修改使用了Stack类通过Vector的随机访问方法操作数据改用ArrayDeque从接口层面禁止非栈操作6. 实操心得老手写栈时的三个独家建议这篇文章写到最后我想分享几个在真实项目中总结的经验希望你在动手实现和使用栈时能少走弯路。第一栈的容量设计不要“拍脑袋”。如果你能预估栈的峰值大小直接指定初始容量避免扩容。比如编译器解析代码时括号嵌套深度很少超过几百层初始容量设256完全够用但表达式求值中操作数的数量可能很大就要适当放大初始容量。扩容是有成本的realloc需要搬移数据频繁扩容会带来性能抖动。第二写栈算法题时一定要先画图再写代码。我在面试别人时经常发现很多候选人拿到括号匹配、表达式求值这类题就直接上手写写着写着栈顶顺序搞反了。我的做法是先在纸上画一支“竖着的栈”把入栈出栈的顺序一步步画出来把变量名都标清楚再落笔写代码。看似多花了30秒实际能省下大量调试时间。第三用Java写栈时明确区分offer/poll和push/pop的区别。Deque接口里既有队列语义的方法offer、poll又有栈语义的方法push、pop。混用会让人读代码时晕头转向而且容易出错。要么只用push/pop/peek要么只用addFirst/removeFirst/getFirst不要在同一份代码里两种风格混着来。数据结构这东西学的时候觉得抽象用起来才觉得真香。栈作为最基础的线性结构之一它的价值不是“能装东西”而是“以严格的顺序约束帮我们管理回溯状态”。希望你读完这篇文章之后能动手把两种C语言实现和Java版本都敲一遍再去LeetCode上找几道栈相关的题练手。等你能熟练地用栈解决实际场景问题的时候你会回来感谢那个认真写代码的自己。 栈数据结构完全指南：原理、实现、应用与JVM调用栈解析
写这篇文章之前我先说个真实感受。我在面试候选人的时候只要问一句“栈和队列有什么区别”十个人里至少有五个能答上“先进后出、先进先出”但你再追问一句“栈这玩意儿在JVM里是怎么工作的IDE里那个调用栈到底在看什么”能答上来的人就少了一大半。不是大家不懂是很多人把栈当成了一个“考试名词”背完定义就扔了根本没把它跟真实的编程场景挂上钩。这篇文章不打算只给你贴一份课本上的伪代码而是站在“一个真正写过代码、调过崩溃、被递归爆栈折磨过的人”的角度把栈这个数据结构从原理讲到源码从数组版讲到链表版从C语言版讲到Java版再顺手把面试最爱考的那几道栈相关的题也拆了。内容偏实操建议你手里放着一个IDE看到代码片段就自己动手敲一遍光看不写永远学不会数据结构。1. 先搞清楚栈是什么后进先出这四个字背后的设计逻辑1.1 从一摞盘子说起栈的直觉模型栈Stack本质上是一种线性表但它比普通线性表多了一个很严格的限制所有的插入和删除操作都只能发生在表的“同一端”这一端叫栈顶Top另一端叫栈底Bottom。操作方式只有两种往栈顶压入一个元素Push以及从栈顶弹出一个元素Pop。后放进去的元素最先被取出来这就是所谓的“后进先出”LIFOLast In First Out。如果你端起一摞盘子你永远只能先把最上面那个盘子拿走想拿最底下的必须把上面的全搬走。往这摞盘子上再放一个新盘子它也一定是在最顶端。栈这个抽象模型本质上就是在模拟这种“只从一头进出”的物理直觉。我第一次学栈的时候觉得这玩意儿太简单了不就是一个“限制版的数组”吗后来代码写多了才意识到恰恰是这个“限制”让它变成了计算机世界里最优雅、最高效的结构之一。为什么这么说因为栈的所有操作都发生在栈顶所以无论栈里现在有多少个元素Push和Pop的时间复杂度都是O(1)跟数据规模无关。这是很多其他数据结构做不到的特性。1.2 栈的核心操作与设计约定不管用哪种语言、哪种底层结构实现栈这五个操作是跑不掉的push(element)将元素压入栈顶。pop()弹出栈顶元素并在栈中移除该元素。peek()/top()返回栈顶元素但不移除它。isEmpty()判断栈是否为空。size()返回栈中元素的个数。这五个方法的设计是有讲究的。pop和peek要分开是因为实际业务里你经常只想看栈顶是啥但不想改变它的状态而push和pop的组合则构成了栈最核心的“状态变更”能力。还有一个很容易忽略的约定对空栈执行pop()或peek()是栈操作中最经典的异常场景后面我会专门讲这个坑。在深入源码之前我想先明确指出一个通用设计要点栈底元素的进出顺序是固定的——先进入的元素永远压在下面只有等它上面的所有元素全部弹出之后才能轮到它。这个特性决定了栈非常适合处理“嵌套结构”和“回溯操作”比如函数调用、括号匹配、表达式求值、撤销重做全都依赖这个特性。2. 用C语言亲手实现一个栈数组版与链表版的完整源码很多教材喜欢直接用高级语言实现栈但我个人强烈建议你先用C语言写一遍。原因很简单C语言会逼着你手动管理内存、手动维护指针和下标能让你真正看到栈的“肉”是什么。用Java写栈自动扩容、自动回收很多细节都被隐藏了写完脑子里还是空的。2.1 顺序栈基于动态数组的实现顺序栈的底层是一个数组加一个“栈顶指针”。这里的栈顶指针有两种约定一种是指向栈顶元素本身初始为-1另一种是指向栈顶元素的下一个空位初始为0。我习惯用前一种后面代码也按这个来。先定义结构体#include stdio.h #include stdlib.h #include stdbool.h #define INIT_CAPACITY 4 typedef struct { int *data; // 动态数组 int top; // 栈顶元素的下标空栈时为 -1 int capacity; // 当前容量 } Stack; // 初始化 Stack* stack_create() { Stack *s (Stack*)malloc(sizeof(Stack)); if (!s) return NULL; s-data (int*)malloc(sizeof(int) * INIT_CAPACITY); if (!s-data) { free(s); return NULL; } s-top -1; s-capacity INIT_CAPACITY; return s; } // 判断是否为空 bool stack_is_empty(Stack *s) { return s-top -1; } // 扩容容量翻倍 static bool stack_resize(Stack *s) { int new_capacity s-capacity * 2; int *new_data (int*)realloc(s-data, sizeof(int) * new_capacity); if (!new_data) return false; s-data new_data; s-capacity new_capacity; return true; } // 压栈 bool stack_push(Stack *s, int value) { if (s-top 1 s-capacity) { if (!stack_resize(s)) return false; } s-data[s-top] value; return true; } // 出栈 bool stack_pop(Stack *s, int *out_value) { if (stack_is_empty(s)) return false; if (out_value) *out_value s-data[s-top]; s-top--; return true; } // 查看栈顶 bool stack_peek(Stack *s, int *out_value) { if (stack_is_empty(s)) return false; *out_value s-data[s-top]; return true; } // 销毁 void stack_destroy(Stack *s) { if (s) { free(s-data); free(s); } }这里面有几个容易被忽略的细节第一扩容策略。我选择的是“容量翻倍”而不是“容量1”。如果每次push都只多分配一个int那么插入n个元素的整体代价是O(n^2)而翻倍扩容的整体代价是O(n)均摊下来每次push还是O(1)。这也是Java ArrayList、C vector通用的扩容策略。扩容的时机要放在写入元素之前而且扩容后原来的数据要原封不动保底在相同位置top不用变。第二pop之后要不要缩容教材通常不讲实际写代码时你会发现如果只push不pop内存占用会一直上涨如果频繁push/pop反复扩容缩容又会造成性能抖动。我的经验是只有当“元素个数小于容量的四分之一”时才缩容一次容量缩减为原来的一半这样可以避免在某个阈值附近来回震荡。这个技巧叫“缩容懒惰策略”面试时如果主动提出来会是个加分项。第三pop操作要不要真的把旧位置的数据清掉对于int这类基础类型无所谓但如果栈里存的是指针或对象引用建议把弹出的位置置空否则会有“内存泄漏”的隐患——栈本身还在引用这个对象垃圾回收器或内存分配器就没办法释放它。2.2 链式栈基于单链表的实现链式栈的思路是让链表的头节点作为栈顶每次push就头插一个新节点每次pop就删掉头节点。时间复杂度和顺序栈一样是O(1)但不需要考虑扩容内存按需分配。typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *top; // 栈顶指针 int size; // 元素个数 } LinkedStack; LinkedStack* lstack_create() { LinkedStack *s (LinkedStack*)malloc(sizeof(LinkedStack)); if (!s) return NULL; s-top NULL; s-size 0; return s; } void lstack_push(LinkedStack *s, int value) { Node *node (Node*)malloc(sizeof(Node)); node-data value; node-next s-top; // 新节点指向原来的栈顶 s-top node; // 新节点成为栈顶 s-size; } bool lstack_pop(LinkedStack *s, int *out_value) { if (s-size 0) return false; Node *to_delete s-top; if (out_value) *out_value to_delete-data; s-top to_delete-next; free(to_delete); s-size--; return true; } bool lstack_peek(LinkedStack *s, int *out_value) { if (s-size 0) return false; *out_value s-top-data; return true; } void lstack_destroy(LinkedStack *s) { while (s-top) { Node *to_delete s-top; s-top to_delete-next; free(to_delete); } free(s); }注意链式栈的头插法非常巧妙因为栈只允许在栈顶操作而链表头节点的插入和删除都是O(1)所以不需要尾指针不需要遍历到链表尾部天然匹配栈的语义。你一定要记住“头插法对应push头删法对应pop”这句话。2.3 两种实现怎么选一张表说清楚维度顺序栈数组版链式栈链表版内存分配连续内存预分配可扩容离散内存按需分配访问速度高缓存友好略低节点有指针开销扩容需要扩容均摊O(1)不需要扩容每次push都malloc内存碎片少多空间占用容量可能大于元素数每个节点额外存一个next指针适用场景栈大小可预估、追求性能元素数量难以预估、频繁创建销毁栈实际项目里90%的场景用顺序栈就够了。链式栈最大的价值在于“不需要预先知道大小”以及“可以很方便地实现多个栈共享空间”这种特殊需求。我自己写代码时默认选择顺序栈只有当“栈的个数非常多、每个栈大小波动很大”时才考虑链式栈。3. Java视角下的栈为什么不推荐用Stack类3.1 从JDK源码看Stack类的设计缺陷Java在JDK 1.0就提供了一个java.util.Stack类但如果你去读它的源码会发现它的实现方式相当“原始”它直接继承了Vector类而Vector本身是一个线程安全的动态数组所有方法都加了synchronized。public class StackE extends VectorE { public E push(E item) { addElement(item); return item; } public synchronized E pop() { E obj; int len size(); obj peek(); removeElementAt(len - 1); return obj; } public synchronized E peek() { int len size(); if (len 0) throw new EmptyStackException(); return elementAt(len - 1); } public boolean empty() { return size() 0; } }这里有几个很尴尬的问题Stack继承Vector意味着它继承了add(int index, E element)、remove(int index)、get(int index)这些随机访问方法。这就坏了——栈的抽象语义是“只允许从栈顶操作”但通过父类方法你完全可以从中间插入、删除、随机访问。这个设计破坏了封装也破坏了你对栈这个数据结构的信任。所有方法都加了synchronized这在单线程场景下是纯粹的性能开销。Java官方后来也承认这个类设计得不算成功。更麻烦的是Vector的扩容机制默认是“如果容量的增量没指定就扩容为原来的两倍”这个策略本身没什么问题但放在一个已经过时的集合类里怎么看都别扭。所以Java官方推荐的做法是使用Deque接口的实现类比如ArrayDeque。ArrayDeque底层是循环数组不允许多线程并发单线程下性能远好于Stack而且它明确实现了栈语义的方法push()、pop()、peek()。这几种方法在Deque接口里都有定义用起来跟Stack几乎一模一样。DequeInteger stack new ArrayDeque(); stack.push(1); stack.push(2); int top stack.pop(); // 2注意不要用LinkedList来做栈。LinkedList虽然也实现了Deque接口但它每个节点有额外的指针和对象头开销内存占用和访问速度都不如ArrayDeque。规则很简单Java里做栈单线程默认ArrayDeque多线程用ConcurrentLinkedDeque或者加锁。3.2 手写一个线程安全的栈很多人面试Java岗会碰到“手写一个线程安全的栈”这个题。简单朴素的答案是给方法加synchronized也就是把ArrayDeque包一层public class SafeStackT { private final DequeT stack new ArrayDeque(); public synchronized void push(T item) { stack.push(item); } public synchronized T pop() { if (stack.isEmpty()) { throw new IllegalStateException(stack is empty); } return stack.pop(); } public synchronized T peek() { if (stack.isEmpty()) { throw new IllegalStateException(stack is empty); } return stack.peek(); } public synchronized boolean isEmpty() { return stack.isEmpty(); } }但这样做有一个问题isEmpty()和pop()是分开的两个方法如果调用方先判空再pop两个步骤之间有其他线程插入依然会出问题。真正的线程安全栈要么把“判空弹出”合并成一个原子操作要么直接提供tryPop()这样的方法。public synchronized T tryPop() { if (stack.isEmpty()) { return null; // 或者抛出异常取决于业务 } return stack.pop(); }这个话题还可以往深了聊如果追求高并发可以换成ConcurrentLinkedDeque它是无锁并发队列基于CAS实现如果追求更极端的性能可以自己用链表实现一个无锁栈如Treiber算法核心思想是用AtomicReference保存栈顶指针CAS循环修改。不过我再强调一句日常业务开发真的需要无锁栈的场景极少不要为了炫技而引入复杂性。3.3 说说“Java堆和栈的区别”这个高频面试题热词里“java中堆和栈的区别”搜索量常年居高不下这里顺手把这个概念一并讲透。注意JVM里的“栈”和数据结构的“栈”不是一个概念但两者又有对应关系。JVM的运行时数据区中每个线程都有一块私有的“虚拟机栈”JVM Stack它里面存放的是一个个“栈帧”Stack Frame每个栈帧对应一次方法调用。方法开始执行时就压入一个栈帧方法返回时就弹出这个栈帧。栈帧内部包括局部变量表、操作数栈、动态链接、方法返回地址等信息。这套机制完美复用了数据结构“栈”的先进后出原则先调用的方法后返回后调用的方法先返回。而JVM的“堆”Heap就是另一回事了它是所有线程共享的一大块内存用来存放对象实例和数组。你在代码里new出来的对象绝大多数都在堆里分配。栈帧里的局部变量存的是引用引用指向堆里的对象基本类型变量有些直接存在栈帧的局部变量表里。所以面试里说的“堆和栈的区别”本质上就是在问栈是线程私有的堆是线程共享的。栈存“调用状态”和“局部变量”堆存“对象实例”。栈的生命周期跟线程一样线程结束栈就释放堆的生命周期由垃圾回收器管理。栈内存不足抛出StackOverflowError堆内存不足抛出OutOfMemoryError: Java heap space。理解了这一层你再去看IDE里报错时显示的“调用栈”Call Stack就明白那其实就是一层层方法调用的栈帧信息从当前正在执行的方法一路往上直到main方法。这也是“栈”这个数据结构在真实系统里最壮观的应用场景。4. 栈的经典应用场景这些代码背后都在用栈4.1 函数调用与递归程序运行背后的无名英雄任何一门语言函数调用都离不开栈。拿一个简单的例子来说int add(int a, int b) { return a b; } int main() { int x 1; int y 2; int z add(x, y); return z; }当main方法执行到add(x, y)时JVM或操作系统的线程栈会为add方法创建一个新的栈帧压入当前线程的虚拟机栈里。栈帧里记录了形参a、b的值、局部变量、返回地址。当add计算完返回时这个栈帧被弹出程序继续回到main方法下一条指令执行也就是int z ...这一句。递归之所以天然适合用栈来理解是因为每一层递归调用都会产生一个新的栈帧。比如经典的阶乘int factorial(int n) { if (n 1) return 1; return n * factorial(n - 1); }调用factorial(3)时栈帧依次压入factorial(3)、factorial(2)、factorial(1)。计算到factorial(1)返回1之后栈帧才依次弹出factorial(2)算出2factorial(3)算出6。整个过程就是后进先出最后一次调用最先返回。4.2 带栈的括号匹配面试常考的代码题括号匹配是我认为最能展示栈这个数据结构的经典题。题目很简单给一个只包含()[]{}的字符串判断括号是否成对且嵌套正确。核心思想是遍历字符串遇到左括号就压入栈遇到右括号就弹出栈顶元素检查是否匹配。如果遍历结束后栈为空说明所有左括号都有对应的右括号匹配成功如果中途发现栈顶元素与当前右括号不匹配或者弹出时栈已经是空的直接返回失败。public boolean isValid(String s) { DequeCharacter stack new ArrayDeque(); MapCharacter, Character map Map.of( ), (, ], [, }, { ); for (char c : s.toCharArray()) { if (c ( || c [ || c {) { stack.push(c); } else { if (stack.isEmpty() || stack.pop() ! map.get(c)) { return false; } } } return stack.isEmpty(); }很多人在这一步会踩一个坑用if (c ) stack.peek() ! ()这种方式时忘了先判断栈是否为空。如果第一个字符就是)对空栈执行peek()或pop()直接抛异常。我在面试里见过太多候选人倒在这个细节上代码逻辑没问题但没处理边界条件。栈的操作首先要考虑空栈情况其次才是匹配逻辑。4.3 表达式求值中缀转后缀与后缀计算计算机处理数学表达式最喜欢的是后缀表达式逆波兰表达式因为不需要考虑运算符优先级和括号。比如中缀表达式3 4 * 2对应的后缀表达式是3 4 2 * 。后缀表达式的计算规则是遇到数字就入栈遇到运算符就弹出两个数字计算再把结果压回栈里。public int evalRPN(String[] tokens) { DequeInteger stack new ArrayDeque(); for (String token : tokens) { if (isNumber(token)) { stack.push(Integer.parseInt(token)); } else { int b stack.pop(); int a stack.pop(); switch (token) { case - stack.push(a b); case - - stack.push(a - b); case * - stack.push(a * b); case / - stack.push(a / b); } } } return stack.pop(); }注意从栈里弹出的两个数字第一个弹出来的是b第二个是a。如果你做减法或除法时把顺序搞反了结果就会错。这种“弹出顺序”的细节是栈类算法题里最容易出错的地方我当年笔试就栽过一次。至于中缀转后缀核心算法是遇到数字直接输出遇到运算符如果栈顶运算符优先级高于或等于当前运算符就不断弹出遇到左括号压栈遇到右括号弹出直到左括号。整个过程依然靠栈来维护“等待处理的运算符”。4.4 撤销重做、浏览器的前进后退栈无处不在这些应用场景你每天都在用但可能没意识到它们就是栈编辑器的CtrlZ每做一次操作就压入一个栈帧撤销就是弹出最近的操作并执行逆操作重做又是另一个栈。浏览器的后退按钮每访问一个页面就压入“前进栈”点击后退就弹出当前页面、压入“后退栈”。代码编辑器的大括号高亮本质上就是括号匹配的变体。我把这些场景列出来是想说明栈不是数据结构课本上的一纸空谈它是系统设计里最常用的“历史记录”模型。凡是存在“先后顺序”且需要“逆序回溯”的地方都可以考虑使用栈。5. 从实现走向实战高频面试题剖析与避坑指北5.1 用两个栈实现一个队列这是一道经典面试题而且包含了“用栈模拟另一种数据结构”的思考路径。队列是先进先出FIFO栈是后进先出LIFO。两个栈配合可以实现先进先出的效果。思路是入队offer直接压入stackIn。出队poll如果stackOut不为空直接从stackOut弹出如果stackOut为空先把stackIn里的所有元素依次弹出并压入stackOut再从stackOut弹出。以入队1、2、3为例。加入stackIn后stackIn从栈底到栈顶是[1,2,3]。出队时把stackIn里的元素全部倒入stackOut现在stackOut从栈底到栈顶是[3,2,1]栈顶是1。弹出1正好是先进入队列的元素。下一次出队时stackOut栈顶是2直接弹出。这就是“一次倒灌多次使用”的精髓。class MyQueue { private final DequeInteger in new ArrayDeque(); private final DequeInteger out new ArrayDeque(); public void push(int x) { in.push(x); } public int pop() { if (out.isEmpty()) { while (!in.isEmpty()) { out.push(in.pop()); } } return out.pop(); } }这里的关键性能点是不要每次pop()都倒灌只有stackOut为空时才需要倒灌。均摊下来每个元素最多被“移动”两次整体时间复杂度还是O(1)。这种“懒加载”思路在真实业务里也很有用不是每次请求都重组数据而是等到真正需要的时候才做一次批量整理。5.2 最小栈O(1)时间找到栈中最小值题目要求设计一个栈支持push、pop、top、getMin四个操作并且getMin要在O(1)时间内完成。最直接的想法是每次push时遍历一遍找最小值但这样getMin就成了O(n)。更优雅的解法是“辅助栈”维护两个栈一个正常存数据一个用来存“当前栈内最小值的轨迹”。每次push时把当前元素和辅助栈栈顶比较把较小值压入辅助栈pop时两个栈同时弹出保证辅助栈栈顶永远是当前栈内的最小值。class MinStack { private final DequeInteger stack new ArrayDeque(); private final DequeInteger minStack new ArrayDeque(); public void push(int val) { stack.push(val); if (minStack.isEmpty() || val minStack.peek()) { minStack.push(val); } else { minStack.push(minStack.peek()); } } public void pop() { stack.pop(); minStack.pop(); } public int getMin() { return minStack.peek(); } }注意我用了val minStack.peek()这里是小于等于。为什么如果等于最小值时也压入辅助栈pop时两个栈依然同步不会出现靠“相等判断”丢失记录的问题。你如果写当连续push两个相同的最小值时pop掉一个后辅助栈顶就没有这个最小值了当前栈里其实还有一个最小值但getMin会给出错误答案。这个细节无数面试者在这里翻车。5.3 递归为什么会导致栈溢出这个问题的本质你已经理解了每一次方法调用都会创建一个栈帧栈帧里存放局部变量、操作数栈、返回地址等信息。如果递归深度太大栈帧数量暴增而每个线程的虚拟机栈容量是有限的通常默认1MB左右取决于JVM参数-Xss设置栈帧把栈空间占满后再想压入新的栈帧就会抛StackOverflowError。解决办法通常有几个方向把递归改成迭代。比如递归版的斐波那契改成循环本质上就是用一个显式的栈来模拟系统栈。改用尾递归。有些语言能优化尾递归不会增加栈帧但Java目前还没有这个能力。增大栈空间-Xss2m这样设置能缓解但不能根治只适用于“递归深度偶尔超限”的场景。从数据结构角度讲递归和显式栈本来就是等价的凡是能递归解决的问题一定能用栈改成迭代反之亦然。理解了这一步你对栈的理解就真正上了一个台阶。5.4 栈的常见问题速查表问题现象可能原因排查方式与建议StackOverflowError递归深度过大或死循环递归检查递归终止条件改用迭代或显式栈必要时调整-XssEmptyStackException/NoSuchElementException对空栈执行pop/peek操作前先isEmpty()判断或设计tryPop返回默认值内存占用持续上涨顺序栈扩容后不缩容或链式栈频繁创建节点未释放缩容采用“四分之一触发”策略注意释放链表节点IDE里调用栈看不清不知道如何分析调用栈信息找到栈顶就是当前执行位置逐层往下是调用来源链栈数据被意外修改使用了Stack类通过Vector的随机访问方法操作数据改用ArrayDeque从接口层面禁止非栈操作6. 实操心得老手写栈时的三个独家建议这篇文章写到最后我想分享几个在真实项目中总结的经验希望你在动手实现和使用栈时能少走弯路。第一栈的容量设计不要“拍脑袋”。如果你能预估栈的峰值大小直接指定初始容量避免扩容。比如编译器解析代码时括号嵌套深度很少超过几百层初始容量设256完全够用但表达式求值中操作数的数量可能很大就要适当放大初始容量。扩容是有成本的realloc需要搬移数据频繁扩容会带来性能抖动。第二写栈算法题时一定要先画图再写代码。我在面试别人时经常发现很多候选人拿到括号匹配、表达式求值这类题就直接上手写写着写着栈顶顺序搞反了。我的做法是先在纸上画一支“竖着的栈”把入栈出栈的顺序一步步画出来把变量名都标清楚再落笔写代码。看似多花了30秒实际能省下大量调试时间。第三用Java写栈时明确区分offer/poll和push/pop的区别。Deque接口里既有队列语义的方法offer、poll又有栈语义的方法push、pop。混用会让人读代码时晕头转向而且容易出错。要么只用push/pop/peek要么只用addFirst/removeFirst/getFirst不要在同一份代码里两种风格混着来。数据结构这东西学的时候觉得抽象用起来才觉得真香。栈作为最基础的线性结构之一它的价值不是“能装东西”而是“以严格的顺序约束帮我们管理回溯状态”。希望你读完这篇文章之后能动手把两种C语言实现和Java版本都敲一遍再去LeetCode上找几道栈相关的题练手。等你能熟练地用栈解决实际场景问题的时候你会回来感谢那个认真写代码的自己。