栈与队列：从底层实现到循环队列与经典算法题

厨房里有一摞盘子：新洗好的盘子总是叠在最上面，要用的时候也总是从最上面拿——你绝不会伸手去抽最底下那块。食堂打饭正好相反：先来的人排在前面先打上饭，后来的人只能乖乖排在队尾，谁也不能插到队伍中间去。

这两种再普通不过的生活场景，恰好对应着数据结构里两兄弟：栈（Stack） 和队列（Queue）。它们本质上都是线性表——元素之间是一对一的线性关系，跟我们之前学过的顺序表、链表没什么两样。但它们是"受限制"的线性表：栈只允许在一端操作，队列只允许一端插入、另一端删除。正因为这种"限制"，它们的行为变得极其可预测，也因此在计算机世界里无处不在——函数调用、浏览器后退、撤销操作、打印任务调度、消息队列，背后都是它们在撑场子。

这一篇，我们从这两兄弟的概念讲到完整的 C 语言实现，再攻克循环队列和四道 LeetCode 经典题，最后看看它们在真实世界里的身影。

栈：只开一扇门的线性表

先看栈。栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。进行插入和删除的一端叫栈顶（top），另一端叫栈底（bottom）。

             高地址
        ┌─────────────┐
        │     5  ← 栈顶 │ ← 最后进去，最先出来
        │     4        │
        │     3        │
        │     2        │
        │     1  ← 栈底 │ ← 最先进去，最后出来
        └─────────────┘
             低地址

栈顶是"活动"的一端，所有操作都发生在这一端；栈底是"固定"的一端，一旦元素进去，在它上面的元素全部出栈之前，它动弹不得。这就注定了栈的规矩：后进先出（LIFO，Last In First Out）——后放进去的元素先被取出来。

栈的两个核心操作术语：

压栈：栈的插入操作，也叫进栈、入栈，把新数据放到栈顶；
出栈：栈的删除操作，把栈顶数据拿走。

举个具体的例子。依次入栈 1、2、3、4，栈里的样子是这样的：

入栈1    入栈2    入栈3    入栈4      出栈序列
┌─┐     ┌─┐     ┌─┐     ┌─┐       出4 → 出3 → 出2 → 出1
│1│     │2│     │3│     │4│ ← 栈顶
│ │     │1│     │2│     │3│
│ │     │ │     │1│     │2│
│ │     │ │     │ │     │1│ ← 栈底
└─┘     └─┘     └─┘     └─┘

出栈的顺序是 4、3、2、1——完全反过来。所以栈又叫"后进先出表"。你可以把它想象成一个只开顶盖的盒子：东西从顶盖放进去，也只能从顶盖拿出来，先放进去的永远压在下面。

栈在生活里随处可见：浏览器的后退按钮，每打开一个新页面就"压栈"，点后退就是"出栈"，退回到上一个页面；编辑器里的撤销（Undo），每一步操作都被压入历史栈，撤销一次就弹出最近的一步；你写代码时的函数调用，本质上也是一层层往系统栈里压入栈帧。这些我们放到最后再展开，先把它在代码层面吃透。

为什么栈用数组实现

栈的底层结构可以用数组，也可以用链表，两种都能实现。但工程和教学上都更推荐数组，理由只有一条：数组在尾上插入数据的代价最小。

对比一下两种方案：

实现方式	核心思路	优点	缺点
数组（推荐）	数组尾端作为栈顶，入栈=尾插、出栈=尾删	尾插尾删 O(1)；内存连续、缓存命中率高；实现简单	空间不足时需要扩容（realloc），扩容那一次是 O(n)
链表	单链表把头结点当栈顶，头插头删	无需扩容，按需分配内存	每个结点有指针开销；内存不连续、缓存命中率低；实现更繁琐

关键在插入和删除的位置。栈的所有操作都在栈顶，也就是"表尾"。数组在表尾插入一个元素，直接往 a[size] 写值就行，O(1)；链表如果在表尾插入，得先从头遍历找到尾结点，是 O(n)——除非你用头插法把链表头当栈顶，可那样虽然也是 O(1)，却要额外维护指针，还失去了连续内存的缓存优势。所以数组是栈的天然搭档。

提示
在分析数据结构时，请始终关注"操作发生的位置"：栈的操作全在表尾，数组尾插便宜；队列的删除在表头，数组头删要搬动所有元素——结论截然不同，后面讲队列时会再次遇到这个思维。

这里自然要用到我们之前学过的结构体、typedef、动态内存 malloc / realloc / free——栈要能装下任意数量的元素，必须动态扩容，这正是 C 语言动态内存管理的主场。

栈的完整实现

栈的结构体由三个成员组成：一个指向动态数组的指针 a，一个栈顶标记 top，一个容量 capacity。

typedef int STDataType;   // 栈元素类型，方便以后换成 double、结构体等
 
typedef struct Stack
{
    STDataType* a;        // 指向动态开辟的数组，栈元素的"仓库"
    int top;              // 栈顶标记（位置约定见下文）
    int capacity;         // 当前数组容量
} ST;

先解决一个绕不开的问题：top 到底指哪？

top 有两种完全不同的约定，初学阶段最容易在这里翻车。第一种，top 表示栈顶元素的下一个位置，也就是"下一个元素该放哪"；此时空栈 top == 0，而栈顶元素的下标是 top - 1，top 的值恰好等于元素个数。第二种，top 表示栈顶元素本身的位置，此时空栈 top == -1，入栈要先 ++top 再存，top + 1 才是元素个数。

约定	空栈时 top	栈顶元素下标	元素个数	入栈	出栈
约定 A：top 指向栈顶的下一个位置	0	top - 1	top	`a[top++] = x`	`--top`
约定 B：top 指向栈顶位置	-1	top	top + 1	`a[++top] = x`	`--top`

两种约定写出来的代码细节不同，但逻辑等价。下面我们统一用约定 A：top 指向栈顶元素的下一个位置，同时兼任"元素个数"的角色，判空直接看 top == 0，STSize 直接返回 top，一气呵成。这也是绝大多数教材采用的方式。

头文件 stack.h

把接口声明完整地写进头文件，接口名与课件保持一致：

#pragma once
 
#include <stdbool.h>   // bool / true / false
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int STDataType;
 
typedef struct Stack
{
    STDataType* a;        // 动态数组
    int top;              // 栈顶位置：指向栈顶元素的下一个位置（即元素个数）
    int capacity;         // 容量
} ST;
 
// 初始化栈
void STInit(ST* ps);
// 销毁栈
void STDestroy(ST* ps);
// 入栈
void STPush(ST* ps, STDataType x);
// 出栈
void STPop(ST* ps);
// 取栈顶元素
STDataType STTop(ST* ps);
// 获取栈中有效元素个数
int STSize(ST* ps);
// 栈是否为空
bool STEmpty(ST* ps);

