数据结构与算法（c 描述）-k8凯发旗舰

20软件工程《数据结构与算法》 第四周安排

理论课

讲解第 3章内容70-86页

实验课

实验2 线性表

重点

1、栈的顺序存储结构（顺序栈）

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

3、栈和队列的操作特性

4、栈和队列的应用

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

师说:

栈和队列的共同点是只允许在端点处插入和删除元素。栈是限定仅在栈顶进行插入和删除操作的线性表，栈的特点是后进先出。队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头，队列的特点是先进先出。

在日常生活中，很多问题可以归结到栈和队列的应用问题。例如，排队购物的现象就可以看做是队列。在计算机学科的应用中，栈和队列的应用就更多了，例如，编译系统、消息队列等。

栈的应用举例:

队列的应用举例:银行业务队列简单模拟 :

经典面试题:

·实现一个栈，要求实现push(出栈)、pop(入栈)、min(返回最小值)的时间复杂度为o(1)

·使用两个栈实现一个队列

·使用两个队列实现一个栈

·元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5)，出栈序列为 (4,5,3,2,1)

·一个数组实现两个栈(共享栈)

有同学学过栈和队列后，成功应用队列在自己的竞赛作品中，你有打算应用么?

成功来自于勤奋，智慧不是自然的恩惠，而是勤奋的结果。只有把握勤奋的钥匙，才能打开知识宝库的大门。