栈 Stack

数据结构 · 后进先出的线性表

什么是栈

栈是一种只能在一端操作的线性表。这一端叫栈顶，另一端是栈底。所有的添加和删除都只发生在栈顶——你没法从中间或底部插手。

往栈顶放一个元素叫 push（压入），从栈顶拿走一个叫 pop（弹出），只看一眼栈顶而不拿走叫 peek。因为进出都在同一端，最后压进去的元素一定最先被弹出——这就是后进先出（LIFO，Last In First Out）。

亲手试试

栈为空

点 push 压入一个元素试试

试试连压 1、2、3，再连弹两次——最先出来的是 3，最后压进去的最先出来。无论栈里有多少元素，push 和 pop 都只动栈顶那一个，所以它们的时间复杂度都是 O(1)。

栈最经典的身影是函数调用栈：每调用一个函数就 push 一个栈帧，函数返回就 pop 掉——所以最后被调用的函数最先返回。此外还有：

撤销操作：每步操作压栈，Ctrl+Z 就是弹栈回到上一步。
括号匹配：遇到左括号压栈，遇到右括号弹栈配对，栈空则匹配成功。
浏览器后退：每访问一个页面压栈，后退就是弹栈。

往下还会接着讲队列——和栈相反，它是先进先出（FIFO），从一端进、另一端出。