企业官网建设流程全解析

很多刚开始学数据结构的朋友，第一反应都是：栈？不就是个“先进后出”的列表吗，有什么好讲的？可等你真正深入下去会发现，栈是整个计算机系统里最基础、也最容易“看起来懂、用起来懵”的数据结构之一。这篇栈入门基础详解，我想按自己这几年带新人、复习数据结构时的心得，把栈从生活模型讲到代码实现，再讲到调试现场，尽量让零基础读者也能一口气看明白。

我不会只丢给你一堆定义。先说清楚栈到底在抽象什么，然后讲程序运行时为什么离不开它，接着手写几种实现，再落到括号匹配、表达式求值、DFS这些高频场景。每个部分都会给出可直接运行的代码和注意事项，这样你学完以后，至少能把“栈”这项基本功真正变成自己的东西。

1. 栈到底在“先进后出”什么：从叠盘子开始理解

1.1 生活里的栈：叠盘子、撤销操作、浏览记录

“后进先出”这个词，第一次接触的人都会觉得抽象。但只要你收盘子干过活，其实已经理解栈了。餐厅收盘子，后放上去的盘子总会被先拿走；收银员手里那沓单据，新压上去的放最上面，结算时也是从上面抽。再想想编辑器里的 Ctrl+Z 撤销操作，你最后一次敲的字符，会最先被撤销；浏览器后退按钮访问历史，同样是你后访问的页面先回退。这些都是栈，只是平时没有用计算机术语去称呼它。

所以遇到“栈”的时候，别一上来就死背“先进后出”这个定义。先在心里建立几个画面：一摞盘子、一沓单据、一条撤销记录。计算机里的栈，就是把这些自然行为抽象成一种数据结构。限制很简单：新增元素只能放到栈顶，移除元素也只能从栈顶拿，不能像数组那样随意插入中间、删除中间。正是这种“受限”的存取方式，让很多算法和系统机制可以高效运转。

1.2 入栈、出栈、读取栈顶：核心操作的抽象逻辑

栈的核心操作并不复杂，但很多人会漏掉一两个。除了常见的入栈、出栈，读取栈顶、判空、取大小也同样是高频操作：

注意 peek 和 pop 的区别。peek 相当于你看一眼盘子最上面是什么，看完放回去；pop 则是直接把最上面的盘子端走。初学者最容易犯的错误，就是把 peek 写成 pop，导致数据被意外删除。

栈的实现底层可以是一个数组，也可以是一条链表，但对外暴露的逻辑永远是栈顶存取。这一点很像一个只能从“一端”进出的容器，另一端正对着地板，焊死了，碰都不能碰。明白这个概念，后面看代码就顺了。

2. 程序运行时为什么必须要一张栈：调用栈与递归深度

2.1 函数调用时栈帧是怎么一层层“摞”起来的

先看一个最简单的函数嵌套场景：

def fun_a(): print("A 开始") fun_b() print("A 结束") def fun_b(): print("B 开始") fun_c() print("B 结束") def fun_c(): print("C 执行")

当程序执行到 fun_a 里调用 fun_b 时，fun_a 不能直接结束，它还得等 fun_b 返回后继续执行那行“A 结束”。所以系统必须把 fun_a 当前执行到哪里、局部变量是什么、返回地址等信息记下来，然后再去执行 fun_b。这个“记下来”的动作，用的就是栈。

每一层函数调用，都会在内存中创建一个“栈帧”，里面放着该函数的参数、局部变量和返回地址。新的调用会把新栈帧压到栈顶，返回时再从栈顶弹出。整个过程完全符合后进先出：最后调用的函数，最先返回。这就是为什么“调用栈”这个概念无处不在，看日志时经常看到的堆栈信息，就是这些栈帧的层层展开。

你可以把函数调用想象成一队人进出隧道。第一个进隧道的人是 fun_a，它走到一半停下来，让 fun_b 先走；fun_b 又停下来，让 fun_c 先走；fun_c 走完出来后，fun_b 才接着走完，最后 fun_a 才走完全程。最先进入的 fun_a，反而是最后出去的。这就是调用栈的天然逻辑。

2.2 栈溢出不是玩笑：递归的深度陷阱

递归是栈最典型的“亲儿子”。比如算阶乘：

def fact(n): if n <= 1: return 1 return n * fact(n - 1)

当 n 等于 5 时，调用链会依次压入 fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。fact(1) 触底返回 1 后，才一层层弹出，最终得到结果。每个递归层级都对应一个栈帧，递归多深，栈就压多高。

