嵌入式开发中的栈与队列：核心数据结构解析

1. 栈与队列：嵌入式开发中的核心数据结构

在嵌入式系统开发中，数据结构的选择直接影响着程序的执行效率和资源利用率。作为两种最基础的线性数据结构，栈和队列在内存管理、任务调度、中断处理等场景中扮演着关键角色。记得我第一次在STM32上实现RTOS的任务调度时，就因为对队列的理解不够深入，导致任务切换时出现了难以排查的内存溢出问题。这段经历让我深刻认识到，扎实的数据结构基础对嵌入式开发者而言绝非可有可无。

2. 栈：后进先出的精密工具

2.1 栈的核心特性与应用场景

栈(Stack)是一种限定仅在表尾进行插入和删除操作的线性表，这个特殊的表尾我们称为栈顶(top)，而表头则称为栈底(bottom)。栈遵循LIFO(Last In First Out)原则，就像我们日常生活中叠放的盘子，总是最先取用最上面那个最后放进去的盘子。

在嵌入式领域，栈的应用无处不在：

• 函数调用栈：每次函数调用时，返回地址、局部变量和参数都会被压入栈中。以ARM Cortex-M为例，在进入中断服务程序(ISR)时，处理器会自动将xPSR、PC、LR、R12及R0-R3压入栈中
• 中断处理：在RTOS中，每个任务都有自己独立的栈空间，用于保存任务上下文
• 内存管理：uC/OS-II等实时操作系统使用栈结构来管理任务控制块(TCB)
• 表达式求值：编译器利用栈来实现复杂的表达式计算和语法分析

c复制// 典型的函数调用栈示例
void func_A(int x) {
    int y = x * 2;
    func_B(y);
}

void func_B(int z) {
    char buffer[16];
    // ...
}

当func_A调用func_B时，栈空间的变化如下图所示（假设从地址0x20001000开始）：

2.2 栈的两种实现方式

2.2.1 顺序栈：静态内存的高效利用

顺序栈使用连续的内存空间存储数据，特别适合内存受限的嵌入式环境。在STM32的HAL库中，我们常看到如下实现：

c复制#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10

typedef struct {
    uint8_t *base;    // 栈底指针
    uint8_t *top;     // 栈顶指针
    uint16_t stacksize; // 当前分配的空间大小(单位：字节)
} SqStack;

HAL_StatusTypeDef InitStack(SqStack *S) {
    S->base = (uint8_t *)malloc(STACK_INIT_SIZE);
    if(!S->base) return HAL_ERROR;
    
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return HAL_OK;
}

关键点说明：

1. base指向栈底，作为基准位置
2. top初始等于base，随着元素入栈向上增长
3. 当top - base >= stacksize时需要动态扩容

注意：在资源受限的嵌入式系统中，应谨慎使用动态扩容。更好的做法是根据应用场景预先评估最大栈深度，直接分配足够空间。

2.2.2 链栈：动态内存的灵活管理

链栈通过链表实现，每个节点包含数据和指向下一节点的指针：

c复制typedef struct StackNode {
    uint32_t data;           // 存储数据
    struct StackNode *next;  // 指向下一节点
} StackNode, *LinkStackPtr;

typedef struct {
    LinkStackPtr top;    // 栈顶指针
    uint16_t count;      // 栈元素计数器
} LinkStack;

链栈的入栈操作示例：

c复制HAL_StatusTypeDef Push(LinkStack *S, uint32_t e) {
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    if(!p) return HAL_ERROR;
    
    p->data = e;
    p->next = S->top;  // 新节点指向原栈顶
    S->top = p;        // 更新栈顶指针
    S->count++;
    return HAL_OK;
}

两种实现的对比选择：