第17章栈与队列模块

课程目录第17章栈与队列模块

栈与队列模块：栈的数组实现与链表实现、队列的环形缓冲区实现

说实话，栈和队列这两个数据结构，是嵌入式系统里最基础也最实用的东西。我做了十几年嵌入式开发，几乎每个项目都离不开它们。今天咱们就把它们彻底讲透。

栈：后进先出的艺术

栈这个东西，说白了就是一个「后进先出」的容器。你想想看，就像一摞盘子，你最后放上去的，总是最先被拿走。在嵌入式里，函数调用、中断嵌套、表达式求值，全都要靠它。

栈的数组实现

数组实现栈，是最直接的方式。我个人的习惯是，只要栈的最大深度能提前确定，就用数组。为什么？因为简单、高效、没有动态内存分配的开销。

#include <stdint.h>
#include <stdbool.h>

#define STACK_MAX_SIZE 64

typedef struct {
    int32_t data[STACK_MAX_SIZE];
    int32_t top;  // 栈顶索引，-1 表示空栈
} Stack_Array;

void stack_init(Stack_Array *s) {
    s->top = -1;
}

bool stack_push(Stack_Array *s, int32_t value) {
    if (s->top >= STACK_MAX_SIZE - 1) {
        return false;  // 栈满
    }
    s->data[++s->top] = value;
    return true;
}

bool stack_pop(Stack_Array *s, int32_t *value) {
    if (s->top < 0) {
        return false;  // 栈空
    }
    *value = s->data[s->top--];
    return true;
}

bool stack_peek(Stack_Array *s, int32_t *value) {
    if (s->top < 0) {
        return false;
    }
    *value = s->data[s->top];
    return true;
}

bool stack_is_empty(Stack_Array *s) {
    return s->top == -1;
}

我的经验：数组实现栈时，top 初始化为 -1 还是 0，很多人搞混。我习惯用 -1，这样 push 时先 ++top 再赋值，逻辑上更自然。曾经有个同事用 0 初始化，结果 push 第一个元素时直接覆盖了 data[0]，排查了半天。

栈的链表实现

如果栈的最大深度不确定，或者你需要频繁地创建和销毁栈，那就用链表实现。不过要注意，链表有动态内存分配的开销，在资源紧张的 MCU 上要慎用。

#include <stdlib.h>

typedef struct Node {
    int32_t data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;  // 栈顶指针
} Stack_List;

void stack_list_init(Stack_List *s) {
    s->top = NULL;
}

bool stack_list_push(Stack_List *s, int32_t value) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    if (!new_node) {
        return false;  // 内存分配失败
    }
    new_node->data = value;
    new_node->next = s->top;
    s->top = new_node;
    return true;
}

bool stack_list_pop(Stack_List *s, int32_t *value) {
    if (!s->top) {
        return false;  // 栈空
    }
    Node *temp = s->top;
    *value = temp->data;
    s->top = temp->next;
    free(temp);
    return true;
}

注意：链表实现栈时，每次 push 都要 malloc，每次 pop 都要 free。在中断服务函数里千万别这么干——malloc 不是线程安全的，而且可能引起内存碎片。我曾经在一个实时系统里吃过这个亏，后来全部改成了数组实现。

队列：先进先出的哲学

队列和栈正好相反，它是「先进先出」的。就像排队买票，先来的人先买到。在嵌入式里，任务调度、数据缓冲、消息传递，队列无处不在。

环形缓冲区：最优雅的队列实现

用数组实现队列，最头疼的就是「假溢出」问题——明明数组前面还有空位，但 rear 已经走到头了。环形缓冲区完美解决了这个问题。说白了，就是把数组的头尾连起来，形成一个环。

#define QUEUE_SIZE 16

typedef struct {
    int32_t buffer[QUEUE_SIZE];
    uint32_t head;  // 读指针
    uint32_t tail;  // 写指针
    uint32_t count; // 当前元素个数
} RingBuffer;

