当前位置：首页 > news >正文

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

news 2025/7/7 11:51:44

一、栈(Stack)详解

1. 栈的基本概念

栈的定义与特性

后进先出(LIFO)：最后入栈的元素最先出栈
操作限制：只能在栈顶进行插入(push)和删除(pop)操作
存储位置：我们实现的链栈位于堆区(malloc分配)，系统栈区存储函数调用信息

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

2. 链栈的基本操作实现

(1) 创建链栈

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) 入栈操作

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) 出栈操作

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) 其他操作

// 判断栈空
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语言符号匹配检查器

实现原理

遇到左括号(, [, {时入栈
遇到右括号), ], }时与栈顶元素匹配
匹配成功则出栈，失败则报错

核心代码段

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) 创建顺序队列

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) 入队操作

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) 出队操作

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

(4) 队满/队空判断

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

三、栈与队列对比

特性	栈(Stack)	队列(Queue)
原则	后进先出(LIFO)	先进先出(FIFO)
操作端	仅栈顶操作	队尾入队，队头出队
应用	函数调用、表达式求值	任务调度、缓冲处理
实现	链式/顺序	多为循环顺序队列