第3章 栈与队列

第3章栈和队列数据结构案例教程Page

2案例提出——迷宫问题迷宫问题是取自心理学的一个经典实验。在该实验中，把一只老鼠从一个无顶大盒子的门中放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置以块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图所示，求出一条从入口到出口的通路，或得出没有通路的结论。Page

33.2知识点学习

3.2.1栈栈是一种特殊的线性表，用途十分广泛。将递归算法转换成非递归算法时常常会用到栈，实现二叉树的算法中也会使用栈。栈是一种只能在一端进行插入或删除的线性表。表中允许进行插入、删除操作的一端称为栈顶（top），表的另一端称为栈底（bottom）。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。Page

43.2.1.2栈的顺序存储结构及其基本运算实现#defineMaxsize100;//最多元素个数typedefintElemType;//数据类型typedefstruct{ ElemTypeelem[MaxSize]; inttop; //栈顶指针}SqStack;//顺序栈类型定义Page

5入栈

Page

63.2.1.3栈的链式存储结构及其基本运算的实现Page

7（链栈中数据结点的类型LinkStack定义如下：typedefintElemType;typedefstructlinknode{ElemTypedata;//数据域structlinknode*next;//指针域}LinkStack;Page

83.2.1.4栈的应用举例1、算术表达式的前缀与后缀表达（任何一个表达式都是由操作数、运算符或界限符组成的。在表达式求值问题中的操作数可以是常数、被说明为变量或常量的标识符、表达式；运算符指的是“+”、“-”、“*”、“/”；界限符指的是括号等字符。在本例中的表达式求值问题就是：对于一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。Page

9前缀转后缀算法演示Page

10后缀转前缀算法演示Page

11练习A*b-cA*b+(c-d*e)/fPage

12栈解决迷宫问题算法演示Page

133.2.2队列队列也具有广泛的应用。特别是在操作系统资源分配和排队论中大量地使用队列。本节介绍队列的定义、队列的存储结构和队列的应用。Page

143.2.2.2队列的顺序存储结构及其基本运算的实现顺序队列类型SqQueue定义如下：#defineMaxSize100typedefintElemType;typedefstruct{ElemTypeelem[MaxSize];intfront,rear;//队首和队尾指针}SqQueue;Page

15队列操作Page

16循环队列Page

17循环队列满和空指针判断冲突Page

183.2.2.3队列的链式存储结构及其基本运算的实现队列的链式存储结构是仅在表头删除和表尾插入的单链表，因此一个栈队列需要使用两个指针：指向队头元素的队首指针front和指向队尾元素的队尾指针rear。用于存储队列的单链表简称链队。如图3.11所示的链队列。Page

19链队中数据结点的类型QNode定义typedefintElemType;typedefstructqnode{ElemTypedata;structqnode*next;}QNode;//链队数据结点类型定义Page

20一个链队的动态变化过程Page

213.2.2.4队列的应用举例

求解报数问题设有n个人站成一排，从左向右的编号分别为1~n，现在从左往右报数“1，2，1，2…”，数到“1”的人出列，数到“2”的立即站到队伍的最右端。报数过程反复进行，直到n个人都出列为止。要求给出他们的出列顺序。Page

223.3案例解决

3.3.1用栈来解决迷宫问题【算法思路】用栈来解决迷宫问题，本质上是一个深度优先算法（在教材的树和图时将学到）。我们设置一个数组maze来表示迷宫，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块是墙，不可走。为了算法方便，在迷宫外围加了一道围墙。这样，在不影响迷宫结构的前提下，原数组中的每个方块都有4个方向可判断。本算法用到的数据结构是顺序栈存储结构，采用“穷举求解”的方法，即从入口出发，顺某一方向向前试探，若能走通，则继续往前走，否则，原路退回，换一个方向再继续试探，直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回（称为回溯），需要用一个后进先出的栈来保存入口到当前位置的路径。Page

233.3.2用队列来解决迷宫问题【算法思路】用队列解决迷宫问题，本质上是一个广度优先算法（在教材的树和图章节中将学到）。这里不能