第18章栈与队列

课程目录第18章栈与队列

栈与队列：顺序存储、链式存储与循环队列

栈和队列，这两个数据结构，说白了就是操作受限的线性表。我刚开始学的时候觉得它们太简单了，不就是数组加几个限制条件嘛。后来在项目中写解析器、做任务调度，才发现这两个东西用好了，代码能写得又稳又漂亮。今天咱们就把它们的顺序存储、链式存储，还有循环队列这个经典设计，一次性讲透。

栈的顺序存储

栈的特点是后进先出（LIFO）。顺序存储就是用数组来实现。我习惯用一个整型变量 top 来标记栈顶位置，初始时 top = -1，表示空栈。

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top;
} SeqStack;

// 初始化
void InitStack(SeqStack *s) {
    s->top = -1;
}

// 入栈
int Push(SeqStack *s, int x) {
    if (s->top == MAXSIZE - 1) {
        return 0;  // 栈满
    }
    s->data[++s->top] = x;
    return 1;
}

// 出栈
int Pop(SeqStack *s, int *x) {
    if (s->top == -1) {
        return 0;  // 栈空
    }
    *x = s->data[s->top--];
    return 1;
}

小提示：入栈时先移动 top 再赋值，出栈时先取值再移动 top。这个顺序搞反了，数据就乱了。我刚开始写的时候犯过这个错，调试了半天才发现。

栈的链式存储

链式存储的栈，说白了就是用链表来实现。入栈和出栈都在链表头部操作，这样时间复杂度是 O(1)。我个人习惯用带头结点的单链表，操作起来更统一。

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

typedef struct {
    StackNode *top;
} LinkStack;

// 入栈
void Push(LinkStack *s, int x) {
    StackNode *node = (StackNode *)malloc(sizeof(StackNode));
    node->data = x;
    node->next = s->top;
    s->top = node;
}

// 出栈
int Pop(LinkStack *s, int *x) {
    if (s->top == NULL) {
        return 0;
    }
    StackNode *p = s->top;
    *x = p->data;
    s->top = p->next;
    free(p);
    return 1;
}

注意：链式栈出栈后一定要 free 掉节点。我曾经在一个嵌入式项目里忘了释放内存，跑了三天后系统直接崩了。内存泄漏在栈这种频繁操作的结构里特别容易发生。

队列的顺序存储

队列是先进先出（FIFO）。顺序存储用数组加两个指针：front 指向队头，rear 指向队尾的下一个位置。初始时 front = rear = 0。

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int front, rear;
} SeqQueue;

// 入队
int EnQueue(SeqQueue *q, int x) {
    if (q->rear == MAXSIZE) {
        return 0;  // 队满
    }
    q->data[q->rear++] = x;
    return 1;
}

// 出队
int DeQueue(SeqQueue *q, int *x) {
    if (q->front == q->rear) {
        return 0;  // 队空
    }
    *x = q->data[q->front++];
    return 1;
}

你想想看，这种实现有个大问题：出队后 front 往前移动，数组前面的空间就浪费了。明明数组还有空间，rear 却已经到末尾了，这就是“假溢出”。

循环队列

为了解决假溢出，我们把数组首尾相连，形成一个环。这就是循环队列。判断队满的条件变成了 (rear + 1) % MAXSIZE == front。为什么要留一个空位？因为如果不留，队空和队满的条件都是 front == rear，就分不清了。

typedef struct {
    int data[MAXSIZE];
    int front, rear;
} CircularQueue;

// 初始化
void InitQueue(CircularQueue *q) {
    q->front = q->rear = 0;
}

// 入队
int EnQueue(CircularQueue *q, int x) {
    if ((q->rear + 1) % MAXSIZE == q->front) {
        return 0;  // 队满
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;
    return 1;
}

// 出队
int DeQueue(CircularQueue *q, int *x) {
    if (q->front == q->rear) {
        return 0;  // 队空
    }
    *x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return 1;
}

// 求长度
int QueueLength(CircularQueue *q) {
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}

核心要点：循环队列中，rear 永远指向下一个空位。队满时数组里其实还有一个空位，这个空位就是用来区分队空和队满的。我建议你画个环形图来理解，比死记公式管用多了。

队列的链式存储

链式队列需要两个指针：front 指向队头节点，rear 指向队尾节点。入队操作在 rear 后面加节点，出队操作删除 front 指向的节点。

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

typedef struct {
    QNode *front;
    QNode *rear;
} LinkQueue;

// 初始化
void InitQueue(LinkQueue *q) {
    q->front = q->rear = (QNode *)malloc(sizeof(QNode));
    q->front->next = NULL;
}

// 入队
void EnQueue(LinkQueue *q, int x) {
    QNode *node = (QNode *)malloc(sizeof(QNode));
    node->data = x;
    node->next = NULL;
    q->rear->next = node;
    q->rear = node;
}

// 出队
int DeQueue(LinkQueue *q, int *x) {
    if (q->front == q->rear) {
        return 0;  // 队空
    }
    QNode *p = q->front->next;
    *x = p->data;
    q->front->next = p->next;
    if (q->rear == p) {
        q->rear = q->front;  // 删除最后一个节点
    }
    free(p);
    return 1;
}

避坑指南：链式队列出队时，如果删除的是最后一个节点，一定要把 rear 重新指向头节点。我曾经漏掉这个判断，结果 rear 变成了野指针，程序跑着跑着就莫名其妙地崩溃了。

知识体系总览

下面这张图把栈和队列的四种存储方式串起来了，你可以对照着看，心里有个整体框架。

四种存储方式对比

结构	优点	缺点	适用场景
顺序栈	实现简单，访问快	大小固定，可能溢出	函数调用、表达式求值
链式栈	动态扩展，无溢出	需要额外指针空间	数据量不确定的场景
循环队列	空间利用率高，无假溢出	判满条件需要留一个空位	缓冲区、消息队列
链式队列	动态扩展，操作灵活	需要管理内存	任务调度、BFS遍历

嗯，到这里栈和队列的四种存储方式就讲完了。我个人觉得，循环队列是这里面最巧妙的设计，用取模运算就把线性数组变成了环形结构。你在写代码的时候，多想想实际场景：数据量固定就用顺序存储，数据量变化大就用链式存储。选对了结构，代码写起来顺手，跑起来也稳当。

📚 课程目录

栈与队列：顺序存储、链式存储与循环队列

栈的顺序存储

栈的链式存储

队列的顺序存储

循环队列

队列的链式存储

知识体系总览

四种存储方式对比