嵌入式 数据结构学习(五) 栈与队列的实现与应用

一、栈(Stack)详解

1. 栈的基本概念

栈的定义与特性

• 后进先出(LIFO)：最后入栈的元素最先出栈

• 操作限制：只能在栈顶进行插入(push)和删除(pop)操作

• 存储位置：我们实现的链栈位于堆区(malloc分配)，系统栈区存储函数调用信息

栈的示意图（top为栈顶指针）

2. 链栈的基本操作实现

(1) 创建链栈

c

LinkStack* CreateLinkStack()
{
    LinkStack* ls = (LinkStack*)malloc(sizeof(LinkStack));
    if(NULL == ls)
    {
        fprintf(stderr,"CreateLinkStack malloc\n");
        return NULL;
    }
    
    ls->top = NULL;   // 初始化栈顶指针
    ls->clen = 0;     // 初始化栈长度
    return ls;
}

(2) 入栈操作

c

int PushLinkStack(LinkStack* ls, DATATYPE* data)
{
    LinkStackNode* newnode = malloc(sizeof(LinkStackNode));
    if(NULL == newnode)
    {
        fprintf(stderr,"PushLinkStack malloc\n");
        return 1;
    }
    
    memcpy(&newnode->data, data, sizeof(DATATYPE));
    newnode->next = ls->top;  // 新节点指向原栈顶
    ls->top = newnode;        // 更新栈顶指针
    ls->clen++;
    return 0;
}

(3) 出栈操作

c

int PopLinkStack(LinkStack* ls)
{
    if(IsEmptyLinkStack(ls)) return 1;
    
    LinkStackNode* tmp = ls->top;
    ls->top = ls->top->next;  // 栈顶指针下移
    free(tmp);                // 释放原栈顶节点
    ls->clen--;
    return 0;
}

(4) 其他操作

c

// 判断栈空
int IsEmptyLinkStack(LinkStack* ls)
{
    return 0 == ls->clen;
}

// 获取栈顶元素
DATATYPE* GetTopLinkStack(LinkStack* ls)
{
    if(IsEmptyLinkStack(ls)) return NULL;
    return &ls->top->data;
}

// 获取栈长度
int GetSizeLinkStack(LinkStack* ls)
{
    return ls->clen;
}

//摧毁链栈

int DestroyLinkStack(LinkStack* ls) 
{ 
    int len = GetSizeLinkStack(ls); // 获取栈当前长度 
    for(int i = 0; i < len; ++i) 
    { 
        PopLinkStack(ls); // 循环调用出栈函数释放所有节点 
    } 
    free(ls); // 释放链栈结构体本身的内存 
    return 0; // 成功返回0 
}

3. 栈的应用实例：C语言符号匹配检查器

实现原理

1. 遇到左括号(, [, {时入栈

2. 遇到右括号), ], }时与栈顶元素匹配

3. 匹配成功则出栈，失败则报错

核心代码段

c

while (*tmp)
{
    switch (*tmp)
    {
        case '(': case '[': case '{':
            data.c = *tmp;
            data.row = row;
            data.col = col;
            PushLinkStack(ls, &data);
            break;
            
        case ')':
            top = GetTopLinkStack(ls);
            if (top && '(' == top->c) {
                PopLinkStack(ls);
            } else {
                // 错误处理...
            }
            break;
        // 其他右括号处理类似...
    }
    // 更新行列计数...
}

二、队列(Queue)详解

1. 队列的基本概念

队列的定义与特性

• 先进先出(FIFO)：最先入队的元素最先出队

• 操作限制：队尾(rear)插入，队头(front)删除

• 循环队列：通过取模运算实现空间的循环利用

队列示意图

2. 顺序队列的基本操作实现

(1) 创建顺序队列

c

SeqQueue* CreateSeqQue(int len)
{
    SeqQueue* sq = (SeqQueue*)malloc(sizeof(SeqQueue));
    if(NULL == sq) return NULL;
    
    sq->array = malloc(sizeof(DATATYPE)*len);
    if(NULL == sq->array)
    {
        free(sq);
        return NULL;
    }
    
    sq->head = 0;    // 初始化头指针
    sq->tail = 0;    // 初始化尾指针
    sq->tlen = len;  // 记录队列容量
    return sq;
}

(2) 入队操作

c

int EnterSeqQue(SeqQueue* sq, DATATYPE* data)
{
    if(IsFullSeqQue(sq)) return 1;
    
    memcpy(&sq->array[sq->tail], data, sizeof(DATATYPE));
    sq->tail = (sq->tail + 1) % sq->tlen;  // 循环队列处理
    return 0;
}

(3) 出队操作

c

int QuitSeqQue(SeqQueue* sq)
{
    if(IsEmptySeqQue(sq)) return 1;
    
    sq->head = (sq->head + 1) % sq->tlen;  // 头指针后移
    return 0;
}

(4) 队满/队空判断

c

// 判断队空
int IsEmptySeqQue(SeqQueue* sq)
{
    return sq->head == sq->tail;
}

// 判断队满
int IsFullSeqQue(SeqQueue* sq)
{
    return (sq->tail + 1) % sq->tlen == sq->head;
}

三、栈与队列对比

四、嵌入式开发建议

1. 栈的应用场景：

   • 函数调用栈管理

   • 中断处理时的上下文保存

   • 递归算法实现

2. 队列的应用场景：

   • 串口数据接收缓冲

   • 任务消息队列

   • 多线程间的数据传递

3. 内存管理技巧：

   • 静态分配内存池避免碎片

   • 合理设置栈/队列大小

   • 使用valgrind工具检测内存泄漏