|
|
教学公告
22软工 第4周安排
[作者：
杨桂芝 发布时间：2023-09-26 17:00:51 浏览次数：466次]
理论课:
讲解第3章的内容 70-90页
重点
1、栈的顺序存储结构
2、队列的链式存储结构（循环队列）
3、栈和队列的操作特性
4、栈和队列的应用
大家可以根据自己的情况进行相应的预习
师说
栈最大的特点是先进后出（LIFO），最先进去的数据最后出来，而队列（Quene）其操作特性是先进先出（FIFO）,最先进去的数据最先出来，栈和队列都是线性表。栈和队列的共同点是只允许在端点处插入和删除元素。
日常生活中队列很常见。还有什么栈的典型例子?
夏天逛超市时，你可能会忍不住想喝一瓶冰饮料降降温。
可是，困扰你的是:放冰箱外头的饮料往往并不冰，而冰箱深处你够不着的地方，才是你想要的。
想想看:冰箱中的饮料应该组织成“队列”还是“栈”?你对超市中的冰箱设计有什么改进性的建议?
比如交试卷，假设学生交试卷的方向都统一，且后来的学生都放在先来学生试卷之上。
如果都是正面朝上交，那么就是一个栈。
如果都是正面朝下交，那么就是一个队列。
跟冰箱一个例子的还有坐电梯，先进后出。交作业，先交的放在下面。弹匣就是栈。
冰箱中的饮料应该组织成“队列”；可以设计成像自动售货机一样竖直摆放的，从最上面放入，从最下面拿取；我们常见的冰箱应该是栈，先进后出。
而如果需要尽可能的能拿到最冰的则需要队列，先进先出。
关于栈与队列的面试题
1、两个栈实现一个队列
2、两个队列实现一个栈
3、一个数组实现两个栈
4、实现一个栈，能够push、pop、min（求栈中最小的数据）
