3.1 栈和队列的定义和特点

- 栈和队列是两种常用的、重要的数据结构
- 栈和队列是限定插入和删除只能在表的“端点”进行的线性表

后进先出

栈的应用

队列

队列的常见应用

栈和队列是线性表的自己（是插入和删除位置受限的线性表）

3.1.1 栈的定义和特点

栈的相关概念

栈的示意图

入栈的操作示图

出栈的操作示图

思考

栈的相关概念

栈和一般的线性表有什么不同？

3.1.2 队列的定义和特点

队列的相关概念

3.2 案例引入

案例3.1（栈）：进制转换

案例3.2（栈）：括号匹配的检验

案例3.3（栈）：表达式求值

案例3.4（队列）：舞伴问题

3.3. 栈的表示和操作实现

3.3.1 栈的抽象数据类型定义

3.3.2 顺序栈的表示

顺序栈的初始化

判断顺序栈是否为空

求顺序栈的长度

清空顺序栈

销毁顺序栈

顺序栈的入栈

顺序栈的出栈

3.3.3 链栈的表示和实现

链栈的初始化

判断链栈是否为空？

链栈入栈

链栈出栈

取栈顶元素

3.4 栈与递归

递归的定义

若一个对象对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的.
若一个过程直接地或间接地调用自己，则称为这个过程是递归的过程。

递归的优缺点

3.5 队列的表示和操作的实现

3.6 案例分析与实现

循环队列的操作——队列的初始化

循环队列的操作——求队列的长度

循环队列的操作——循环队列的入队

循环队列的操作——循环队列的出队

循环队列的操作——取队头元素

3.5.3 链队——队列的链式表示和实现

链队列的操作——链队列初始化

链队列的销毁

不设p

链队列入队

链队列出队

链队列的队头元素