但栈帧是有内存成本的。每个栈帧至少要保存局部变量、参数、返回地址。一旦递归层数过于夸张，比如处理一个超深层级的目录树，或者某些递归搜索算法本身没有剪枝，栈内存就会被打满。常见表现就是程序直接抛出栈溢出错误，甚至让整个进程崩溃。

我以前见过一个同学，用递归去扫描文件夹，没加深度限制。本地小目录测得好好的，一放到真实的项目目录上，几百层嵌套直接爆栈。后来改成显式栈做深度优先遍历，虽然内存占用变高了，但至少不再受线程栈大小限制。这个经验后面第 5 节会继续展开。

3. 自己动手实现一个栈：数组、链表与动态扩容

3.1 数组实现：代码最直观，读起来也最省心

用 Python 的 list 实现栈，是最简版本：

class ArrayStack: def __init__(self): self._items = [] def push(self, item): self._items.append(item) def pop(self): if self.is_empty(): raise IndexError("pop from empty stack") return self._items.pop() def peek(self): if self.is_empty(): raise IndexError("peek from empty stack") return self._items[-1] def is_empty(self): return len(self._items) == 0 def size(self): return len(self._items)

很多朋友觉得这代码太简单。确实简单，但简单才是优点。栈本来就是对容器做受限访问，语言内置的数组类型已经帮你处理好了底层扩容，我们只需要保证“只能从末尾存取”这个约束，不让别人乱插入、乱删除就行。

关键点是 pop 和 peek 前必须先检查是否为空。如果不检查，空栈直接取下标，轻则抛异常，重则在不同语言里产生未定义行为，调试起来非常头疼。

3.2 链表实现：不扩容、不搬运，代价是节点内存

有些场景不适合用数组，比如你不确定容量，又不想让数组扩容带来的“整体拷贝”影响到性能。这时候可以试试链表版栈：

class Node: def __init__(self, data): self.data = data self.next = None class LinkedStack: def __init__(self): self._head = None self._size = 0 def push(self, data): node = Node(data) node.next = self._head self._head = node self._size += 1 def pop(self): if self.is_empty(): raise IndexError("pop from empty stack") top_data = self._head.data self._head = self._head.next self._size -= 1 return top_data def peek(self): if self.is_empty(): raise IndexError("peek from empty stack") return self._head.data def is_empty(self): return self._head is None def size(self): return self._size

链表版栈把新的节点插到链表头部，栈顶就是链表的头节点。压栈时新节点指向旧的头节点，弹栈时头节点往后移一位。这样每次入栈出栈只需要改变两三个指针，不需要像数组那样担心扩容搬迁。

链表的代价也很明显：每个节点都多存了一个 next 指针，内存开销比纯数组大。如果数据本身是很小的整数，节点指针带来的额外内存占比会非常可观。所以该用数组版用数组版，该用链表版用链表版，不要迷信某一种实现。

3.3 动态扩容栈：从固定容量到自动增长的演化

真正生产环境里的栈，不是一上来就无限扩容的，而是一开始给一个固定容量，满了以后扩大数组容量。以 Python 的 list 为例，它内部就是那种动态数组的思路。我们也可以自己实现一版：

class DynamicStack: def __init__(self, initial_capacity=4): self._data = [None] * initial_capacity self._size = 0 self._capacity = initial_capacity def push(self, item): if self._size == self._capacity: self._resize(self._capacity * 2) self._data[self._size] = item self._size += 1 def pop(self): if self._size == 0: raise IndexError("pop from empty stack") self._size -= 1 result = self._data[self._size] self._data[self._size] = None if 0 < self._size <= self._capacity // 4: self._resize(self._capacity // 2) return result def peek(self): if self._size == 0: raise IndexError("peek from empty stack") return self._data[self._size - 1] def is_empty(self): return self._size == 0 def size(self): return self._size def _resize(self, new_capacity): new_data = [None] * new_capacity for i in range(self._size): new_data[i] = self._data[i] self._data = new_data self._capacity = new_capacity

扩容策略是容量翻倍，缩容策略是元素个数小于四分之一容量时缩到一半。为什么等到四分之一才缩？因为如果元素减到一半就缩，反复在临界点 push、pop，会产生大量不必要的扩容和缩容，引发性能抖动。这种“翻倍扩容、缩容留缓冲”的思路，在很多语言内置容器里都能看到。

