第三章栈、队列与受限线性结构

📖 ⏱️ 预计阅读时长

1. 栈

栈是一种后进先出（LIFO, Last In First Out）的线性结构。栈只允许在一端进行插入和删除，这一端称为栈顶，另一端称为栈底。

与普通线性表相比，栈的最大特征在于访问规则受限。用户不能随意访问中间元素，而只能围绕栈顶进行操作。正是这种“看似受限”的设计，使栈非常适合描述一层套一层的处理过程。

1.1 栈的基本操作

push：入栈。
pop：出栈。
top 或 peek：读取栈顶元素但不删除。
isEmpty：判断是否为空栈。

1.2 栈的典型应用

函数调用与递归。
表达式求值与括号匹配。
撤销操作、回溯搜索、深度优先遍历。

函数调用为什么能“调用结束后回到原位置继续执行”，本质上就是因为系统运行时把返回地址、局部变量和现场信息压入了调用栈。

从抽象角度看，栈适合描述“最近进入的状态，最先需要处理”的问题。凡是具有明显嵌套关系的问题，例如括号嵌套、函数嵌套、表达式嵌套、回溯搜索中的路径回退，本质上都符合后进先出的规律，因此自然适合用栈表示。

2. C 语言示例：顺序栈

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void init_stack(Stack *s) {
    s->top = -1;
}

int push(Stack *s, int value) {
    if (s->top == MAX_SIZE - 1) {
        return 0;
    }
    s->data[++s->top] = value;
    return 1;
}

int pop(Stack *s, int *value) {
    if (s->top == -1) {
        return 0;
    }
    *value = s->data[s->top--];
    return 1;
}

int main(void) {
    Stack s;
    int x;
    init_stack(&s);
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    if (pop(&s, &x)) {
        printf("%d\n", x);   /* 输出：3 */
    }
    return 0;
}

当栈采用数组实现时，入栈和出栈通常都是 O(1)。这也是栈成为基础运行时结构的重要原因。

之所以能够保持常数级时间，是因为栈只在一端进行操作，不需要像普通线性表那样处理中间位置元素。换言之，栈的高效并不是来自“结构更神秘”，而是来自“规则更严格”。正因为限制了使用方式，才换来了操作上的简单和稳定。

3. 队列

队列是一种先进先出（FIFO, First In First Out）的线性结构。插入通常在队尾进行，删除通常在队头进行。

现实生活中的排队现象是理解队列最直观的例子。先到的人先处理，后到的人后处理。操作系统中的任务调度、消息系统中的请求缓冲、打印任务的等待队列，都体现了这种思想。

队列尤其适合描述“按到达顺序处理任务”的问题。当系统希望保证公平性，或者希望按时间先后来消费事件时，队列就会成为天然选择。许多消息中间件、任务队列系统和网络数据缓冲区，都是这一思想在工程中的体现。

3.1 队列的典型应用

操作系统中的任务调度。
打印任务排队。
缓冲区管理。
图的广度优先遍历。

3.2 顺序队列与“假溢出”

如果用普通数组实现队列，当队头不断后移时，即使前面出现空位，也可能因为队尾到达数组末端而无法继续入队，这种现象称为“假溢出”。

为解决这个问题，常采用循环队列。循环队列把数组逻辑上看作一个首尾相接的环，从而提高存储空间利用率。

循环队列的设计之所以合理，是因为队列只关心“逻辑上的前后次序”，并不要求元素在数组中永远向一个方向线性推进。只要队头和队尾的相对关系保持正确，物理位置回绕并不会破坏队列语义。这个例子非常适合说明：数据结构设计并不是机械照搬现实对象，而是对现实规则进行抽象后的高效实现。

4. C 语言示例：循环队列

#include <stdio.h>

#define MAX_SIZE 6

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

void init_queue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

int is_empty(Queue *q) {
    return q->front == q->rear;
}

int is_full(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

int enqueue(Queue *q, int value) {
    if (is_full(q)) {
        return 0;
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return 1;
}

int dequeue(Queue *q, int *value) {
    if (is_empty(q)) {
        return 0;
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return 1;
}

int main(void) {
    Queue q;
    int x;
    init_queue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    dequeue(&q, &x);
    printf("%d\n", x);   /* 输出：10 */
    return 0;
}

5. 双端队列与优先队列

5.1 双端队列

双端队列（Deque）允许在队头和队尾两端都进行插入和删除。它结合了栈和队列的部分特点，适合实现滑动窗口、单调队列等结构。

5.2 优先队列

优先队列不是按进入顺序出队，而是按照优先级规则取出元素。其典型实现是堆。操作系统调度、最短路径算法、任务管理等都广泛使用优先队列。

优先队列的本质在于“顺序由优先级决定，而不是由时间决定”。这一点与普通队列构成根本区别。

5.3 栈和队列为何高频出现在算法题中

这是因为很多问题本身就带有明显的访问规则。例如：

遇到最近进入、最先回退的问题，往往对应栈。
遇到按层推进、先来先处理的问题，往往对应队列。
遇到需要动态维护最大值或最小值优先处理的问题，往往对应优先队列。

因此，判断何时使用栈和队列，本质上是在识别问题的“访问顺序约束”。

5.4 为什么栈和队列被称为“受限线性结构”

普通线性表允许在任意合法位置访问、插入和删除，而栈和队列只允许在特定端点执行操作，因此它们比线性表“自由度更低”。但这种限制并不是缺陷，反而是一种对问题规律的主动利用。很多时候，正因为只允许少数操作，程序的逻辑才会更清晰，复杂度才会更稳定。

6. 栈与队列的比较

6.1 共性

栈和队列都属于线性结构，也都属于受限访问结构。它们都不允许像普通线性表那样任意位置插入和删除。

6.2 差异

栈强调后进先出，适合嵌套与回退。
队列强调先进先出，适合调度与排队。

理解这一区别后，很多算法中的结构选择就会变得自然。例如 DFS 常配合栈，BFS 常配合队列。

7. 本章小结

栈和队列并不是“功能更少”的线性表，而是“规则更强”的线性表。正因为访问规则明确，它们在表达递归、调度、回溯、缓冲和图遍历等问题时具有很高效率。学习本章时，应特别注意三点：第一，理解 LIFO 与 FIFO 的本质差异；第二，掌握顺序实现与循环实现思想；第三，能根据问题特征判断究竟应该使用栈还是队列。

第三章 栈、队列与受限线性结构 ​

1. 栈 ​

1.1 栈的基本操作 ​

1.2 栈的典型应用 ​

2. C 语言示例：顺序栈 ​

3. 队列 ​

3.1 队列的典型应用 ​

3.2 顺序队列与“假溢出” ​

4. C 语言示例：循环队列 ​

5. 双端队列与优先队列 ​

5.1 双端队列 ​

5.2 优先队列 ​

5.3 栈和队列为何高频出现在算法题中 ​

5.4 为什么栈和队列被称为“受限线性结构” ​

6. 栈与队列的比较 ​

6.1 共性 ​

6.2 差异 ​

7. 本章小结 ​