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