栈：为什么你的代码能“撤销”？从原理到手写实现

栈（Stack）：为什么你的代码能"撤销"？

前言

你写过这样的代码吗？

printf("A");
fork();

你以为输出一个 A，结果蹦出两个。为什么？因为 printf 的数据躲在缓冲区里，而 fork 把它复制了一份。这个"隐身副本"的幕后推手，就是一个叫栈的数据结构。

栈是最简单的数据结构，没有之一。但正是这个"最简单"的结构，支撑着函数调用、表达式求值、浏览器后退、编辑器撤销……你日常用的每一个功能，底层都有它的身影。

本篇不堆概念，直接从你手写的 Stack.c 出发，边看代码边理解栈的每一个设计决策。

环境：C99 / GCC 11.4 / x86_64 Linux

📋 目录

• 一、栈是什么？一摞盘子就够了
• 二、为什么计算机离不开栈？
• 三、我的栈：动态数组 + 自动扩容
• 四、入栈：扩容的"小心机"
• 五、出栈：不释放内存的聪明做法
• 六、四种数据结构大乱斗
• 七、踩过的坑
• 八、总结

一、栈是什么？一摞盘子就够了

栈（Stack）就一件事：后进先出（LIFO）。

生活里最像栈的东西是什么？一摞盘子。你只能从最上面放盘子，也只能从最上面拿盘子。最先放上去的盘子，被压在最底下，最后才能拿到。

放盘子：10 → 20 → 30 → 50（最后放）
┌─────┐ ← 栈顶（最新）
│ 50 │
├─────┤
│ 30 │
├─────┤
│ 20 │
├─────┤
│ 10 │ ← 栈底（最早）
└─────┘
拿盘子：先拿 50，再 30，再 20，最后 10

栈只有五个动作：

💡 一句话：栈就是"只能从顶部操作"的列表，所有操作都是 O(1)。

二、为什么计算机离不开栈？

栈看起来简单，但它在计算机里无处不在。来看看几个你可能每天都在用的场景：

函数调用栈的"幕后故事"：

假设你的代码是这样的：

void bar() { int c = 3; }
void foo() { bar(); }
int main() { int a = 1; foo(); }

当 bar() 正在执行时，内存里的栈长这样：

┌─────────────────────┐ ← 栈顶（最新）
│ bar 的栈帧 │ ← 局部变量 c=3
├─────────────────────┤
│ foo 的栈帧 │ ← 返回地址
├─────────────────────┤
│ main 的栈帧 │ ← 局部变量 a=1
└─────────────────────┘ ← 栈底

bar() 执行完 → 弹栈 → 回到 foo() → foo() 结束 → 弹栈 → 回到 main()。

这就是栈在操作系统层面最核心的角色：维护调用上下文。每次函数调用 = 压栈，每次返回 = 弹栈。

💡 小结：栈的价值在于"维护上下文"。函数调用、撤销操作、括号匹配……所有需要"记住之前做过什么"的场景，本质上都是栈。

三、我的栈：动态数组 + 自动扩容

我实现的栈基于动态数组，核心就三个字段：

typedef struct {
DataType* data; // 指向动态数组的指针
int size; // 当前有多少个元素
int capacity; // 当前数组总共能放多少个
} Stack;

内存长什么样？

capacity=4, size=0（刚初始化，空空如也）
data ──→ ┌─────┬─────┬─────┬─────┐
│ │ │ │ │
└─────┴─────┴─────┴─────┘
↑
size=0（下一个插入位置）

capacity=4, size=3（放了 10、20、30）
data ──→ ┌─────┬─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ │
└─────┴─────┴─────┴─────┘
↑ ↑
size=3 capacity=4（还能塞1个）

初始化：申请第一块地

ErrorCode StackInit(Stack* stack) {
if (NULL == stack) return ERR_INVALID_PARAM;
stack->capacity = INIT_CAPACITY;
stack->size = 0;
stack->data = malloc(sizeof(DataType) * stack->capacity);
if (stack->data == NULL) return ERR_MALLOC;
return SUCCESS;
}

就三件事：设容量、设大小为 0、申请内存。C 语言数据结构的标准起手式。

销毁：干干净净地走

ErrorCode StackDestroy(Stack* stack) {
if (NULL == stack) return ERR_INVALID_PARAM;
free(stack->data);
stack->data = NULL;
stack->capacity = 0;
stack->size = 0;
return SUCCESS;
}

释放内存 → 指针置 NULL → 归零。防止悬空指针的经典操作。

💡 小结：栈的底层就是动态数组。data 指向内存，size 记录用了多少，capacity 记录总共多大。当 size == capacity 时，就要扩容了。

四、入栈：扩容的"小心机"

入栈本身很简单——把数据放到 size 位置，然后 size++。但问题来了：数组满了怎么办？

我的做法是两倍扩容：

