栈和队列都是操作位置受到限制的线性表。栈遵循后进先出，适合保存尚未完成的上下文；队列遵循先进先出，适合按照到达顺序处理任务。理解它们的关键不仅是记住 LIFO 与 FIFO，还要掌握空满状态、底层实现和边界不变量。
1. 栈：后进先出
栈（Stack）只允许在栈顶插入和删除：
push：把元素压入栈顶；pop：删除栈顶元素；top/peek：读取但不删除栈顶元素；empty：判断栈是否为空。
最后入栈的元素最先出栈，因此称为 LIFO（Last In, First Out）。栈的另一端称为栈底。
2. 栈的实现选择
2.1 动态数组栈
用 data[0..size-1] 保存元素，size 同时表示有效元素数和下一个插入位置：
1
2
3
4
| 空栈：size == 0
栈顶：data[size - 1]
入栈：data[size++] = value
出栈：--size
|
数组栈遍历和访问栈顶的缓存局部性好，绝大多数操作不需要单独分配节点。尾部入栈的均摊复杂度为 $O(1)$，出栈和取栈顶为 $O(1)$。
2.2 链式栈
把链表头部作为栈顶，头插和头删均为 $O(1)$。链式栈不需要整体扩容，但每个节点需要指针字段，并产生动态分配开销。
3. 一份可运行的动态数组栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
typedef struct {
int *data;
size_t size;
size_t capacity;
} Stack;
static void stack_init(Stack *s)
{
assert(s != NULL);
s->data = NULL;
s->size = 0;
s->capacity = 0;
}
static bool stack_push(Stack *s, int value)
{
assert(s != NULL);
if (s->size == s->capacity) {
size_t next = s->capacity == 0 ? 4 : s->capacity * 2;
if (next < s->capacity || next > SIZE_MAX / sizeof(*s->data)) {
return false;
}
int *data = realloc(s->data, next * sizeof(*data));
if (data == NULL) {
return false;
}
s->data = data;
s->capacity = next;
}
s->data[s->size++] = value;
return true;
}
static bool stack_pop(Stack *s, int *out)
{
assert(s != NULL && out != NULL);
if (s->size == 0) {
return false;
}
*out = s->data[--s->size];
return true;
}
static bool stack_top(const Stack *s, int *out)
{
assert(s != NULL && out != NULL);
if (s->size == 0) {
return false;
}
*out = s->data[s->size - 1];
return true;
}
static void stack_destroy(Stack *s)
{
assert(s != NULL);
free(s->data);
s->data = NULL;
s->size = 0;
s->capacity = 0;
}
int main(void)
{
Stack s;
int value = 0;
stack_init(&s);
assert(stack_push(&s, 10));
assert(stack_push(&s, 20));
assert(stack_top(&s, &value) && value == 20);
assert(stack_pop(&s, &value) && value == 20);
assert(stack_pop(&s, &value) && value == 10);
assert(!stack_pop(&s, &value));
puts("stack ok");
stack_destroy(&s);
return 0;
}
|
接口使用 bool 表示成功与否，并通过输出参数返回数据，从而避免用某个特殊整数表示“空栈”。
4. 栈的典型应用
4.1 函数调用与递归
调用函数时，运行时栈保存返回地址、参数、局部变量等上下文。递归深度过大可能耗尽调用栈，因此可以在必要时用显式栈把递归改写为迭代。
4.2 括号匹配
扫描表达式：
- 遇到左括号就入栈；
- 遇到右括号时，栈不能为空且栈顶必须是对应左括号；
- 扫描结束后栈必须为空。
时间复杂度 $O(n)$，额外空间最坏为 $O(n)$。
4.3 表达式求值
中缀表达式可以借助运算符栈转换为后缀表达式；计算后缀表达式时，遇到操作数就入栈，遇到运算符就弹出所需操作数并把结果压回栈。
4.4 深度优先搜索与回溯
DFS 总是沿一条路径深入，遇到死路再退回最近的分叉点，这种“最后进入的状态最先恢复”的行为天然适合栈。
5. 队列：先进先出
队列（Queue）只允许在队尾插入、队头删除：
enqueue/push：从队尾入队；dequeue/pop：从队头出队；front：读取队头；back：读取队尾。
最先入队的元素最先出队，因此称为 FIFO（First In, First Out）。
6. 链式队列
使用单链表并同时维护队头、队尾指针，可以让入队和出队都达到 $O(1)$。
关键不变量：
1
2
| 空队列：front == NULL && rear == NULL
非空队列：front != NULL && rear != NULL && rear->next == NULL
|
完整实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct QueueNode {
int value;
struct QueueNode *next;
} QueueNode;
typedef struct {
QueueNode *front;
QueueNode *rear;
size_t size;
} Queue;
static void queue_init(Queue *q)
{
assert(q != NULL);
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
static bool queue_push(Queue *q, int value)
{
assert(q != NULL);
QueueNode *node = malloc(sizeof(*node));
if (node == NULL) {
return false;
}
node->value = value;
node->next = NULL;
if (q->rear == NULL) {
q->front = node;
} else {
q->rear->next = node;
}
q->rear = node;
++q->size;
return true;
}
static bool queue_pop(Queue *q, int *out)
{
assert(q != NULL && out != NULL);
if (q->front == NULL) {
return false;
}
QueueNode *node = q->front;
*out = node->value;
q->front = node->next;
free(node);
--q->size;
if (q->front == NULL) {
q->rear = NULL;
}
return true;
}
static void queue_destroy(Queue *q)
{
assert(q != NULL);
int ignored = 0;
while (queue_pop(q, &ignored)) {
}
}
int main(void)
{
Queue q;
int value = 0;
queue_init(&q);
assert(queue_push(&q, 1));
assert(queue_push(&q, 2));
assert(queue_pop(&q, &value) && value == 1);
assert(queue_pop(&q, &value) && value == 2);
assert(q.front == NULL && q.rear == NULL && q.size == 0);
queue_destroy(&q);
puts("queue ok");
return 0;
}
|
7. 循环队列
普通数组队列如果每次出队都移动剩余元素，成本为 $O(n)$。循环队列让头尾下标在数组末端“绕回”开头：
1
2
| rear = (rear + 1) % capacity;
front = (front + 1) % capacity;
|
7.1 如何区分空与满
如果只维护 front 和 rear，二者相等既可能表示空，也可能表示满。常见方案有三种：
- 牺牲一个槽位：空为
front == rear，满为 (rear + 1) % capacity == front，实际容量是 capacity - 1；
- 维护元素个数
size：空为 size == 0，满为 size == capacity，可使用全部槽位；
- 维护额外状态位：记录最后一次操作或单独的满标志。
讨论循环队列容量时必须先说明采用哪种约定，否则“数组长度”和“可存元素数”可能相差 1。
7.2 使用 size 的核心状态
1
2
3
4
5
6
| typedef struct {
int *data;
size_t capacity;
size_t front;
size_t size;
} RingQueue;
|
队尾下标可以由 (front + size) % capacity 计算。入队和出队均为 $O(1)$，而且全部数组槽位都可使用。
8. 队列的典型应用
- 操作系统和服务端的任务调度；
- 消息缓冲与生产者—消费者模型；
- 网络数据包排队；
- 打印任务；
- 二叉树层序遍历；
- 无权图的广度优先搜索与最短路。
普通 FIFO 队列保证的是到达顺序；如果要优先处理更重要的任务，应使用优先队列，而不是普通队列。
9. 栈与队列互相模拟
9.1 两个栈实现队列
一个栈负责接收入队元素，另一个栈负责出队。出队栈为空时，把入队栈的全部元素倒入出队栈。每个元素最多在两个栈之间移动一次，因此操作的均摊复杂度为 $O(1)$。
9.2 两个队列实现栈
入栈时把新元素放入空队列，再把原队列中的元素依次转移到它后面；或者让入栈保持 $O(1)$、在出栈时搬移。无论哪种策略，至少一类操作需要 $O(n)$。
10. 常见错误与测试清单
- 空栈仍访问
data[size - 1]，造成下标下溢；
- 固定容量栈没有检查上溢；
- 链式队列删除最后一个节点后留下悬空
rear；
- 循环队列取模时
capacity == 0；
- 混淆
rear 指向最后一个元素还是下一个可写位置；
- 销毁结构后没有把指针和状态重置；
- 用断言处理可恢复的外部输入错误，而不是返回状态。
至少应测试空结构、单元素、容量边界、绕回、反复入队出队、连续扩容和销毁后状态。只要空满判定与下标含义始终保持一致，栈与队列的实现就会清晰很多。