注意一个细节：所有接口都接收指针 ST*，因为入栈、出栈、初始化都会修改栈本身，必须传地址才能在函数内部改动到外面的栈。这与我们之前学结构体传参时"结构体太大要传指针"的道理一样——不过更本质的原因是这里要修改它。

源文件 stack.c

#include "stack.h"
 
// 初始化：top = 0 表示空栈
void STInit(ST* ps)
{
    assert(ps);            // 传进来的指针不能是空指针
    ps->a = NULL;
    ps->top = 0;           // 空栈：top == 0
    ps->capacity = 0;
}
 
// 销毁：释放动态数组，防止内存泄漏
void STDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);           // free 释放 malloc/realloc 出来的空间
    ps->a = NULL;          // 置空，防止"野指针"二次释放
    ps->top = 0;
    ps->capacity = 0;
}
 
// 入栈：先检查容量，不够就扩容，然后尾插
void STPush(ST* ps, STDataType x)
{
    assert(ps);
 
    // 容量用满（top == capacity）时需要扩容
    if (ps->top == ps->capacity)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)          // realloc 失败会返回 NULL
        {
            perror("realloc fail");
            exit(1);
        }
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
 
    ps->a[ps->top] = x;   // 新元素放在 top 指向的位置
    ps->top++;            // top 后移一位
}
 
// 出栈：top 前移即可，元素"逻辑删除"
void STPop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));   // 空栈不能出栈！assert 帮忙拦截
    ps->top--;
}
 
// 取栈顶元素
STDataType STTop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));        // 空栈没有栈顶元素
    return ps->a[ps->top - 1];   // 栈顶元素在下标 top-1 处
}
 
// 有效元素个数：top 本身即元素个数
int STSize(ST* ps)
{
    assert(ps);
    return ps->top;
}
 
// 判空：top == 0
bool STEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

几个值得停下来细看的点：

扩容策略。 用 realloc 在原有空间的基础上扩大，容量不够时按 2 倍增长（capacity * 2），初始容量为 0 时先开 4 个。为什么按 2 倍扩容而不是每次只加 1 个？假设入栈 n 个元素，每次加 1 意味着前面每次都要 realloc，总开销是 1+2+3+...+n = O(n²)；按 2 倍扩容，realloc 的次数只有 log n 次，均摊下来每次入栈依然是 O(1)。这就是"均摊复杂度"思想——数组动态扩容的经典课。

边界处理。 STTop 和 STPop 都要求栈非空，空栈时取栈顶、出栈都是"未定义行为"。我们用 assert(!STEmpty(ps)) 在 Debug 版本里立刻崩溃并指出问题，这比闷声返回垃圾值好得多。

出栈为什么不清数据。 STPop 只是 top--，a[top] 里的旧值还在，但没关系——它已经被"逻辑删除"了：top 以上的区域根本不属于栈，下次入栈会直接覆盖它。把旧值手动清零反而多此一举。

入栈出栈，跟着指针走一遍

以约定 A 为例，模拟一次完整流程（初始容量 4）：

初始（空栈）          入栈 10              入栈 20              入栈 30
top=0                top=1                top=2                top=3
┌─┬─┬─┬─┐           ┌─┬─┬─┬─┐           ┌─┬─┬─┬─┐           ┌─┬─┬─┬─┐
│ │ │ │ │           │10│ │ │ │           │10│20│ │ │           │10│20│30│ │
└─┴─┴─┴─┘           └─┴─┴─┴─┘           └─┴─┴─┴─┘           └─┴─┴─┴─┘
  ↑                     ↑                     ↑                     ↑
top指向这里            新元素写到 top 处      ……                     …
 
STTop：返回 a[top-1] = a[2] = 30
STPop：top-- → top=2，30 被"逻辑删除"

每一步都只有数组尾端的一次读写，再加上偶尔的扩容搬运——所以栈的入栈、出栈、取栈顶都是 O(1) 的时间复杂度。

一段完整的测试

#include "stack.h"
 
int main(void)
{
    ST st;
    STInit(&st);              // 初始化空栈
 
    STPush(&st, 1);           // 依次入栈 1 2 3 4
    STPush(&st, 2);
    STPush(&st, 3);
    STPush(&st, 4);
 
    printf("栈中元素个数：%d\n", STSize(&st));   // 输出 4
    printf("栈顶元素：%d\n", STTop(&st));        // 输出 4
 
    printf("出栈序列：");
    while (!STEmpty(&st))     // 全部弹出，验证后进先出
    {
        printf("%d ", STTop(&st));
        STPop(&st);
    }
    printf("\n");             // 输出 4 3 2 1
 
    STDestroy(&st);           // 用完销毁，释放内存
    return 0;
}

到这里，栈我们已经完全掌握了：一个结构体、三个成员、七个接口。它的全部智慧浓缩在一句话里——只在栈顶动手。

队列：先来先服务

再看队列。队列是只允许在一端插入、在另一端删除的特殊线性表。进行插入的一端叫队尾（rear），进行删除的一端叫队头（front）。规矩是先进先出（FIFO，First In First Out）——先排队的人先被服务，跟食堂打饭一模一样。

出队列（删）                     入队列（插）
    │                              │
    ▼                              ▼
┌──────┐   ┌──────┐   ┌──────┐   ┌──────┐
│  1   │ → │  2   │ → │  3   │ → │  4   │
└──────┘   └──────┘   └──────┘   └──────┘
  队头（front）                    队尾（rear）

入队列：在队尾插入数据；
出队列：在队头删除数据。

为什么队列用链表实现

这里的选择和栈正好相反。回想一下栈：操作全在表尾，数组尾插 O(1)，于是选了数组。队列呢？入队在队尾，出队在队头——出队是"在表头删除"，如果用数组实现，删掉下标 0 的元素后，后面所有元素都得往前搬一位，一次出队就是 O(n)，n 大一点就肉眼可见地卡。

实现方式	入队（队尾）	出队（队头）	评价
数组	尾插 O(1)	头删 O(n)，要搬动所有元素	出队效率太低
链表（推荐）	尾插 O(1)，需维护队尾指针	头删 O(1)，只需改队头指针	两个方向都高效

链表则天然适合：每个结点是独立分配的内存，出队时把 phead 指向下一个结点、释放旧结点即可，O(1) 搞定，不需要搬动任何数据。所以结论是：栈用数组，队列用链表——记住这个反着来的选择，它背后是同一个思维：让高频操作发生在"便宜"的位置。这里我们也就用上了链表的知识：结点 struct QueueNode 里存放数据和指向下一个结点的指针，结点的自我引用、malloc 动态创建、遍历释放，都是链表的看家本领。

队列的完整实现

