数据结构与算法（c 描述）-z6尊龙旗舰厅

理论课:

讲解第3章的内容 70-90页

重点

1、栈的顺序存储结构

2、队列的链式存储结构（循环队列）

3、栈和队列的操作特性

4、栈和队列的应用

大家可以根据自己的情况进行相应的预习

师说

栈最大的特点是先进后出（lifo），最先进去的数据最后出来，而队列（quene）其操作特性是先进先出（fifo）,最先进去的数据最先出来，栈和队列都是线性表。栈和队列的共同点是只允许在端点处插入和删除元素。

日常生活中队列很常见。还有什么栈的典型例子?
夏天逛超市时，你可能会忍不住想喝一瓶冰饮料降降温。
可是，困扰你的是:放冰箱外头的饮料往往并不冰，而冰箱深处你够不着的地方，才是你想要的。

想想看:冰箱中的饮料应该组织成“队列”还是“栈”?你对超市中的冰箱设计有什么改进性的建议?

比如交试卷，假设学生交试卷的方向都统一，且后来的学生都放在先来学生试卷之上。

如果都是正面朝上交，那么就是一个栈。

如果都是正面朝下交，那么就是一个队列。

跟冰箱一个例子的还有坐电梯，先进后出。交作业，先交的放在下面。弹匣就是栈。

冰箱中的饮料应该组织成“队列”；可以设计成像自动售货机一样竖直摆放的，从最上面放入，从最下面拿取；我们常见的冰箱应该是栈，先进后出。
而如果需要尽可能的能拿到最冰的则需要队列，先进先出。

关于栈与队列的面试题

1、两个栈实现一个队列

2、两个队列实现一个栈

3、一个数组实现两个栈

4、实现一个栈，能够push、pop、min（求栈中最小的数据）