一、栈(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语言符号匹配检查器
实现原理
遇到左括号
(
,[
,{
时入栈遇到右括号
)
,]
,}
时与栈顶元素匹配匹配成功则出栈,失败则报错
核心代码段
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; }
三、栈与队列对比
特性 | 栈(Stack) | 队列(Queue) |
---|---|---|
原则 | 后进先出(LIFO) | 先进先出(FIFO) |
操作端 | 仅栈顶操作 | 队尾入队,队头出队 |
应用 | 函数调用、表达式求值 | 任务调度、缓冲处理 |
实现 | 链式/顺序 | 多为循环顺序队列 |
四、嵌入式开发建议
栈的应用场景:
函数调用栈管理
中断处理时的上下文保存
递归算法实现
队列的应用场景:
串口数据接收缓冲
任务消息队列
多线程间的数据传递
内存管理技巧:
静态分配内存池避免碎片
合理设置栈/队列大小
使用valgrind工具检测内存泄漏