队列由两种结构构成：一个结点结构，一个队列结构。结点就是普通单链表结点；队列结构里维护队头指针、队尾指针和元素个数——注意，链表本身只有头指针，这里特意多存一个队尾指针 ptail，目的就是让入队（尾插）也能做到 O(1)，否则每次入队都要从头遍历到尾。

typedef int QDataType;   // 队列元素类型
 
// 队列结点结构：单链表结点
typedef struct QueueNode
{
    QDataType val;            // 数据域
    struct QueueNode* next;   // 指针域：指向下一个结点
} QNode;
 
// 队列结构：队头 + 队尾 + 元素个数
typedef struct Queue
{
    QNode* phead;   // 队头指针（出队的一端）
    QNode* ptail;   // 队尾指针（入队的一端）
    int size;       // 有效元素个数
} Queue;

头文件 queue.h

#pragma once
 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int QDataType;
 
typedef struct QueueNode
{
    QDataType val;
    struct QueueNode* next;
} QNode;
 
typedef struct Queue
{
    QNode* phead;   // 队头指针
    QNode* ptail;   // 队尾指针
    int size;       // 元素个数
} Queue;
 
// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);
// 入队列，队尾
void QueuePush(Queue* pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);
// 取队头数据
QDataType QueueFront(Queue* pq);
// 取队尾数据
QDataType QueueBack(Queue* pq);
// 队列判空
bool QueueEmpty(Queue* pq);
// 队列有效元素个数
int QueueSize(Queue* pq);

源文件 queue.c

#include "queue.h"
 
// 初始化：空队列，两个指针都指向 NULL
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->phead = NULL;
    pq->ptail = NULL;
    pq->size = 0;
}
 
// 销毁：逐个释放结点，先记下一个再释放当前
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->phead;
    while (cur != NULL)
    {
        QNode* next = cur->next;  // 先保存下一个结点的地址
        free(cur);                // 再释放当前结点
        cur = next;
    }
    pq->phead = NULL;
    pq->ptail = NULL;
    pq->size = 0;
}
 
// 入队列（队尾）：尾插法
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
 
    // 1. 创建新结点
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newNode->val = x;
    newNode->next = NULL;
 
    // 2. 挂到队尾
    if (pq->ptail == NULL)        // 空队列：新结点既是队头也是队尾
    {
        pq->phead = pq->ptail = newNode;
    }
    else                          // 非空：挂在旧队尾后面，更新队尾
    {
        pq->ptail->next = newNode;
        pq->ptail = newNode;
    }
    pq->size++;
}
 
// 出队列（队头）：头删
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));      // 空队列不能出队
 
    QNode* del = pq->phead;
    pq->phead = pq->phead->next;  // 队头指针后移
    free(del);                    // 释放旧队头结点
    del = NULL;
 
    // 关键边界：删除后队列空了，队尾指针也必须置空！
    if (pq->phead == NULL)
    {
        pq->ptail = NULL;
    }
    pq->size--;
}
 
// 取队头数据
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));      // 空队列没有队头
    return pq->phead->val;
}
 
// 取队尾数据
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));      // 空队列没有队尾
    return pq->ptail->val;
}
 
// 判空：队头指针为 NULL（或 size == 0）
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->phead == NULL;
}
 
// 有效元素个数
int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}

最容易被忽略的边界：出队出空了

队列实现里最容易写错的地方不是入队，而是出队——尤其是队列只剩一个结点时。走一遍：

出队前（只剩一个结点）：            QueuePop 执行：
                                del = phead → 结点3
phead ──► [3] ◄── ptail          phead = phead->next = NULL
                                free(结点3)
                                此时 phead == NULL，但 ptail 还指着已释放的结点3！

如果在 phead == NULL 时不把 ptail 也置空，ptail 就成了指向已释放内存的悬垂指针，下一次 QueuePush 判断 ptail == NULL 会失败，然后执行 pq->ptail->next = newNode——往一块已经归还给系统的内存里写数据，这是典型的未定义行为，程序可能在几天后以莫名其妙的方式崩溃。所以 QueuePop 末尾那两行 if (pq->phead == NULL) pq->ptail = NULL; 是必须的，不是锦上添花。

警告
链表操作的黄金法则：先保存"下一个"的地址，再释放"当前"。`QueueDestroy` 里遍历释放、`QueuePop` 里移动指针，都必须遵守，否则一释放就找不到后面的结点了。

队列测试

#include "queue.h"
 
int main(void)
{
    Queue q;
    QueueInit(&q);            // 初始化空队列
 
    QueuePush(&q, 1);         // 依次入队 1 2 3 4
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
 
    printf("队列元素个数：%d\n", QueueSize(&q));          // 输出 4
    printf("队头：%d  队尾：%d\n", QueueFront(&q), QueueBack(&q));  // 输出 1 4
 
    printf("出队序列：");
    while (!QueueEmpty(&q))   // 全部出队，验证先进先出
    {
        printf("%d ", QueueFront(&q));
        QueuePop(&q);
    }
    printf("\n");             // 输出 1 2 3 4
 
    QueueDestroy(&q);         // 销毁，释放所有结点
    return 0;
}

注意入队序列是 1 2 3 4，出队序列还是 1 2 3 4——与栈的输出 4 3 2 1 正好相反。FIFO 与 LIFO，一正一反，各司其职。

循环队列：把队尾接回队头

队列用链表实现非常完美，但如果你坚持用数组实现队列，会立刻撞上一堵墙：假溢出。

看下面这个过程。数组容量 6，front、rear 都从 0 出发，rear 指向下一个可写位置：

步骤       数组（下标0~5）          front  rear
① 初始    [ ][ ][ ][ ][ ][ ]        0      0
② 入队a   [a][ ][ ][ ][ ][ ]        0      1
③ 入队b   [a][b][ ][ ][ ][ ]        0      2
④ 出队a   [ ][b][ ][ ][ ][ ]        1      2
⑤ 出队b   [ ][ ][ ][ ][ ][ ]        2      2   ← 空队列了
⑥ 入队c   [ ][ ][c][ ][ ][ ]        2      3
⑦ 入队d   [ ][ ][c][d][ ][ ]        2      4
⑧ 入队e   [ ][ ][c][d][e][ ]        2      5
⑨ 入队f   [ ][ ][c][d][e][?]       2      5   ← rear 到末尾了！还想入队？

明明下标 0、1 还空着，可 rear 已经走到数组末尾，再入队就越界了。这就是假溢出——空间没满，却用不了。

怎么破？把数组在逻辑上首尾相接，想象成一条环形跑道：下标 5 再往前走一步，就绕回下标 0。于是 循环队列（环形队列） 诞生了：

                     ┌───────────────┐
                     │    [2]        │
                     │  ┌────────┐   │
                    [3]│        │[1] │
                     │  │        │   │
                     │ [4]──[5]─┘   │
                     │  ↑rear       │
                     └──────────────┘
                         ↑front
         front 和 rear 沿顺时针方向移动，绕圈循环

