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

理论课

讲解第 3章内容70-86页

实验课

实验2 线性表

重点

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

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

3、栈和队列的操作特性

4、栈和队列的应用

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

师说:

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

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

栈的应用举例:https://blog.csdn.net/gavin_john/article/details/71374487

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

https://blog.csdn.net/weixin_51430607/article/details/115679019?utm_term=%E9%93%B6%E8%A1%8C%E4%B8%9A%E5%8A%A1%E9%98%9F%E5%88%97%E7%AE%80%E5%8D%95%E6%A8%A1%E6%8B%9F%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84&utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduweb~default-1-115679019&spm=3001.4430

经典面试题:

· 实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间复杂度为O(1)

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

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

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

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

https://blog.csdn.net/z_x_m_m_q/article/details/82804923

https://blog.csdn.net/hansionz/article/details/81636768

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

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