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

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

在嵌入式系统开发中，数据结构的选择直接影响着程序的执行效率和资源利用率。作为两种最基础的受限线性表，栈和队列在内存管理、任务调度、中断处理等场景中扮演着关键角色。本文将深入解析它们的实现原理与典型应用场景。

2. 栈：后进先出的数据管理专家

2.1 栈的基本特性与操作原则

栈（Stack）是一种操作受限的线性表，其核心特性可概括为FILO（First In Last Out）原则。这种特性使得栈在以下场景中表现优异：

• 函数调用时的现场保护（保存返回地址和局部变量）
• 中断服务程序中的上下文保存
• 表达式求值和语法分析
• 内存分配中的堆栈管理

栈的操作限制体现在：

• 仅允许在栈顶（Top）进行插入（Push）和删除（Pop）操作
• 栈底（Bottom）作为固定端点不参与常规操作
• 访问元素必须遵循后进先出的顺序

2.2 顺序栈：基于数组的高效实现

顺序栈通过连续内存空间实现，特别适合内存受限的嵌入式环境。其典型数据结构定义如下：

c复制typedef int data_t;  // 数据类型可替换为实际需求

typedef struct seqstack {
    data_t *stack;  // 动态分配的存储空间
    int top;        // 栈顶指针
    int max;        // 栈容量
} seqstack_t;

2.2.1 关键状态判断

状态判断是栈操作安全的前提：

c复制// 栈满判断（假设top初始为-1）
int is_full(seqstack_t *s) {
    return s->top == s->max - 1;
}

// 栈空判断
int is_empty(seqstack_t *s) {
    return s->top == -1;
}

注意：top的初始值设定会影响判断逻辑。若初始设为0（表示下一个可插入位置），则满栈条件应改为top == max

2.2.2 创建与销毁操作

创建顺序栈时需要动态分配内存：

c复制seqstack_t *stack_create(int size) {
    seqstack_t *s = malloc(sizeof(seqstack_t));
    if (!s) return NULL;
    
    s->stack = calloc(size, sizeof(data_t));
    if (!s->stack) {
        free(s);
        return NULL;
    }
    
    s->top = -1;  // 初始化栈顶指针
    s->max = size;
    return s;
}

销毁操作需注意释放顺序：

c复制void stack_destroy(seqstack_t **s) {
    if (!s || !*s) return;
    
    free((*s)->stack);  // 先释放数据空间
    free(*s);           // 再释放结构体
    *s = NULL;          // 避免悬垂指针
}

2.2.3 入栈与出栈实现

入栈操作需要先检查栈状态：

c复制int push(seqstack_t *s, data_t value) {
    if (is_full(s)