5. 栈与队列进阶：循环队列、链队列、栈的应用、队列的应用

好，咱们继续往下走。上一章我们把栈和队列的基本概念讲清楚了，说白了就是两种操作受限的线性表。但光知道概念没用，真正干活的时候，你得知道怎么用、怎么优化、怎么避开那些坑。这一章，我带你看看它们在实际工程里的进阶玩法。

5.1 循环队列——别让空间白白浪费

先说说队列。用数组实现队列，有个很尴尬的问题：front 指针一直往后移，前面的空间就空着，但你又没法用。我早年做嵌入式通信模块时就吃过这个亏——缓冲区明明还有一半空间，队列却告诉我满了。为什么？因为 rear 已经跑到数组末尾了。

解决办法很简单：把数组头尾连起来，做成一个环。这就是循环队列。

5.1.1 核心结构

typedef struct {
    int *data;      // 动态数组
    int front;      // 队头指针
    int rear;       // 队尾指针
    int capacity;   // 数组容量
} CircularQueue;

这里有个关键点：判空和判满。你想想看，如果 front == rear，到底是空还是满？

嗯，我习惯的做法是「牺牲一个元素空间」。也就是说，队列最多存 capacity - 1 个元素。这样判空就是 front == rear，判满就是 (rear + 1) % capacity == front。

5.1.2 入队与出队

// 入队
bool enqueue(CircularQueue *q, int val) {
    if ((q->rear + 1) % q->capacity == q->front)
        return false;  // 队列满
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % q->capacity;
    return true;
}

// 出队
bool dequeue(CircularQueue *q, int *val) {
    if (q->front == q->rear)
        return false;  // 队列空
    *val = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    return true;
}

注意那个取模运算 %。我见过有人直接用 rear++，结果数组越界了还不知道。循环队列的精髓就在这个「循环」二字上，指针走到头了就得绕回来。

5.2 链队列——动态扩容，不怕溢出

循环队列虽然高效，但有个硬伤：容量固定。如果你事先不知道数据量，或者数据量波动很大，用数组就不太合适。这时候就该链队列上场了。

链队列说白了就是一个带尾指针的单链表。为什么带尾指针？因为入队操作在尾部，没有尾指针的话每次入队都要遍历到链表末尾，时间复杂度就变成 O(n) 了。我当年写网络协议栈时，接收队列就是用链队列实现的——数据包大小不确定，用数组根本没法搞。

5.2.1 结构定义

typedef struct QNode {
    int data;
    struct QNode *next;
} QNode;

typedef struct {
    QNode *front;  // 队头
    QNode *rear;   // 队尾
} LinkedQueue;

入队时，新节点挂在 rear 后面，然后 rear 指向新节点。出队时，从 front 取节点，然后 front 后移。注意：当队列只剩一个节点时，出队后 front 和 rear 都要置为 NULL。

5.3 栈的应用：括号匹配

栈这东西，最经典的应用就是括号匹配。你写代码时，IDE 会帮你检查括号有没有成对出现，背后就是栈在干活。

思路很简单：遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶是不是对应的左括号。如果是，弹出；如果不是，说明不匹配。最后如果栈为空，说明所有括号都匹配上了。

bool isMatching(char *expr) {
    Stack s;
    initStack(&s);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&s, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&s)) return false;
            char top = pop(&s);
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
                return false;
        }
    }
    return isEmpty(&s);
}

这个算法的时间复杂度是 O(n)，空间复杂度也是 O(n)。你想想看，如果嵌套深度特别大，比如几千层括号，栈会不会爆？嗯，这就是为什么有些编译器会限制嵌套深度——不是不想支持，是栈空间有限。

5.4 栈的应用：表达式求值

表达式求值比括号匹配复杂多了。你要处理运算符优先级、括号、甚至负数。我当年写计算器时，被这个坑折腾了两天。

标准做法是「双栈法」：一个栈存操作数，一个栈存运算符。遍历表达式时：

• 遇到数字，直接压入操作数栈
• 遇到运算符，比较它和栈顶运算符的优先级：
  • 如果当前运算符优先级更高，压栈
  • 否则，弹出栈顶运算符，从操作数栈弹出两个数，计算，结果压回操作数栈
• 遇到左括号，直接压栈
• 遇到右括号，一直弹出运算符计算，直到遇到左括号

这里有个细节：减法不满足交换律。比如 3 - 5，弹出的是 5 和 3，计算时要用 3 - 5，而不是 5 - 3。我建议你写代码时，把先弹出的数当作右操作数，后弹出的当作左操作数。

5.5 队列的应用：舞伴问题

最后聊一个轻松点的——舞伴问题。说白了就是：男生排一队，女生排一队，每次从两队各取一个人配对跳舞。如果某一队没人了，就等着。

这不就是两个队列嘛！男生队列和女生队列。每次从两个队列分别出队一个人，组成一对。如果某个队列空了，就输出「等待中」。

void danceMatch(char *males[], int mCount, char *females[], int fCount) {
    Queue maleQ, femaleQ;
    initQueue(&maleQ);
    initQueue(&femaleQ);
    
    for (int i = 0; i < mCount; i++) enqueue(&maleQ, males[i]);
    for (int i = 0; i < fCount; i++) enqueue(&femaleQ, females[i]);
    
    while (!isEmpty(&maleQ) && !isEmpty(&femaleQ)) {
        char *male = dequeue(&maleQ);
        char *female = dequeue(&femaleQ);
        printf("配对：%s 和 %s\n", male, female);
    }
    
    if (!isEmpty(&maleQ))
        printf("还有 %d 位男生在等待\n", size(&maleQ));
    if (!isEmpty(&femaleQ))
        printf("还有 %d 位女生在等待\n", size(&femaleQ));
}

这个例子虽然简单，但它的思想在很多地方都用得上。比如打印机的任务队列、操作系统的进程调度，本质上都是「排队 + 配对」的逻辑。

5.6 本章知识结构图

下面这张图把本章的核心知识点串起来了，你可以对照着回顾一下。

好了，这一章的内容就到这儿。循环队列和链队列各有各的适用场景，栈的应用在编译器和计算器里随处可见，队列的配对思想在很多调度场景都能复用。你把这些吃透了，后面学树和图的时候，会发现很多地方都用得上这些基本功。