理解动态扩容栈还有个额外好处：你能看懂为什么很多语言数组尾部 push 的时间复杂度是均摊 O(1)。虽然某一次扩容需要把旧数组全部复制一遍，但均摊到整个操作序列看，每次成本仍然很小。

4. 栈的两个高频实战场景：括号匹配与表达式求值

4.1 括号匹配：一道几乎每个平台都有的栈入门题

括号匹配大概是栈应用里最经典的题目。给定一个只包含()[]{}的字符串，判断括号是否合法。合法条件包括：括号必须同类型配对，配对顺序必须正确。

比如([])是合法的，([)]就不合法，因为右括号)的匹配对象应该是(，但中间被]隔断了。用栈解决起来非常自然：

def is_valid_brackets(s): pairs = { ')': '(', ']': '[', '}': '{' } left_set = set(pairs.values()) stack = [] for ch in s: if ch in left_set: stack.append(ch) else: if not stack: return False if stack.pop() != pairs[ch]: return False return len(stack) == 0

从左到右扫描。遇到左括号就压栈，遇到右括号就用这个右括号去和栈顶左括号配对。如果栈顶不是对应的左括号，或者栈已经空了，说明匹配失败。最后还要检查整条栈是否为空——如果栈里还有残留的左括号，说明有左括号没有对应的右括号闭合。

这里最容易踩的坑：只做了“遇到右括号时栈顶是否匹配”的判断，却忘了最后检查stack是否为空。比如输入"((("，你在循环里不会撞到任何 false 分支，最后如果直接返回True，那就是完全错误的结果。

4.2 中缀转后缀与后缀表达式求值：人脑算术与栈的配合

我们平时写3 + 4 * 5叫中缀表达式，运算优先级和括号都得靠人来理解。计算机解析中缀表达式没那么方便，所以编译器和计算器更喜欢把中缀转成后缀表达式，再借助栈求值。

后缀表达式也叫逆波兰表达式，运算符放在两个操作数后面：3 + 4 * 5会写成3 4 5 * +。求值过程不依赖优先级比较，只要有一个操作数栈：

def eval_postfix(tokens): stack = [] for token in tokens: if token.isdigit(): stack.append(int(token)) else: op2 = stack.pop() op1 = stack.pop() if token == '+': stack.append(op1 + op2) elif token == '-': stack.append(op1 - op2) elif token == '*': stack.append(op1 * op2) elif token == '/': stack.append(op1 / op2) return stack[-1]

运算规则是遇到数字直接压栈，遇到运算符连续弹出两个操作数，先弹出的作为右侧操作数，后弹出的作为左侧操作数。这个顺序非常关键。比如后缀表达式5 3 -，结果应该是 5 - 3 = 2。如果你把顺序搞反，先弹出的 3 当成 op1，后弹出的 5 当成 op2，就会算出 -2，整整差了一个符号。

表达式求值是栈“后进先出”特性最直观的体现，因为它天然对应了“运算时要找到最近的两个操作数”这个需求。做题遇到表达式相关问题时，第一反应就应该考虑：这里是不是可以维护一个栈，来保存最近扫描过的数据？

5. 进阶必看：单调栈与用栈改写的DFS

5.1 单调栈到底在单调什么：下一个更大元素

很多初学者见到“单调栈”三个字就害怕，其实它依然是栈，只是额外维护了栈内元素的有序性。最常见的场景是：给定一个数组，找到每个元素右边第一个比它大的元素。比如[2, 1, 2, 4, 3]，结果是[4, 2, 4, -1, -1]。

暴力做法是两层循环，数据量变大以后很容易超时。单调栈的做法可以只扫描一次：

def next_greater_element(arr): stack = [] result = [-1] * len(arr) for i in range(len(arr) - 1, -1, -1): while stack and stack[-1] <= arr[i]: stack.pop() if stack: result[i] = stack[-1] stack.append(arr[i]) return result

从右往左遍历时，栈里维护的是当前位置右边的候选元素，栈底到栈顶保持递减。为什么弹出<= arr[i]的元素？因为对更左边的位置来说，如果某个右边的数不大于当前arr[i]，那它既不会成为当前的“下一个更大元素”，也不会成为更左边的“下一个更大元素”。与其留着影响栈顶判断，不如直接弹出，让栈里的候选元素越来越精简。

这种“及时淘汰肯定不再有用的数据”的思维，就是单调栈的核心。它不只是用到栈，还用到了单调性，来优化淘汰规则。理解了这一点，后面遇到接雨水、直方图最大矩形这类题，思路会清晰很多。