void rb_init(RingBuffer *q) {
    q->head = 0;
    q->tail = 0;
    q->count = 0;
}

bool rb_enqueue(RingBuffer *q, int32_t value) {
    if (q->count >= QUEUE_SIZE) {
        return false;  // 队列满
    }
    q->buffer[q->tail] = value;
    q->tail = (q->tail + 1) % QUEUE_SIZE;
    q->count++;
    return true;
}

bool rb_dequeue(RingBuffer *q, int32_t *value) {
    if (q->count == 0) {
        return false;  // 队列空
    }
    *value = q->buffer[q->head];
    q->head = (q->head + 1) % QUEUE_SIZE;
    q->count--;
    return true;
}

bool rb_is_full(RingBuffer *q) {
    return q->count == QUEUE_SIZE;
}

bool rb_is_empty(RingBuffer *q) {
    return q->count == 0;
}

关键点：环形缓冲区里，head 和 tail 的移动都用取模运算 (index + 1) % SIZE。这样当指针走到数组末尾时，自动回到开头。我见过有人用 if 判断来重置指针，其实取模运算更简洁，而且现代编译器会优化成位运算，效率很高。

实战：设计一个任务调度队列

好了，理论讲完了，咱们来点实战。假设你要设计一个简单的任务调度器，任务以函数指针的形式存在，按顺序执行。这就是队列的典型应用。

#include <stdint.h>
#include <stdbool.h>

#define TASK_QUEUE_SIZE 32

// 任务类型：无参数、无返回值的函数指针
typedef void (*TaskFunc)(void);

typedef struct {
    TaskFunc tasks[TASK_QUEUE_SIZE];
    uint32_t head;
    uint32_t tail;
    uint32_t count;
} TaskQueue;

void task_queue_init(TaskQueue *q) {
    q->head = 0;
    q->tail = 0;
    q->count = 0;
}

bool task_queue_add(TaskQueue *q, TaskFunc task) {
    if (q->count >= TASK_QUEUE_SIZE) {
        return false;  // 任务队列满了
    }
    q->tasks[q->tail] = task;
    q->tail = (q->tail + 1) % TASK_QUEUE_SIZE;
    q->count++;
    return true;
}

bool task_queue_execute_next(TaskQueue *q) {
    if (q->count == 0) {
        return false;  // 没有待执行的任务
    }
    TaskFunc task = q->tasks[q->head];
    q->head = (q->head + 1) % TASK_QUEUE_SIZE;
    q->count--;
    
    if (task) {
        task();  // 执行任务
    }
    return true;
}

// 调度主循环：不断从队列中取出任务执行
void task_scheduler_run(TaskQueue *q) {
    while (1) {
        if (!task_queue_execute_next(q)) {
            // 队列空了，可以进入低功耗模式或做其他事情
            break;
        }
    }
}

避坑指南：我曾经在一个物联网网关项目里，用这个模式来调度网络数据包的处理任务。一开始没加队列满的保护，结果某个传感器疯狂发数据，直接把任务队列撑爆了，系统死机。从那以后，我所有的队列实现都加了满/空检查，而且会在队列快满时触发告警。

知识体系总览

下面这张图，把本章的核心逻辑串起来了。你可以看到栈和队列的两种实现方式，以及它们在任务调度中的具体应用。

嗯，到这里，栈和队列的核心内容就讲完了。数组实现和链表实现各有优劣，环形缓冲区是队列的最佳实践。任务调度队列这个例子，你可以在很多嵌入式 RTOS 里看到类似的影子。下次写代码时，不妨想想：这个场景用栈还是队列？用数组还是链表？选对了，代码会干净很多。

📚 课程目录

栈与队列模块：栈的数组实现与链表实现、队列的环形缓冲区实现

栈：后进先出的艺术

栈的数组实现

栈的链表实现

队列：先进先出的哲学

环形缓冲区：最优雅的队列实现

实战：设计一个任务调度队列

知识体系总览