static ErrorCode EnsureEnoughSpace(Stack* stack) {
if (stack->capacity == stack->size) {
int new_capacity = stack->capacity * 2;
DataType* tmp = realloc(stack->data, new_capacity * sizeof(DataType));
if (tmp == NULL) {
LOG("申请空间失败");
return ERR_MALLOC;
}
stack->data = tmp;
stack->capacity = new_capacity;
}
return SUCCESS;
}

ErrorCode StackPush(Stack* stack, DataType val) {
if (NULL == stack) return ERR_INVALID_PARAM;
ErrorCode ret = EnsureEnoughSpace(stack);
if (ret != SUCCESS) return ret;
stack->data[stack->size] = val; // 插入
stack->size++; // 大小+1
return SUCCESS;
}

扩容全过程可视化：

阶段1: capacity=4, size=0（空的）
┌─────┬─────┬─────┬─────┐
│ │ │ │ │
└─────┴─────┴─────┴─────┘

阶段2: push(10)(20)(30)(40) 后，size=4，满了
┌─────┬─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ 40 │ ← 下次 push 触发扩容！
└─────┴─────┴─────┴─────┘

阶段3: push(50) → realloc 扩容 4→8
旧数组 ──→ 拷贝数据 ──→ 新数组（capacity=8）
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │ │ │ │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

阶段4: capacity=8, size=5，继续 push…

为什么用 realloc 而不是 malloc + memcpy？

realloc 会先尝试在原内存块后面直接扩展，如果后面有空位就不需要拷贝数据，一步到位。只有没空间时才会分配新块并拷贝。我的代码用 realloc 一步完成"申请+拷贝+释放旧空间"。

两倍扩容为什么不是三倍、四倍？

• 扩太少（+1）：频繁扩容，总复杂度变成 O(n²)
• 扩太多（×10）：浪费内存
• 扩两倍：摊还复杂度 O(1)，内存浪费可控——中庸之道

💡 小结：入栈的核心不是"放进去"，而是"满了怎么办"。两倍扩容 + realloc 是经典组合拳，摊还 O(1) 的同时控制内存浪费。

五、出栈：不释放内存的聪明做法

出栈更简单——size– 就行了。

ErrorCode StackPop(Stack* stack) {
if (NULL == stack) return ERR_INVALID_PARAM;
if (StackIsEmpty(stack)) return ERR_DATA_NOT_EXISTS;
stack->size—; // 关键：只做逻辑删除
return SUCCESS;
}

注意：我没有 free 内存！只是把 size 减 1，相当于"逻辑删除"。

出栈前:
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │ │
└─────┴─────┴─────┴─────┴─────┴─────┘
↑ ↑
size=5 capacity=6

StackPop() → size–

出栈后:
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │ │ ← 50 变成"垃圾数据"
└─────┴─────┴─────┴─────┴─────┴─────┘
↑ ↑
size=4 capacity=6

下次 push(60) 会直接覆盖 50 的位置:
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ 40 │ 60 │ │ ← 60 覆盖了 50
└─────┴─────┴─────┴─────┴─────┴─────┘

为什么不 free 内存？

因为下次 push 会直接复用这块空间。如果每次 pop 都 free，下次 push 又要 malloc，来回分配释放的开销比留着内存大得多。这是空间换时间的经典策略。

当然，如果你真的想释放内存，可以在 size 降到 capacity 的一半时触发缩容（类似扩容但方向相反）。不过我的实现里没有做，保持简洁。

判空和获取大小：

bool StackIsEmpty(const Stack* stack) {
if (NULL == stack) return false;
return stack->size == 0;
}

int StackSize(const Stack* stack) {
if (NULL == stack) return 0;
return stack->size;
}

💡 小结：出栈不做物理删除，只做 size–。这是性能优化的常见技巧——用一点闲置内存换取避免频繁分配释放的开销。

六、四种数据结构大乱斗

前面我写了四个数据结构：栈（Stack）、双端队列（Deque）、普通队列（NormalQueue）、循环队列（RingQueue）。它们各有所长，来看看怎么选：

核心特性对比

一句话选型

四种结构优缺点一览

栈：

• ✅ 实现最简单，所有操作 O(1)，内存连续缓存友好
• ❌ 只能访问栈顶，扩容需拷贝，出栈不释放内存

双端队列：

• ✅ 两端操作都是 O(1)，块级管理减少碎片
• ❌ 实现复杂，指针操作容易出错

普通队列：

• ✅ 代码复用高，实现简单
• ❌ 出队 O(n)，效率低

循环队列：

• ✅ 入队出队都是 O(1)，固定内存零分配
• ❌ 容量固定，牺牲一个位置，取模有开销

💡 小结：没有最好的数据结构，只有最合适的。栈适合嵌套回溯，双端队列适合两端操作，普通队列适合快速开发，循环队列适合高性能缓冲。理解每种结构的代价，才能做出正确的选型。

七、踩过的坑

八、总结