西安免费网站建站模板,成都市住房和城乡建设局电话,百度seo优化按年收费,网站模板大全官网名人说#xff1a;莫听穿林打叶声#xff0c;何妨吟啸且徐行。—— 苏轼《定风波莫听穿林打叶声》 本篇笔记整理#xff1a;Code_流苏(CSDN)#xff08;一个喜欢古诗词和编程的Coder#x1f60a;#xff09; 目录 0、思维导图栈和队列1、栈1#xff09;特点2#xff0… 名人说莫听穿林打叶声何妨吟啸且徐行。—— 苏轼《定风波·莫听穿林打叶声》 本篇笔记整理Code_流苏(CSDN)一个喜欢古诗词和编程的Coder 目录 0、思维导图栈和队列1、栈1特点2分类3应用 2、队列1特点2分类3应用 0、思维导图 栈和队列
1、栈
栈是一种遵循后进先出LIFOLast In First Out原则的数据结构。可以想象成一摞盘子最后放上去的盘子会最先拿掉。
1特点
“后进先出LIFO”
2分类
①顺序栈
采用顺序存储的栈结构。 1️⃣入栈和出栈 2️⃣判断栈满空 说明栈顶指针top表示当前栈顶元素的位置、MAXSIZE是数组容量大小。 a.满top MAXSIZE - 1 b.空top -1
②链栈
采用链式存储的栈结构
a.入栈和出栈 b.判断栈满空 说明top为栈顶指针 栈满一般不存在此类情况 栈空top NULL
③共享栈 共享栈通常是指在程序设计中多个线程共享同一个栈空间的概念如下图两个顺序栈共享内存空间。
判断栈空、栈满
栈空top0-l 时0号栈为空toplMaxSize时1号栈空栈满两个栈顶指针相邻(topl-top0l)。时
3应用
①函数调用一般递归较为常见
②表达式求值 前缀表达式 运算符位于操作数之前 中缀表达式 运算符位于操作数之间 后缀表达式 运算符位于操作数之后 前中后缀转换 1️⃣中缀转前缀 转换步骤 1、加括号 2、前移运算符 3、去括号 举例 2️⃣中缀转后缀 转换步骤 1、加括号 2、后移运算符 3、去括号 举例
③括号匹配 ④深度优先搜索
2、队列
队列是一种遵循先进先出FIFOFirst In First Out原则的数据结构。可以想象成排队买票最先排队的人最先买到票。 1特点
“ 先进先出FIFO”
2分类
①顺序队列
使用顺序存储的队列结构 入队和出队 判断满与空 队头指针front和队尾指针rear分别指示当前队头元素和队尾元素的位置 满rear MAXSIZE - 1 空front rear
②循环队列
队列的头尾相接的顺序队列结构 判断满与空 队头指针front和队尾指针rear分别指示当前队头元素和队尾元素的位置。Maxsize指队列的数组大小。 满(rear 1) % Maxsize front其中%表示取模运算。 空front rear。 元素个数(rear - front Maxsize) % Maxsize
③链式队列
使用链式存储的队列结构 判断满与空 说明头指针front和尾指针rear分别指向当前队头元素和队尾元素。 满一般不存在此类情况空front NULL且rear NULL。
④双端队列 两端都可以进行入队和出队操作的队列 输出受限的双端队列 一端可插入和删除另一端只允许插入 输入受限的双端队列 一端可进行插入和删除另一端只允许删除
3应用
①层次遍历
②计算机系统 资源管理 消息缓冲 页面替换算法
③广度优先搜索 上述内容笔记部分图片来源网络侵删。 参考内容 1.《王道数据结构》 2.【LeetCode】括号匹配问题 3.数据结构电子讲义 4.数据结构共享栈 Code_流苏(CSDN)一个喜欢古诗词和编程的Coder 点赞加关注收藏不迷路本篇文章对你有帮助的话还请多多点赞支持
