13、栈与队列：顺序栈、链式栈、循环队列、链式队列的实现与应用

栈和队列，这两个数据结构在嵌入式系统里太常用了。我刚开始做嵌入式那会儿，总觉得它们就是教科书上的概念，直到自己写Bootloader和通信协议栈时，才发现它们简直是底层代码的骨架。

说白了，栈就是后进先出，队列就是先进先出。你想想看，函数调用时的返回地址、中断嵌套的现场保护，哪个不是栈在背后撑着？而串口数据缓冲、任务调度队列，又哪个离得开队列？

今天咱们就把这两种结构的四种实现方式——顺序栈、链式栈、循环队列、链式队列——彻底讲透。我会把我在项目中踩过的坑、总结的技巧都抖出来。

13.1 顺序栈：最简单，也最容易翻车

顺序栈就是用数组实现的栈。优点是访问快、代码简单，缺点嘛——容量固定，用之前就得想好最大深度。

我在一个传感器数据采集项目里用过顺序栈。当时要缓存最近100次采样的历史值，用于滑动窗口滤波。用顺序栈正合适，因为深度已知，而且不需要动态内存分配——这在资源紧张的MCU上是个大优势。

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

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

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

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

⚠️ 我曾经踩过的坑： 顺序栈的top指针初始值，有人用0表示空栈，有人用-1。我个人习惯用-1，这样入栈时先++再赋值，逻辑上更自然。但如果你用0，记得入栈时先赋值再++。两种风格都行，但整个项目必须统一，否则调试时能把你逼疯。

13.2 链式栈：动态扩容，但小心内存碎片

链式栈用链表实现，每个节点包含数据和指向下一个节点的指针。它的好处是理论上容量只受堆内存限制，适合数据量不确定的场景。

我记得在一个多任务操作系统的移植项目中，任务栈就是用链式栈实现的。因为每个任务需要的栈深度不同，用顺序栈要么浪费内存，要么不够用。链式栈按需分配，灵活多了。

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

typedef struct {
    StackNode *top;  // 栈顶指针
} LinkedStack;

// 入栈
int LinkedStack_Push(LinkedStack *s, int val) {
    StackNode *node = (StackNode *)malloc(sizeof(StackNode));
    if (!node) return -1;
    node->data = val;
    node->next = s->top;
    s->top = node;
    return 0;
}

// 出栈
int LinkedStack_Pop(LinkedStack *s, int *val) {
    if (!s->top) return -1;
    StackNode *tmp = s->top;
    *val = tmp->data;
    s->top = tmp->next;
    free(tmp);
    return 0;
}

💡 我的建议： 在嵌入式环境里，malloc/free要慎用。频繁分配释放会导致内存碎片，运行几天后可能就分配不出连续内存了。如果非要用链式栈，我建议预先分配一个节点池，用静态链表的方式管理，这样既灵活又可控。

13.3 循环队列：环形缓冲区，通信的命脉

循环队列，也叫环形缓冲区，是嵌入式通信中最常用的数据结构。串口接收、SPI收发、网络数据包缓冲，几乎处处可见它的身影。

为什么用循环队列？因为普通队列出队后，前面的空间就浪费了。循环队列把数组首尾相连，让空间可以重复利用。说白了，就是一块内存转着圈用。

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front;  // 队头，指向第一个元素
    int rear;   // 队尾，指向下一个插入位置
} CircularQueue;

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

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

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

🔑 关键点： 循环队列判空判满是个经典问题。上面代码里，我牺牲了一个存储单元来区分空和满——当(rear+1)%size == front时认为队满。你也可以用额外变量记录元素个数，或者加一个flag标记。我个人偏爱牺牲一个单元的方式，因为省内存、速度快。

13.4 链式队列：灵活但开销大

链式队列用链表实现，有队头和队尾两个指针。入队从队尾插入，出队从队头删除。它的优势是动态长度，适合数据量波动大的场景。

我在一个物联网网关项目里用过链式队列。当时要缓存来自多个传感器的上报数据，每个传感器的数据量不确定，而且上报频率也不同。用链式队列，每个传感器一个队列，来多少数据存多少，系统空闲时再批量处理。

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

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

// 入队
int LinkedQueue_Enqueue(LinkedQueue *q, int val) {
    QNode *node = (QNode *)malloc(sizeof(QNode));
    if (!node) return -1;
    node->data = val;
    node->next = NULL;
    if (q->rear) {
        q->rear->next = node;
    } else {
        q->front = node;
    }
    q->rear = node;
    return 0;
}

// 出队
int LinkedQueue_Dequeue(LinkedQueue *q, int *val) {
    if (!q->front) return -1;
    QNode *tmp = q->front;
    *val = tmp->data;
    q->front = tmp->next;
    if (!q->front) {
        q->rear = NULL;
    }
    free(tmp);
    return 0;
}

⚠️ 注意： 链式队列出队时，如果删除的是最后一个节点，记得把rear也置为NULL。我见过不少代码只更新front，结果队列空了rear还指着已释放的内存，下次入队时直接野指针崩溃。

13.5 四种实现对比与选型

到底用哪种？没有绝对答案，得看场景。我整理了一张对比表，方便你快速决策。

特性 顺序栈 链式栈 循环队列 链式队列
存储结构 数组 链表 数组 链表
容量 固定 动态 固定 动态
访问速度 O(1) O(1) O(1) O(1)
内存开销 低 高（每个节点额外指针） 低 高
适用场景 深度已知、实时性高 深度不确定、内存充足 通信缓冲、数据流处理 数据量波动大、动态管理
嵌入式推荐度 ★★★★★ ★★★☆☆ ★★★★★ ★★★☆☆

13.6 知识体系总览

下面这张图把本章的核心逻辑串起来了。你可以看到栈和队列的两种实现方式，以及它们各自的应用场景。

栈与队列知识体系 栈 (LIFO) 顺序栈 链式栈 函数调用 中断现场保护 表达式求值 任务栈 深度不确定场景 队列 (FIFO) 循环队列 链式队列 串口缓冲 网络数据包 音频/视频流 多传感器缓存 任务调度队列 选型核心原则 资源受限 → 顺序结构（数组） 动态变化 → 链式结构（链表）

13.7 实战中的避坑指南

最后，分享几个我在项目中用栈和队列时总结的经验。

  • 初始化一定要做：不管是顺序结构还是链式结构，使用前必须初始化。我见过太多bug是因为局部变量没初始化，top或front指向随机值，一操作就崩。
  • 判空判满不能省：入栈/入队前判满，出栈/出队前判空。这个检查看似多余，但在多任务环境下，少一个检查就可能造成数据覆盖或读取野指针。
  • 中断中慎用动态内存：如果在中断服务函数里用链式栈或链式队列，malloc/free要格外小心。中断中分配内存可能导致优先级反转，甚至死锁。我一般会在中断里用循环队列，配合DMA使用。
  • 考虑原子操作：在多任务系统中，对栈和队列的操作要保证原子性。最简单的办法是关中断，或者用自旋锁。否则一个任务在读数据，另一个任务在写数据，读到的可能是半残的数据。

嗯，栈和队列的内容就讲到这里。这两种结构看似简单，但用好了能解决嵌入式开发中80%的数据缓冲问题。下次你写通信协议或者任务调度时，不妨想想今天讲的这些实现细节。

专注资料整理

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