循环队列可以使用数组实现，也可以使用循环链表实现（循环链表的尾结点 next 指回头结点，首尾相连成环，下面的结构体就是它的骨架）：

// 循环链表版本的环形队列：尾结点的 next 指回头结点，成环
typedef struct CQueueNode
{
    QDataType val;
    struct CQueueNode* next;
} CQueueNode;
 
typedef struct CircularQueue
{
    CQueueNode* phead;   // 队头结点
    CQueueNode* ptail;   // 队尾结点
    int size;            // 当前元素个数
    int capacity;        // 最大容量
} CircularQueue;

数组实现更常见，因为内存连续、实现简单。指针移动全靠取模运算"绕圈"：

入队后：rear = (rear + 1) % capacity
出队后：front = (front + 1) % capacity

最难想通的问题：为什么 Q.rear 不存储数据？

这是循环队列最精华、也最容易懵的地方。让我们先想想：如果不做任何约定，front == rear 这个条件该表示"队空"还是"队满"？

答案是两个都成立——这就是麻烦所在。空队列：front 和 rear 指向同一位置。队列完全填满时呢？rear 在写入最后一个元素后前进一位，恰好又转回到 front 的位置，front == rear 同样成立。同一个条件，两种含义，程序根本没法区分，会陷入混乱。

既然 front == rear 有歧义，就得想办法打破它。教科书上最经典的做法是：牺牲一个存储单元，让 rear 永远指向一个"哨兵"空位，该位置永不存数据。这样：

队空：front == rear——指针重逢，没有元素；
队满：(rear + 1) % capacity == front——rear 再走一步就撞上 front，说明除了 rear 脚下的哨兵位，其余全满了。

提示
"Q.rear 为什么不存储数据"的答案：不是 rear 不能存，而是**故意留一个空位**，让"队空"和"队满"不再共用同一个判定条件。用 N 个存储单元，换来逻辑清晰的判空判满，还能保持所有操作 O(1)。

举个例子。capacity = 5（数组下标 0~4），实际最多存 4 个元素：

入队 A B C D 之后（满）：
数据: [ A ][ B ][ C ][ D ][   ]
下标:   0    1    2    3    4
front = 0    rear = 4（哨兵空位）
判满：(4 + 1) % 5 == 0 == front ✔ 队列已满
 
出队 A 之后：
数据: [   ][ B ][ C ][ D ][   ]
front = 1    rear = 4
判满：(4 + 1) % 5 == 0 ≠ 1 ✔ 未满，可以继续入队

你可能会问：为了区分空和满，除了"牺牲一个单元"，还有别的办法吗？有，主要有三种流派：

方案	判空	判满	评价
牺牲一个存储单元（经典）	front == rear	(rear+1)%capacity == front	实现最简单，无额外开销，最常用
计数器 count	count == 0	count == capacity	空间一点不浪费，但要维护 count，多一次读写
标志位 flag	front == rear && flag == 0	front == rear && flag == 1	每次入队出队都要维护标志位，易出错

牺牲一个单元之所以成为主流，正因为它在实现简单和空间开销之间取得了最佳平衡，代价只是少存一个元素——在大多数场景下可以忽略。记住判空判满这两条公式，它们是循环队列的魂：

判空：front == rear
判满：(rear + 1) % capacity == front

五道经典算法题

光会实现还远远不够。栈和队列在算法题里是高频主角，下面五道题是必刷的经典，前四道用我们刚写的代码就能解，最后一道直接考数据结构设计的功力。

第一题：有效的括号（LeetCode 20）

题目链接：https://leetcode.cn/problems/valid-parentheses/

给定一个只包含 ( ) [ ] { } 的字符串，判断括号是否有效：左括号必须用同类型的右括号闭合，且按正确顺序闭合。

思路。 这正是栈的天然舞台。遍历字符串：遇到左括号就压栈；遇到右括号，先看栈——栈空说明没有左括号可配对，直接返回 false；栈不空则弹出栈顶，检查是否与当前右括号配对。遍历结束后，栈必须是空的——否则说明还有没被闭合的左括号。

输入: "({[]})"
① 遇到 ( → 入栈  栈: [ ( ]
② 遇到 { → 入栈  栈: [ ( { ]
③ 遇到 [ → 入栈  栈: [ ( { [ ]
④ 遇到 ] → 弹栈匹配 [ ] ✔  栈: [ ( { ]
⑤ 遇到 } → 弹栈匹配 { } ✔  栈: [ ( ]
⑥ 遇到 ) → 弹栈匹配 ( ) ✔  栈: [ ]
结束，栈空 → 有效 ✔

嵌套越深，越需要"后进先出"——最内层的括号先闭合，正好对应栈顶元素先弹出。

#include <stdbool.h>
 
// 题目：https://leetcode.cn/problems/valid-parentheses/
// 思路：左括号入栈，右括号与栈顶匹配；最终栈必须为空
bool isValid(char* s)
{
    char stack[10000];   // 直接数组模拟栈（题目保证 s 长度 ≤ 10^4）
    int top = 0;         // 栈顶标记（元素个数）
 
    for (int i = 0; s[i] != '\0'; i++)
    {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{')
        {
            stack[top++] = c;          // 左括号：入栈
        }
        else                            // 右括号：
        {
            if (top == 0)               // 栈空 → 没有左括号配对
            {
                return false;
            }
            char left = stack[--top];   // 弹出栈顶
            // 检查是否配对
            if ((c == ')' && left != '(') ||
                (c == ']' && left != '[') ||
                (c == '}' && left != '{'))
            {
                return false;
            }
        }
    }
    return top == 0;   // 栈空才说明全部配对完成
}

时间复杂度和空间复杂度都是 O(n)。这题是栈应用的"hello world"，面试几乎必考。

第二题：用队列实现栈（LeetCode 225）

题目链接：https://leetcode.cn/problems/implement-stack-using-queues/

只用队列（FIFO）实现栈（LIFO），要求支持 push / pop / top / empty 四个操作。

思路。 两个队列配合：始终保持一个队列有数据、另一个队列空着。核心技巧在 push：把新元素放进空队列，再把另一个队列里的所有元素依次搬过来。这样一来，新元素被搬到了队头——而队头是"最先出"的位置，于是它成了最先被弹出的元素，完美模拟了"栈顶"。pop 就简单了，直接从非空队列的队头弹。

用队列 q1、q2 实现栈，依次 push 1、2、3：
push(1)：q1 空 → 1 放 q1，q2 空不用搬 → q1: [1]
push(2)：q2 空 → 2 放 q2，把 q1 的 1 搬过来 → q2: [2, 1]
push(3)：q1 空 → 3 放 q1，把 q2 的 2、1 搬过来 → q1: [3, 2, 1]
pop()：弹出 q1 队头 → 3 ✔（后进先出）

#include <stdbool.h>
#include <stdlib.h>
 
// 题目：https://leetcode.cn/problems/implement-stack-using-queues/
// 思路：两个数组队列 q1、q2。push 时把新元素放入空队列，
//       再把另一队列的元素全部搬来，使新元素始终处于队头（栈顶）。
 
#define MAX 101   // 题目保证最多调用 100 次
 
typedef struct
{
    int q1[MAX];        // 主队列（元素集中在这里）
    int q2[MAX];        // 辅助队列（空着）
    int front1, rear1;  // q1 队头、队尾下标
    int front2, rear2;  // q2 队头、队尾下标
} MyStack;
 
MyStack* myStackCreate(void)
{
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    st->front1 = st->rear1 = 0;
    st->front2 = st->rear2 = 0;
    return st;
}
 
void myStackPush(MyStack* obj, int x)
{
    // q1 空 → 把 x 放入 q1，再把 q2 的元素全部搬入 q1
    if (obj->front1 == obj->rear1)
    {
        obj->q1[obj->rear1++] = x;
        while (obj->front2 != obj->rear2)
        {
            obj->q1[obj->rear1++] = obj->q2[obj->front2++];
        }
    }
    // 否则 q2 空 → 把 x 放入 q2，再把 q1 的元素全部搬入 q2
    else
    {
        obj->q2[obj->rear2++] = x;
        while (obj->front1 != obj->rear1)
        {
            obj->q2[obj->rear2++] = obj->q1[obj->front1++];
        }
    }
}
 
int myStackPop(MyStack* obj)
{
    // 从非空队列的队头弹出（队头即栈顶）
    if (obj->front1 != obj->rear1)
    {
        return obj->q1[obj->front1++];
    }
    return obj->q2[obj->front2++];
}
 
int myStackTop(MyStack* obj)
{
    if (obj->front1 != obj->rear1)
    {
        return obj->q1[obj->front1];
    }
    return obj->q2[obj->front2];
}
 
bool myStackEmpty(MyStack* obj)
{
    return obj->front1 == obj->rear1 && obj->front2 == obj->rear2;
}
 
void myStackFree(MyStack* obj)
{
    free(obj);
}

push 是 O(n)（要把另一个队列的元素全搬过来），pop、top、empty 是 O(1)。这题想通"新元素必须出现在队头"这一层，代码就是水到渠成。

第三题：用栈实现队列（LeetCode 232）

题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/

反过来，只用栈实现队列。

思路。 两个栈，一个入队栈 in、一个出队栈 out。push 时直接压入 in。关键在 pop：如果 out 为空，就先把 in 里的元素全部弹出并压入 out——这个"倒腾"把顺序颠倒了两次（先进去的元素被压到了 out 的栈顶），于是 out 的栈顶恰好就是队列的队头。之后 pop 就只弹 out 的栈顶。这就是著名的双栈法。

push 1、2、3 → in: [1, 2, 3]（栈顶是 3）
pop 时 out 为空，把 in 全部倒入 out：
  out: [3, 2, 1]（栈顶是 1）
pop → 弹出 1 ✔（先进先出）
再 push 4 → in: [4]
再 pop → out 不空，直接弹 out → 2 ✔

注意倒腾的时机：只在 out 为空时才倒。如果每次 pop 都倒一遍，就退化成 O(n) 且逻辑更乱。而按"out 空了才倒"，每个元素最多被倒两次（一次入 in，一次入 out），均摊复杂度 O(1)。

#include <stdbool.h>
#include <stdlib.h>
 
// 题目：https://leetcode.cn/problems/implement-queue-using-stacks/
// 思路：双栈法。in 管入队，out 管出队；
//       out 为空时，把 in 全部倒入 out（顺序颠倒），out 栈顶即队头。
 
#define MAX 101
 
typedef struct
{
    int in[MAX];    // 入队栈
    int out[MAX];   // 出队栈
    int topIn;      // in 的栈顶（元素个数）
    int topOut;     // out 的栈顶（元素个数）
} MyQueue;
 
MyQueue* myQueueCreate(void)
{
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    q->topIn = 0;
    q->topOut = 0;
    return q;
}
 
// 把 in 的元素全部倒入 out（仅当 out 为空时执行）
void inToOut(MyQueue* obj)
{
    if (obj->topOut == 0)
    {
        while (obj->topIn > 0)
        {
            obj->out[obj->topOut++] = obj->in[--obj->topIn];
        }
    }
}
 
void myQueuePush(MyQueue* obj, int x)
{
    obj->in[obj->topIn++] = x;   // 入队：压入 in 栈
}
 
int myQueuePop(MyQueue* obj)
{
    inToOut(obj);                          // 保证 out 有元素
    return obj->out[--obj->topOut];        // 弹出 out 栈顶 = 队头
}
 
int myQueuePeek(MyQueue* obj)
{
    inToOut(obj);
    return obj->out[obj->topOut - 1];      // 只看不弹
}
 
bool myQueueEmpty(MyQueue* obj)
{
    return obj->topIn == 0 && obj->topOut == 0;
}
 
void myQueueFree(MyQueue* obj)
{
    free(obj);
}

延伸
"225 用队列实现栈"和"232 用栈实现队列"是一对镜像题：前者靠"搬移让新元素到队头"，后者靠"倒腾让旧元素到栈顶"。两个思路对比着刷，你对 LIFO 和 FIFO 的本质理解会突飞猛进。

第四题：设计循环队列（LeetCode 622）

题目链接：https://leetcode.cn/problems/design-circular-queue/

设计一个循环队列，支持 enQueue（入队）、deQueue（出队）、Front（队头）、Rear（队尾）、isEmpty、isFull，容量固定为 k。

思路。 直接用前面循环队列的结论：数组长度开 k + 1，多出的一格当"哨兵"。front 指向队头元素，rear 指向下一个可写位置（不存数据）。判空 front == rear，判满 (rear + 1) % capacity == front，指针移动全部取模绕圈。

#include <stdbool.h>
#include <stdlib.h>
 
// 题目：https://leetcode.cn/problems/design-circular-queue/
// 思路：数组 + front/rear 下标，取模绕圈。
//       rear 指向下一个可写位置（该位置不存数据，牺牲一格），
//       判空 front == rear，判满 (rear + 1) % capacity == front。
 
typedef struct
{
    int* a;          // 动态数组
    int front;       // 队头下标：指向队头元素
    int rear;        // 队尾下标：指向下一个可写位置（哨兵空位）
    int capacity;    // 数组容量（实际可用 capacity - 1）
} MyCircularQueue;
 
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a = (int*)malloc(sizeof(int) * (k + 1));   // 多开一格做哨兵
    q->front = 0;
    q->rear = 0;
    q->capacity = k + 1;
    return q;
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->front == obj->rear;   // 指针重逢 → 空
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    // rear 再走一步就撞上 front → 满
    return (obj->rear + 1) % obj->capacity == obj->front;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
    if (myCircularQueueIsFull(obj))
    {
        return false;                       // 满则入队失败
    }
    obj->a[obj->rear] = value;              // 数据写入 rear 位置
    obj->rear = (obj->rear + 1) % obj->capacity;  // rear 绕圈前进
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return false;                       // 空则出队失败
    }
    obj->front = (obj->front + 1) % obj->capacity;  // front 绕圈前进
    return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}
 
int myCircularQueueRear(MyCircularQueue* obj)
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    // 队尾元素在 rear 的前一格；取模是为了处理"绕回开头"的情况
    int index = (obj->rear - 1 + obj->capacity) % obj->capacity;
    return obj->a[index];
}
 
void myCircularQueueFree(MyCircularQueue* obj)
{
    free(obj->a);   // 先释放数组
    free(obj);      // 再释放结构体
}

一个容易写错的小地方：myCircularQueueRear 里取队尾下标时，直接写 obj->rear - 1 在 rear == 0 时会得到 -1，必须加上 capacity 再取模：(obj->rear - 1 + obj->capacity) % obj->capacity。在 C 语言里，负数取模的结果仍是负数（-1 % 5 == -1），这就是越界访问——这种"负下标"错误是循环队列题目里的经典翻车点。

所有操作的时间复杂度都是 O(1)，空间复杂度 O(k)。

第五题：最小栈（LeetCode 155）

题目链接：https://leetcode.cn/problems/min-stack/

设计一个支持 push、pop、top 的栈，再额外支持一个 getMin：常数时间内返回栈中的最小元素。难点全在最后这个要求上——如果每次 getMin 都遍历一遍栈找最小值，那就是 O(n)，不合格。

思路。 双栈法：一个普通的数据栈 st 存数据，一个辅助栈 minSt 同步维护"栈中每个状态下的最小值"。关键规则是：入栈时，新元素 x 与辅助栈栈顶的当前最小值比较，谁小压谁——这样辅助栈的栈顶永远等于"数据栈当前所有元素的最小值"。出栈时两个栈一起弹，保证辅助栈顶始终同步。

操作序列               数据栈 st        辅助栈 minSt（栈顶 = 当前最小值）
push(3)                [3]             [3]
push(5)                [3, 5]          [3, 3]      ← 5 > 3，压入旧最小值 3
push(2)                [3, 5, 2]       [3, 3, 2]   ← 2 < 3，压入新最小值 2
getMin() → 2           读取 minSt 栈顶即可
pop()                  [3, 5]          [3, 3]      ← 两个栈一起弹
getMin() → 3           最小值跟着恢复成了 3！

注意 push(5) 那一步：5 比当前最小值 3 大，但辅助栈仍然压入 3 而不是 5——因为"压入 5 之后栈的最小值还是 3"。辅助栈里压的是"每个时刻的最小值"，而不是"每个时刻的值"。这样数据栈弹出后，辅助栈同步弹出，最小值能自动恢复到之前的状态——这正是这个解法最精妙的地方。

#include <stdbool.h>
#include <stdlib.h>
 
// 题目：https://leetcode.cn/problems/min-stack/
// 思路：数据栈 st + 辅助栈 minSt。minSt 栈顶始终是 st 中所有元素的最小值。
//       push 时压入 min(x, minSt 栈顶)；pop 时两个栈一起弹。
 
#define MAX 30005   // 题目最多 3*10^4 次调用，数组容量开大一点避免越界
 
typedef struct
{
    int st[MAX];      // 数据栈
    int minSt[MAX];   // 辅助栈：栈顶 = 当前最小值
    int top;          // 数据栈栈顶（元素个数）
    int minTop;       // 辅助栈栈顶（元素个数）
} MinStack;
 
MinStack* minStackCreate(void)
{
    MinStack* obj = (MinStack*)malloc(sizeof(MinStack));
    obj->top = 0;
    obj->minTop = 0;
    return obj;
}
 
void minStackPush(MinStack* obj, int x)
{
    obj->st[obj->top++] = x;   // 数据栈正常入栈
    // 辅助栈压入"当前最小值"：空栈直接压 x，否则压 min(x, 栈顶)
    if (obj->minTop == 0 || x < obj->minSt[obj->minTop - 1])
    {
        obj->minSt[obj->minTop++] = x;   // x 更小，压 x
    }
    else
    {
        // x 不小于当前最小值：重复压入旧最小值（minSt 栈顶），
        // 保证 minSt 与 st 同步增长、栈顶恒为当前最小值
        int curMin = obj->minSt[obj->minTop - 1];  // 先取出旧最小值
        obj->minSt[obj->minTop++] = curMin;        // 再压入（注意顺序）
    }
}
 
void minStackPop(MinStack* obj)
{
    obj->top--;      // 两个栈同步弹出，保证状态一致
    obj->minTop--;
}
 
int minStackTop(MinStack* obj)
{
    return obj->st[obj->top - 1];
}
 
int minStackGetMin(MinStack* obj)
{
    return obj->minSt[obj->minTop - 1];   // 辅助栈栈顶就是当前最小值，O(1)
}
 
bool minStackEmpty(MinStack* obj)
{
    return obj->top == 0;
}
 
void minStackFree(MinStack* obj)
{
    free(obj);
}

四个操作全部 O(1)，空间 O(n)（两个栈）。最小栈是面试高频题，它的价值在于：当"取最值"这个需求碰上了"动态变化"的栈，用一个辅助结构把最值"增量维护"起来。这个"增量维护最值"的思想，后面还会在单调栈、堆、滑动窗口最大值里反复出现。

栈和队列的广阔世界

栈和队列不只是算法题里的常客，它们是真实计算机系统的地基。理解了它们，你会突然看懂很多"原来如此"。

栈：无处不在的"撤销"与"回溯"

函数调用栈。 每次调用函数，系统都会把这次调用的信息（返回地址、局部变量、参数）打包成一个"栈帧"压入调用栈；函数返回时，栈帧弹出。所以先调用的函数后返回——这正是 LIFO：

#include <stdio.h>
 
// 输出顺序：C 执行 → B 执行 → A 执行
// 调用顺序：A → B → C，返回顺序正好相反（后进先出）
void funcC(void) { printf("C 执行\n"); }
void funcB(void) { funcC(); printf("B 执行\n"); }
void funcA(void) { funcB(); printf("A 执行\n"); }
 
int main(void)
{
    funcA();
    return 0;
}

递归正是函数调用栈的直接应用。每次递归调用都压入一个新的栈帧，递归深度就是调用栈的深度——所以深度过大的递归会"栈溢出"（Stack Overflow），因为系统栈的大小是有限的。这解释了你可能遇到过的"栈溢出错误"。

表达式求值。 编译器把中缀表达式 (3 + 4) * 5 转成后缀（逆波兰）表达式 3 4 + 5 *，然后用一个栈轻松求值：遇到数字压栈，遇到运算符弹出两个操作数、计算、再压回结果：

#include <stdio.h>
#include <ctype.h>
 
// 用栈求后缀表达式的值："34+5*" 即 (3+4)*5 = 35
// 遇到数字压栈，遇到运算符弹出两个操作数计算后压回
int main(void)
{
    const char* expr = "34+5*";   // 只演示一位数字和 + - * /
    int stack[100];
    int top = 0;
 
    for (int i = 0; expr[i] != '\0'; i++)
    {
        char c = expr[i];
        if (isdigit((unsigned char)c))
        {
            stack[top++] = c - '0';   // 数字入栈
        }
        else
        {
            int b = stack[--top];     // 先弹出的是右操作数
            int a = stack[--top];     // 后弹出的是左操作数
            switch (c)
            {
                case '+': stack[top++] = a + b; break;
                case '-': stack[top++] = a - b; break;
                case '*': stack[top++] = a * b; break;
                case '/': stack[top++] = a / b; break;
            }
        }
    }
    printf("结果：%d\n", stack[--top]);   // 输出 35
    return 0;
}

注意弹出顺序：先弹出的是 b（右操作数），后弹出的是 a（左操作数），减法和除法时必须分清，否则 3 4 - 会被算成 4 - 3。

中缀转后缀：运算符栈的完整算法

上面假设后缀表达式已经给好了。可现实中人们写的是中缀表达式（(3 + 4) * 5），怎么把它转成后缀？靠的还是一张栈——运算符栈。算法分四种情况处理扫描到的每个字符：

遇到什么	怎么处理
数字/操作数	直接输出（追加到后缀表达式末尾）
左括号 `(`	直接压栈
右括号 `)`	不停弹出栈顶运算符并输出，直到弹出左括号（左括号弹出但不输出）
运算符 `+ - * /`	只要栈不空、且栈顶是运算符、且栈顶优先级 ≥ 当前运算符优先级，就弹出栈顶并输出；然后把当前运算符压栈

规则里最需要理解的是最后一行：栈顶优先级 ≥ 当前才弹出。原因是运算符的"左结合"——同级运算符从左往右算，所以先出现的（在栈底的）应该先输出。左括号的优先级约定为最低（遇到它必须停，因为括号内的运算符要在括号配对后才输出）。扫描结束后，把栈里剩下的运算符全部弹出输出。

优先级表：+ - 为 1 级，* / 为 2 级，( 为 0 级（最低）。

以 (3 + 4) * 5 为例逐步推演（输出列 = 后缀表达式）：

扫描到    操作                               运算符栈    输出
(         压栈                                [ ( ]
3         直接输出                            [ ( ]       3
+         栈顶是 ( ，优先级最低不弹出，压栈      [ ( + ]     3
4         直接输出                            [ ( + ]     3 4
)         弹 + 输出，再弹出 ( 不输出           [ ]         3 4 +
*         栈空，压栈                           [ * ]       3 4 +
5         直接输出                            [ * ]       3 4 + 5
结束      弹出剩余运算符                       [ ]         3 4 + 5 *

结果 3 4 + 5 *，和 (3+4)×5 的语义完全一致。再看一个有优先级梯度的：2 + 3 * 4 - 5：

扫描到    操作                               运算符栈    输出
2         直接输出                            [ ]         2
+         栈空压栈                             [ + ]       2
3         直接输出                            [ + ]       2 3
*         栈顶 + 优先级 1 < 2，不弹出，压栈     [ + * ]     2 3
4         直接输出                            [ + * ]     2 3 4
-         栈顶 * 优先级 2 ≥ 1，弹 *；再比 + ≥ 1，弹 +；
          栈空，压入 -                         [ - ]       2 3 4 * +
5         直接输出                            [ - ]       2 3 4 * + 5
结束      弹出剩余                            [ ]         2 3 4 * + 5 -

注意处理 - 那一步：它一口气把 * 和 + 都弹了出来——因为栈里的 *、+ 都先于 - 出现，且优先级不低于 -，按照"同级从左到右、高优先级先算"的原则，它们必须排在 - 前面输出。转成后缀后求值：2 3 4 * + 5 - = 2 + 12 - 5 = 9 ✓。这个"把中缀转成后缀，再用一个栈求值"的两步法，就是编译器计算表达式的最经典方案——中缀给人看，后缀给机器算，中间那一步就是运算符栈的功劳。

#include <stdio.h>
#include <ctype.h>
 
// 中缀表达式转后缀：只处理单字符操作数 + - * / 和括号
// 优先级：+ - 为 1，* / 为 2，( 为 0
int priority(char op)
{
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;   // '(' 优先级最低
}
 
// 把中缀表达式 infix 转成后缀存进 postfix
void infixToPostfix(const char* infix, char* postfix)
{
    char stack[100];
    int top = 0;      // 运算符栈（栈顶位置 = 元素个数）
    int len = 0;      // 输出长度
 
    for (int i = 0; infix[i] != '\0'; i++)
    {
        char c = infix[i];
        if (isdigit((unsigned char)c))       // ① 操作数：直接输出
        {
            postfix[len++] = c;
        }
        else if (c == '(')                   // ② 左括号：压栈
        {
            stack[top++] = c;
        }
        else if (c == ')')                   // ③ 右括号：弹到左括号为止
        {
            while (top > 0 && stack[top - 1] != '(')
            {
                postfix[len++] = stack[--top];   // 栈顶运算符输出
            }
            if (top > 0)                     // 弹出左括号本身，不输出
            {
                top--;
            }
        }
        else                                 // ④ 运算符：弹出所有优先级 >= 它的栈顶
        {
            while (top > 0 && priority(stack[top - 1]) >= priority(c))
            {
                postfix[len++] = stack[--top];
            }
            stack[top++] = c;                // 当前运算符压栈
        }
    }
    while (top > 0)                          // ⑤ 扫描结束，弹出剩余运算符
    {
        postfix[len++] = stack[--top];
    }
    postfix[len] = '\0';
}
 
int main(void)
{
    char postfix[100];
    infixToPostfix("(3+4)*5", postfix);
    printf("%s\n", postfix);   // 输出 34+5*
 
    infixToPostfix("2+3*4-5", postfix);
    printf("%s\n", postfix);   // 输出 234*+5-
 
    return 0;
}

易错点
① 右括号弹出运算符时，左括号本身**不输出**——它是纯粹的控制符，没有对应的后缀符号；② 运算符弹栈的条件是"栈顶优先级 **≥** 当前"，用 ≥ 才能保证同级运算符从左到右的顺序，如果错用 >，`2 - 3 - 4` 会被转成 `2 3 4 - -`（= 2-3-4 = -5 的语义被破坏）；③ 遇到括号嵌套时，优先级比较必须被 `(` 挡住，所以把 `(` 的优先级设为最低最稳妥。

浏览器前进后退与撤销。 浏览器的"后退"就是历史记录栈：新页面入栈，后退出栈；如果要支持"前进"，还需要另一个栈装被退出的页面，两个栈对倒——这就是用栈实现队列（232 题）的现实原型。编辑器的撤销（Undo）同样是操作历史栈，每步操作压栈，撤销弹出。

队列：排队的秩序感

广度优先搜索（BFS）。 二叉树的层序遍历、图的最短路径，靠的都是队列：先把起点入队，然后循环——出队一个结点、把它的所有邻居入队。这样一层一层往外扩散，天然保证"先到达的先被处理"，这正是 FIFO。等我们后面学树和图，队列就是最趁手的工具。

任务调度。 操作系统、线程池里最常见的就是队列。打印任务、进程就绪队列、磁盘 IO 请求，全部排成队列，先来先服务（FCFS）——公平、有序、不插队。这保证了系统"雨露均沾"，不会出现某个任务饿死的情况。

消息队列。 大型系统解耦的利器：生产者往队尾发消息，消费者从队头取消息。生产慢、消费快，或反过来，队列都默默消化掉速度差，两边谁都不用等谁。消息中间件（如 Kafka、RabbitMQ）的核心就是"先进先出的有序缓冲区"。

思考题与练习

栈和队列的代码短、接口少，但正因为结构简单，反而最考验"把场景抽象成结构"的能力。下面几道题，前两题是经典的原理题，后几题是热门的算法题。

练习 1：出栈序列合法性判断。 已知元素 1, 2, 3, 4, 5 依次入栈（入栈过程中可以随时出栈，比如入 1、入 2、出 2、入 3……）。判断下面哪些出栈序列是可能的：A. 4 5 3 2 1　B. 5 4 3 2 1　C. 3 1 2 4 5　D. 1 5 2 4 3

提示

A 可能：入 1 2 3 4 → 出 4 → 入 5 → 出 5 → 出 3 2 1。B 可能：全部入栈再依次弹出。C 不可能：要出 3，必须先入 1 2 3，此时 1、2 还在栈里，出 3 后下一个能出的只有 2，不可能是 1。D 不可能：出 1 后出 5 意味着 2 3 4 已经全部入栈，之后只能依次出 4 3 2，不可能出 2 后跳回 4。判断的通用方法：用一个栈模拟入栈序列，每入一个就尝试按出栈序列弹出，最终栈空且序列走完则合法。

练习 2：两个队列实现栈的另一种思路。 文中用"把新元素放空队列再搬运"实现了 push O(n)。如果改成 push 直接入队、pop 时搬运呢？想一想：pop 时怎么把"队尾元素"变成"队头元素"取出来？这个版本各操作复杂度是多少？

提示

push 直接入队 q1，O(1)。pop 时把 q1 的前 n-1 个元素搬到 q2，q1 剩下的最后一个就是"栈顶"，取走它；然后交换 q1、q2 的角色，O(n)。两种方案一个"push 贵"、一个"pop 贵"，各有取舍——这再次说明"操作发生的位置决定复杂度"。

练习 3：每日温度（LeetCode 739）。 给定每日温度数组 temperatures，返回数组 answer，其中 answer[i] 是第 i 天之后需要等多少天才会出现更高的温度；如果之后没有更高温度，填 0。提示：单调递减栈——栈里存"还没找到更高温度的下标"，温度严格递减（新的温度只比栈顶高时，才把栈顶弹出来结算）。

提示

核心思路：遍历温度，当前温度 t 如果高于栈顶下标的温度，就弹出栈顶下标 idx，answer[idx] = i - idx（栈顶下标等了这么多天），然后继续和新的栈顶比；如果 t 不高于栈顶，就把当前下标入栈（栈内温度从栈底到栈顶严格递减）。每个下标最多入栈、出栈各一次，总复杂度 O(n)。单调栈是栈里最进阶的内容，能吃透这道题，说明你对栈的理解已经远超平均水平。

练习 4（挑战）：完整的中缀表达式求值。 把"中缀转后缀"和"后缀求值"两段代码拼起来，写一个 int eval(const char* infix)，直接计算 (3+4)*5-2 这类表达式的结果（提示：可以先转后缀存到临时数组，再套用后缀求值；也可以一步到位用双栈法——操作数栈 + 运算符栈，边扫描边算）。

提示

双栈法要点：遇到数字压操作数栈；遇到运算符，只要"运算符栈栈顶优先级 ≥ 当前"，就弹出运算符和两个操作数，计算后把结果压回操作数栈，再压入当前运算符；遇到右括号同理，弹到左括号为止。扫描结束，把运算符栈清空，操作数栈顶就是结果。完整实现约 60 行，能独立写出来，表达式求值这一块你就彻底毕业了。

自检清单
学完本章，你应该能说清：栈为什么用数组、队列为什么用链表（操作发生的位置）；top 两种约定怎么选；循环队列为什么牺牲一个单元（front == rear 有歧义）；最小栈怎么用辅助栈增量维护最值；中缀转后缀为什么"栈顶优先级 ≥ 当前"才弹出；用栈模拟队列为什么均摊 O(1)；函数调用栈、BFS、消息队列为什么分别是栈和队列的应用。这些都清楚，栈与队列就算真正拿下了，接下来可以去见见层次结构的代表——树。

写在最后

走到这里，我们完成了两件大事：亲手用 C 语言实现了栈和队列，以及用它们解决了五道经典算法题。回过头看，栈和队列的全部奥秘其实就两句话——栈，后进先出，只在栈顶动手；队列，先进先出，一头进一头出。它们都是"受限的线性表"，正因为受限，行为才可预测；正因为可预测，才成了无数算法和系统最底层的砖石。

选型上那个反直觉的结论也别忘：栈用数组（尾插便宜），队列用链表（头删便宜）；非要用数组实现队列，就得上循环队列，用牺牲一个单元换来判空判满的清晰。栈和队列，一个"回溯"一个"排队"，一纵一横，接下来我们学习树、图的遍历时，会反复与它们重逢——那时你会发现，今天打下的地基有多么结实。

下一站，我们从线性结构走向层次结构，看看"树"如何用递归和栈（或者队列）演绎出另一番天地。