栈（Stack）详解：概念、实现与避坑指南

1. 栈的基本概念

栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作。这一端称为栈顶（Top），另一端称为栈底（Bottom）。栈遵循 后进先出（LIFO，Last In First Out）的原则。

• 压栈（Push）：在栈顶插入元素

• 出栈（Pop）：从栈顶删除元素

生活中的类比：叠盘子。新盘子总是放在最上面，取盘子也是从最上面先取。后放的盘子先被取走。

示意图：

压栈方向 →
┌───┐
│ 5 │ ← 栈顶
├───┤
│ 4 │
├───┤
│ 3 │
├───┤
│ 2 │
├───┤
│ 1 │
└───┘
栈底

2. 栈的底层结构选型

栈可以用数组或链表实现，两者各有特点：

为什么通常选择数组？
因为栈的操作都在尾部进行，数组在尾部插入/删除的代价非常小（无需移动其他元素），而且连续内存对 CPU 缓存友好。链表则需要额外的指针存储开销。因此，绝大多数栈的实现都采用动态数组。

3. 栈的实现（C语言）

下面我们以动态数组的方式实现一个通用的栈。代码分为三个文件：Stack.h（声明）、Stack.c（定义）、test.c（测试）。

3.1 结构体定义（Stack.h）

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// 栈存储的数据类型，可根据需要修改
typedef int STDataType;

// 栈结构体
typedef struct Stack
{
STDataType* arr; // 动态数组指针
int top; // 栈顶指针（指向下一个要插入的位置）
int capacity; // 当前数组的总容量
} ST;

// 函数声明
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);

关键点说明：

• arr：指向动态分配的数组内存。

• top：指向下一个待插入的位置。当栈为空时，top = 0。栈中有效元素的下标范围是 [0, top-1]。

• capacity：数组的当前容量，当 top == capacity 时表示数组已满，需要扩容。

3.2 初始化（StackInit）

void StackInit(ST* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}

• 将 arr 置为 NULL，此时未分配任何内存。

• top 和 capacity 都初始化为 0。

为什么 top 初始为 0 而不是 -1？
这是一种常见的设计选择。top 表示下一个空位置的下标，这样栈空时 top == 0，栈中元素个数恰好等于 top，非常直观。如果 top 指向栈顶元素，则栈空时需要 top = -1，元素个数为 top+1，容易引起混淆。

3.3 销毁（StackDestroy）

void StackDestroy(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}

• 如果 arr 非空，释放内存。

• 将指针置为 NULL，并将 top 和 capacity 归零，防止悬空指针被误用。

坑点：调用 free(ps->arr) 后，ps->arr 仍指向已被释放的内存（野指针）。务必将其置为 NULL，否则后续对 ps->arr 的判空可能导致错误。

3.4 入栈（StackPush）

void StackPush(ST* ps, STDataType x)
{
assert(ps); // 确保 ps 非空
if (ps->top == ps->capacity) // 空间不足，需要扩容
{
// 新容量：原容量为0时给4，否则翻倍
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x; // 放入元素，然后 top 自增
}

流程图：

开始
│
▼
断言 ps 不为空
│
▼
top == capacity ?
│
├─ 否 ──→ 直接放入元素 arr[top++] = x ──→ 结束
│
└─ 是 ──→ 计算新容量
│
▼
realloc 扩容
│
├─ 失败 ──→ 打印错误并退出程序
│
└─ 成功 ──→ 更新 arr 和 capacity
│
▼
放入元素

重点解释：

入栈过程示意图：

初始：capacity=4, top=0, arr 指向一块内存
┌───┬───┬───┬───┐
│ │ │ │ │
└───┴───┴───┴───┘
↑
top

Push 1: arr[0]=1, top=1
┌───┬───┬───┬───┐
│ 1 │ │ │ │
└───┴───┴───┴───┘
↑
top

Push 2: arr[1]=2, top=2
┌───┬───┬───┬───┐
│ 1 │ 2 │ │ │
└───┴───┴───┴───┘
↑
top

… 继续 Push 3,4
┌───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │
└───┴───┴───┴───┘
↑
top (此时 top == capacity)
Push 5: 触发扩容，capacity 变为 8
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
↑
top (5)

3.5 出栈（StackPop）

void StackPop(ST* ps)
{
assert(!StackEmpty(ps)); // 栈不能为空
–ps->top; // 直接让 top 减一
}

• 出栈只需将 top 减一，逻辑上元素就被“删除”了。实际上数组中的旧值仍然存在，但后续入栈会覆盖它。

• 必须确保栈非空，否则对空栈执行 Pop 会导致 top 变成 -1，后续操作会越界。

为什么不真正 free 内存？
栈顶指针下移后，原来占用的空间仍属于数组的已分配内存，后续入栈时可以直接复用，避免了频繁的内存分配/释放，提升效率。

3.6 取栈顶元素（StackTop）

STDataType StackTop(ST* ps)
{
assert(!StackEmpty(ps));
return ps->arr[ps->top – 1]; // 栈顶元素下标是 top-1
}

• 只读取，不删除。

• 同样需要断言栈非空。

3.7 获取栈中元素个数（StackSize）

int StackSize(ST* ps)
{
return ps->top;
}

• 因为 top 正好表示元素个数，直接返回即可。

3.8 栈是否为空（StackEmpty）

bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}

3.9 完整代码汇总（Stack.c）

#include "Stack.h"

void StackInit(ST* ps)
{
ps->arr = NULL;
ps->top = ps->capacity = 0;
}

void StackDestroy(ST* ps)
{
if (ps->arr)
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}

bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}

void StackPop(ST* ps)
{
assert(!StackEmpty(ps));
–ps->top;
}

STDataType StackTop(ST* ps)
{
assert(!StackEmpty(ps));
return ps->arr[ps->top – 1];
}

int StackSize(ST* ps)
{
return ps->top;
}

4. 测试代码及使用示例

#include "Stack.h"

void test01()
{
ST st;
StackInit(&st);

StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPush(&st, 5);

printf("size: %d\\n", StackSize(&st)); // 输出 5

// 依次弹出并打印所有元素
while (!StackEmpty(&st))
{
int top = StackTop(&st);
printf("%d ", top);
StackPop(&st);
}
// 输出 5 4 3 2 1 （后进先出）

StackDestroy(&st);
}

int main()
{
test01();
return 0;
}

输出：

size: 5
5 4 3 2 1

5. 常见坑点与避坑指南

6. 栈的应用场景

• 函数调用栈：保存函数返回地址、局部变量。

• 表达式求值：中缀转后缀、计算器实现。

• 括号匹配：LeetCode 经典题目（有效的括号）。

• 撤销操作（Undo）：编辑器中的撤销栈。

• 浏览器的后退功能：每次访问页面入栈，后退即出栈。

7. 复杂度总结

8. 扩展：链式栈的简单对比

如果使用链表实现栈，通常采用头插法（让头结点作为栈顶），这样入栈和出栈都是 O(1)。但需要额外的 next 指针，且每个节点单独分配内存，缓存局部性较差。代码结构大致如下：

typedef struct StackNode {
STDataType data;
struct StackNode* next;
} StackNode;

typedef struct LinkedStack {
StackNode* top;
int size;
} LinkedStack;

不过，在绝大多数场景下，动态数组实现的顺序栈是更优的选择。

总结：栈是一种简单但极其重要的数据结构。掌握它的数组实现，不仅要理解其逻辑，还要注意内存管理、边界条件等细节。希望本文能帮助你彻底搞懂栈的原理与实现。如果有任何疑问，欢迎留言讨论！