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

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

理论课:

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

实验课:

实验2 线性表

重点

1、栈的顺序存储结构

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

3、栈和队列的操作特性

4、栈和队列的应用

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

师说

栈最大的特点是先进后出，日常生活中有很多相关的例子:（1）逆序输出是栈经常用到的一个应用场景，首先把所有元素依次入栈，然后把所有元素出栈并输出，这样就实现了逆序输出。（2）在我们日常编程中，括号都是成对出现的，比如“()”“[]”“{}”“”这些成对出现的符号。那么具体处理的方法就是:凡是遇到括号的前半部分，即把这个元素入栈，凡是遇到括号的后半部分就比对栈顶元素是否该元素相匹配，如果匹配，则前半部分出栈，否则就是匹配出错。

其他应用，链接所示，这里讲述了栈的四个应用的例子,包括进制转换、括号匹配检验、迷宫求解以及中缀表达式转后缀表达式和表达式的求值。

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

慕课资源

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

讲解思路清晰，启发性强

关于栈与队列的面试题

1、两个栈实现一个队列

2、两个队列实现一个栈

3、一个数组实现两个栈

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