栈与队列：顺序存储与链式存储，以及实际应用场景

栈和队列，这两个数据结构，说白了就是两种特殊的线性表。特殊在哪？特殊在它们的操作规则。我刚开始学C语言的时候，觉得这俩玩意儿不就是数组和链表吗？有啥好学的？后来在项目中吃了亏，才明白它们的设计哲学有多精妙。

今天咱们就把栈和队列彻底聊透。从存储方式到代码实现，再到实际场景，一步到位。

栈：后进先出的世界

栈，就像一摞盘子。你只能从最上面拿盘子，也只能把新盘子放在最上面。这个规则叫后进先出（LIFO）。

我个人习惯把栈想象成一个死胡同。先进去的车，必须等后面的车都倒出来，它才能出来。你想想看，是不是这个理？

栈的顺序存储

顺序存储，就是用数组来实现栈。我们需要一个数组，一个栈顶指针（top）。

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int top;  // 栈顶指针，-1表示空栈
} SeqStack;

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

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

嗯，这里要注意：top指针的初始值。我见过不少新手把top初始化为0，结果逻辑全乱套。我个人习惯用-1表示空栈，这样top指向的就是当前栈顶元素的位置。

避坑指南：我曾经在嵌入式项目中，因为栈空间分配太小，导致递归调用时栈溢出，整个系统直接崩溃。后来我养成了一个习惯：凡是使用顺序栈，一定要做栈满检查。别偷懒，真的。

栈的链式存储

链式存储，就是用链表来实现栈。入栈和出栈都在链表头部操作，时间复杂度O(1)。

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

typedef struct {
    StackNode *top;  // 栈顶指针
    int count;       // 栈中元素个数
} LinkStack;

// 入栈
int push(LinkStack *s, int value) {
    StackNode *node = (StackNode *)malloc(sizeof(StackNode));
    if (!node) return -1;
    node->data = value;
    node->next = s->top;
    s->top = node;
    s->count++;
    return 0;
}

// 出栈
int pop(LinkStack *s, int *value) {
    if (s->top == NULL) return -1;
    StackNode *temp = s->top;
    *value = temp->data;
    s->top = temp->next;
    free(temp);
    s->count--;
    return 0;
}

链式栈的好处是动态扩容，不用担心栈满。但代价是每个节点都要额外存储一个指针。说白了，就是用空间换灵活性。

队列：先进先出的艺术

队列，就像排队买奶茶。先来的人先买到，后来的人排后面。这个规则叫先进先出（FIFO）。

我在项目中用队列处理过网络数据包。数据包到达的顺序就是它们被处理的顺序，用队列再合适不过了。

队列的顺序存储

顺序队列有个坑：假溢出。什么意思？就是数组前面有空位，但rear指针已经到末尾了，你没法再入队了。

解决方案？循环队列！

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
} SeqQueue;

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

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

// 出队
int deQueue(SeqQueue *q, int *value) {
    if (q->front == q->rear) {
        return -1;  // 队空
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return 0;
}
关键点：循环队列中，判断队满的条件是 (rear + 1) % MAXSIZE == front。这意味着数组里始终有一个空位没用。为什么？因为如果不留这个空位，队满和队空的条件就一样了，都是 front == rear。

队列的链式存储

链式队列就简单多了。一个头指针指向队头，一个尾指针指向队尾。

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

typedef struct {
    QNode *front;  // 队头指针
    QNode *rear;   // 队尾指针
} LinkQueue;

// 入队
int enQueue(LinkQueue *q, int value) {
    QNode *node = (QNode *)malloc(sizeof(QNode));
    if (!node) return -1;
    node->data = value;
    node->next = NULL;
    q->rear->next = node;
    q->rear = node;
    return 0;
}

// 出队
int deQueue(LinkQueue *q, int *value) {
    if (q->front == q->rear) return -1;
    QNode *temp = q->front->next;
    *value = temp->data;
    q->front->next = temp->next;
    if (q->rear == temp) {
        q->rear = q->front;
    }
    free(temp);
    return 0;
}

链式队列的入队和出队都是O(1)，而且没有假溢出的问题。我个人的建议是：如果数据量不确定，优先用链式队列。

实际应用场景

光说不练假把式。咱们来看看栈和队列到底用在哪些地方。

数据结构 应用场景 说明
栈 函数调用 函数调用栈，保存返回地址和局部变量
栈 表达式求值 中缀转后缀，计算器实现
栈 括号匹配 编译器检查括号是否成对
栈 撤销操作 Ctrl+Z，回退到上一步
队列 任务调度 CPU进程调度，先来先服务
队列 消息队列 生产者-消费者模型
队列 广度优先搜索 BFS算法，逐层遍历
队列 打印任务 多个文档排队打印
我的经验：在写网络协议栈的时候，我用队列来缓冲接收到的数据包。每个数据包按顺序入队，应用层按顺序读取。这样即使处理速度跟不上接收速度，数据也不会丢失。说白了，队列就是天然的缓冲区。

知识体系总览

下面这张图，把栈和队列的核心知识点串起来了。你可以把它当作复习提纲。

栈与队列知识体系 栈（Stack） 后进先出（LIFO） 顺序存储（数组实现） 链式存储（链表实现） 应用：函数调用、表达式求值 应用：括号匹配、撤销操作 队列（Queue） 先进先出（FIFO） 顺序存储（循环队列） 链式存储（链表实现） 应用：任务调度、消息队列 应用：BFS、打印任务 对比 核心：栈是LIFO，队列是FIFO；顺序存储空间固定，链式存储动态扩容

栈和队列，说白了就是两种操作受限的线性表。但正是这种限制，让它们在某些场景下比普通数组和链表更高效、更安全。

我个人觉得，理解栈和队列的关键不在于记住代码怎么写，而在于理解它们的设计思想。栈的LIFO适合需要回溯的场景，队列的FIFO适合需要按顺序处理的场景。你想想看，是不是这个道理？

一句话总结：栈是后进先出，适合做撤销、函数调用；队列是先进先出，适合做排队、缓冲。选哪个，看你的数据是"后来居上"还是"先来先得"。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →