栈
最后更新
栈是只有一个开口的集合。添加值叫入栈（push），把它放到栈顶；删除值叫出栈（pop），把栈顶的值取下来。所以最后进去的值总是最先出来。这就是后进先出（LIFO）的含义，也是栈唯一的规则：不先拿走上面的东西，就无法碰到中间的元素。点击上方的“播放”，观看这一列随着每次入栈变高，又随着每次出栈从同一端变矮。
这种限制正是栈的意义所在。因为两种操作都只涉及栈顶，所以无论栈有多高，每个操作都是 O(1)。正是这种可预测性，让栈成为计算机中无处不在的基础：运行递归的调用栈、编辑器的撤销历史、解析器中的括号匹配，以及把递归的深度优先搜索改写成循环时用到的显式栈。把删除的一端换到另一头，你得到的就是队列。
时间复杂度与空间复杂度
以下是基于数组或链表实现的标准栈：
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 入栈（push） | O(1) | 在动态数组上是均摊 O(1)，因为偶尔需要扩容。 |
| 出栈（pop） | O(1) | 总是取栈顶元素，不需要移动其他元素。 |
| 查看栈顶（peek） | O(1) | 读取栈顶的值，但不删除它。 |
| 查找 | O(n) | 这不是栈的用途：你只能一路出栈往下找。 |
| 空间 | O(n) | 每个存储的值占一个位置。 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 栈一开始是空的，栈顶不指向任何元素。 |
| 2 | 入栈时把值写到栈顶位置，然后栈顶上移一位。 |
| 3 | 之后每次入栈，新值都直接放在前一个值的上面。 |
| 4 | 出栈时读取栈顶的值，然后栈顶下移一位。 |
| 5 | 取出的值永远是最近一次入栈的那个。 |
| 6 | 对空栈执行出栈是一种错误，叫作栈下溢，所以实际代码会先检查 is_empty()。 |
实例演示
依次把 3、7、5 入栈，然后把栈清空：
| 操作 | 栈（从栈底到栈顶） | 返回值 |
|---|---|---|
push(3) | [3] | 无 |
push(7) | [3, 7] | 无 |
push(5) | [3, 7, 5] | 无 |
pop() | [3, 7] | 5，最新加入的值 |
pop() | [3] | 7 |
pop() | [] | 3，最早加入的值，最后取出 |
什么时候用栈
Stack 代码
简洁、可运行的 Stack 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Stack 的 Python 代码
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)Stack 的 JavaScript 代码
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Stack 的 Java 代码
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}Stack 的 C++ 代码
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}Stack 的 C 代码
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}栈常见问题
LIFO 是什么意思？
后进先出（Last In, First Out）：最近入栈的值最先出栈。常见的比喻是一摞盘子，你拿走的是刚放上去的那个，而不是最底下的。队列则遵循相反的规则，即先进先出（FIFO）。
栈和队列有什么区别？
区别只在于从哪一端删除。两者都以
O(1) 在一端添加；栈从同一端删除（LIFO），队列从另一端删除（FIFO）。除此之外的一切，包括上面的复杂度表，都完全相同。栈有哪些主要操作？
push 把一个值放到栈顶，pop 删除并返回栈顶的值，peek（有时叫 top）读取栈顶但不删除，is_empty 判断栈里是否还有元素。这四个操作都是 O(1)。栈溢出是什么？
就是往一个已经没有空间的栈里继续入栈。最有名的例子是调用栈：每次函数调用都会压入一个栈帧，所以一个永远到不了基线条件的递归会不停入栈，直到超出运行时的栈限制，程序崩溃。与之相对的错误是对空栈出栈，叫作栈下溢。
栈是怎么实现的？
常见的方式有两种。动态数组在末尾入栈和出栈，均摊
O(1)，而且缓存友好：Python 的 list 和 Java 的 ArrayDeque 就是这样工作的。链表在头部入栈和出栈，最坏情况也是 O(1)，不需要扩容，但每个元素要多占一个指针。C++ 的 std::stack 是一个适配器，默认基于分段数组 std::deque 运行，你也可以传入别的容器。相关资源
更多可视化
