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