5.2 用栈彻底拿掉递归：DFS的非递归写法

深度优先搜索（DFS）是算法题里的高频项目。平时写 DFS 大多数人直接用递归，代码短、可读性高。但递归有栈溢出风险，有时还要自己控制遍历顺序，改成显式栈会更稳：

def dfs_stack(start, graph): visited = set() stack = [start] while stack: node = stack.pop() if node in visited: continue visited.add(node) for neighbor in graph[node]: if neighbor not in visited: stack.append(neighbor)

这里栈替换的是系统调用栈，逻辑上的遍历顺序依然是“最新加入的节点优先访问”。为什么这不叫 BFS？因为 BFS 用的是队列，先进先出，节点按“层”扩展；而栈后进先出，会沿着一条路一直往下扎。把代码里的stack.append改成queue.append，再把pop()改成从左端出队，就是 BFS。两种遍历方式唯一的本质差别，就在于数据结构从栈变成了队列。

用显式栈写 DFS 时，有一个小坑需要注意：同一个节点可能因为多个邻居都把它入栈，所以入栈的时候没有阻止重复，出栈时才做 visited 判断并用continue跳过。另一种做法是在入栈时就标记 visited，减少无效节点入栈。两种都能用，但如果你既想在入栈时去重，又想保持某种遍历顺序，就需要认真设计入栈顺序，顺序反向也是常见问题。

6. 我在学习和教学里反复踩过的几个坑

6.1 边界条件：空栈和满栈往往比算法本身更致命

栈相关代码出 bug，十有八九出在边界上。空栈取栈顶、空栈弹栈、容量满时继续压栈，都是最容易翻车的地方。

我自己带人写题时，会反复强调三个检查点：

• 执行 pop 或 peek 之前，必须判断栈是否为空，尤其当输入数据里有大量右括号、减号这类“需要双操作数”的场景。
• 在模拟栈的题目里，如果题目明确说容量固定，push 时就要先检查栈是否已满，而不是傻等系统报错。
• 栈里如果存的是引用类型，pop 之后最好把数组对应位置的引用设为None，避免对象一直占着内存，尤其是长生命周期栈在 GC 前的内存占用。

第一个检查点很多人看得懂，第二个和第三个容易忽略。固定容量栈常见于嵌入式、驱动代码、以及面试里要求“不要用现成容器”的模拟题，一旦忽略限制，就会产生与预期不符的脏数据。引用类型清空，则涉及内存回收质量，生产环境里高并发场景尤其明显。

6.2 建议的学习节奏：先手写，再调库，最后看源码

栈的内容不算多，但想真正内化，我建议按三步走。

第一步，手写实现。至少写一版数组栈、一版链表栈，把 push、pop、peek、isEmpty、size 都实现一遍。写的时候刻意让栈在空栈时 pop，看错误是什么，理解各语言空数组访问的行为差异。

第二步，用语言自带的数据结构。Python 里直接用 list 的 append/pop，Java 里优先使用 Deque 而不是 Vector 等过时容器。把内置结构用顺手，再回到算法题，你能少被细节干扰，把注意力放在场景本身。

第三步，看一点标准库源码。不用全看懂，只看扩容策略、缩容策略、为什么不是每次 pop 都缩容，就够了。很多编程语言数组容器的实现，本质上就是你在第 3 节看到的动态栈思路。

然后再配套做 3 到 5 道经典题巩固：有效的括号、最小栈、用两个栈实现队列、下一个更大元素、二叉树迭代遍历。这些题覆盖了栈的基础操作、优化维护、结构组合和深度优先遍历，做完之后栈的基础就算彻底扎实了。

7. 最后再分享一点我的个人体会

栈这套东西，看起来只是限制了你“只能从一端进出”，可恰恰是这种限制，让很多模糊的直觉变成了可执行、可证明的算法。学习栈的过程中，我最大的感受是：一个数据结构有没有用，不看它的操作有多丰富，而看它能不能帮你把“回溯”“最近相关”“优先级嵌套”这类抽象问题，变成一行行清晰的 push 和 pop。

遇到递归不顺手，想想栈；遇到历史记录、表达式、嵌套匹配，也想想栈。甚至很多回溯算法，本质上都是“用一个看不见的系统栈在帮忙记忆”。把这篇栈入门基础详解里每个例子都亲手跑一遍，再回去看那些曾让你头疼的递归、DFS、表达式解析，你会发现自己多了一双看问题的眼睛。