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

讲解第3章的内容 57-78页

重点

1、栈的顺序存储结构、队列的链式存储结构

2、栈和队列的操作特性

3、栈和队列的应用，如3.3表达式求值和火车车厢重排

实验内容于9月27日公布

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

慕课资源

学堂在线 - 清华大学《数据结构》- 中缀表达式求值

讲解思路清晰，启发性强

http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184+sp/courseware/ad1a23c053df4501a3facd66ef6ccfa9/41f9baac0b6a4d348ee1354d5d07c30e/

师说

队列（Quene）是一种数据结构，其操作特性是先进先出（FIFO）,最先进去的数据最先出来，而栈是一种（LIFO）。Quene结构在现实生活中很常见，例如可以用Quene模拟人们在银行里排队，打印机打印文件，飞机等待起飞，互联网上数据包的发送等。

Quene有一个tail与head。通常情况add操作是在tail后面添加元素或者数据，而remove操作是在head（队列的头部进行删除数据）。通常Quene有Peek（查看）、add、remove操作。在add数据之前需要提前判断Quene isFull，在remove数据之前需要判断Quene isEmpty。这些都是保证Quene操作安全稳定的措施。

当向队列中不断从对尾（tail）添加数据时，tail指针不断上移（可以理解为向地址增大的方向的移动）。如果队列空间开辟很小，那么添加较少数数据tail指针就到了顶端。之后若是不及时优化处理就会使队列效率很低。因此采用循环队列或者缓冲环能够解决这一问题，缓冲环不仅在应用层使用广泛，特别是通信或者数据传输时使用方便。

数学界大地震！刚刚，证明黎曼猜想预印本被贴出

https://www.ithome.com/html/it/384983.htm

腾讯机器人实验室首曝光 攻坚“通用人工智能”

https://news.cnblogs.com/n/607961/