2022年 stack设计与实现专题讲座.pdf

Stack 设计与实现专题讲座 Stack 基本概念 栈是一种特殊的线性表 栈仅能在线性表的一端进行操作 栈顶(Top)：允许操作的一端 栈底(Bottom)：不允许操作的一端 Stack 的常用操作 创建栈 销毁栈 清空栈 进栈 出栈 获取栈顶元素 获取栈的大小 C 语言描述=====》栈的设计与实现 人生财富库积累 #ifndef _MY_STACK_H_ #define _MY_STACK_H_ typedef void Stack; Stack* Stack_Create(); void Stack_Destroy(Stack* stack); void Stack_Clear(Stack* stack); int Stack_Push(Stack* stack, void* item); void* Stack_Pop(Stack* stack); void* Stack_Top(Stack* stack); int Stack_Size(Stack* stack); #endif //_MY_STACK_H_ 栈的顺序存储设计与实现 1、基本概念 2、设计与实现 头文件 #ifndef __MY_SEQLIST_H__ #define __MY_SEQLIST_H__ typedef void SeqList; typedef void SeqListNode; SeqList* SeqStack_Create(int capacity); void SeqStack_Destroy(SeqStack * list); void SeqStack_Clear(SeqStack * list); int SeqStack_Length(SeqStack * list); int SeqStack_Capacity(SeqStack * list); int SeqStack_Insert(SeqStack * list, SeqListNode* node, int pos); SeqListNode* SeqList_Get(SeqList* list, int pos); SeqListNode* SeqList_Delete(SeqList* list, int pos); #endif //__MY_SEQLIST_H__ 栈的链式存储设计与实现 1、基本概念 2、设计与实现 头文件 #ifndef _MY_LINKSTACK_H_ #define _MY_LINKSTACK_H_ typedef void LinkStack; LinkStack* LinkStack_Create(); void LinkStack_Destroy(LinkStack* stack); void LinkStack_Clear(LinkStack* stack); int LinkStack_Push(LinkStack* stack, void* item); void* LinkStack_Pop(LinkStack* stack); void* LinkStack_Top(LinkStack* stack); int LinkStack_Size(LinkStack* stack); #endif //_MY_LINKSTACK_H_ 栈的应用 应用 ：就近匹配 1 几乎所有的编译器都具有检测括号是否匹配的能力 如何实现编译器中的符号成对检测？ #include stdio.h int main() {int a[4][4]; int (*p)[4];p a[0];return 0; 算法思路 从第一个字符开始扫描 当遇见普通字符时忽略，当遇见左符号时压入栈中 当遇见右符号时从栈中弹出栈顶符号，并进行匹配 匹配成功：继续读入下一个字符 匹配失败：立即停止，并报错 结束： 成功: 所有字符扫描完毕，且栈为空 失败：匹配失败或所有字符扫描完毕但栈非空 当需要检测成对出现但又互不相邻的事物时 可以使用栈 “后进先出”的特性 栈非常适合于需要 “就近匹配”的场合 计算机的本质工作就是做数学运算，那计算机可以读入字符串 “ ”并计算值吗？ 9 + (3 - 1) * 5 + 8 / 2 应用2：中缀 后缀 计算机的本质工作就是做数学运算，那计算机可以读入字符串 “9 + (3 - 1) * 5 +