山东大学《数据结构》讲义03栈和队列.docx

第三章栈和队列
内容概述
从数据结构角度来看，栈和队列是两种特殊的线性表，其特殊性表达在它们的 基本操作是线性表操作的子集，因此它们是限定性的数据结构。从抽象数据类型 角度来看，它们是不同于线性表的两类重要的抽象数据类型。由于栈和队列在实 际应用中的广泛性和其操作的特殊性，本章从栈和队列的抽象数据类型定义、栈 和队列的顺序表示与实现、栈和队列的链式表示与实现、栈和队列的应用等几个 方面进行专门讨论。
重点与难点
重点为栈和队列的运算，循环队列。难点为栈与递归的关系，栈与队列的应用。
思考.栈是具有什么特性的线性表？
1 .队列是具有什么特性的线性表？
2 .分析栈与递归的关系。
3 .假设一个栈的入栈序列是1, 2, 3,…,n,其输出序列为pl,p2,p3,…,pn, 假设 pl=n,那么 pi=?
4 .设有一个顺序栈S,元素sl,s2,s3,s4,s5,s6依次进栈,如果6个元素的出栈 顺序为s2,s3,s4,s6,s5zsl,那么顺序栈的容量至少应为多少？
5 .为什么要循环队列？在循环队列中队列空、满的评定标准是什么？
6 .利用两个栈模拟一个队列的入队、出队、判断队空等运算。
第一节栈栈是一种具有''后进先出〃特性的线性表。这种特性对其操作有何影响呢？其存储 结构相对于一般线性表又会有哪些变化？本节将从栈的定义、抽象类型定义、栈 的顺序与链式存储结构等方面入手解答上述问题。
1、栈的定义1、栈的定义
栈(Stack)又称堆栈，是一种特殊的线性表，可定义为插入、删除和访问只能 在某一端进行的线性数据结构。堆栈允许插入、删除和访问的一端称为栈顶
(Top),另一端称为栈底(Bottom) o栈顶的第一个元素被称为栈顶元素。不 含数据元素的空表称为空栈。
向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使 之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删 除掉，使其下面的相邻元素成为新的栈顶元素。
堆栈的性质决定它的数据是按''先进后出〃的顺序被访问，即最先存储的元素最后 被访问、删除，最后存储的元素最先被访问、删除，所以栈也称为、'LIFO〃
(Last_In,First_Out) □栈的模型在日常生活中是普遍存在的，如铁路列车调度系统等，在计算机科学中, 栈是一种非常有用的数据结构。实际上，TurboC在将参数传递给函数时，就使 用堆栈。
我们应该注意到：栈是一种动态的数据结构，也就是说，随着对栈进行插入和删 除等不同的操作，其结点个数、内容等将会不断发生变化。
径。如图35 图中路径为该迷宫探索的全过程，包含退回至「前一通道块〃的操 作过程。
本算法的描述如下：
StatusMazeRath(MazeTypemaze,RosTypestart,PosTypeend){〃假设迷宫maze中存在从入口 start到出口 end的通道，那么求得一条路径存放在
栈中(从〃栈底到栈顶)，并返回TRUE；否那么返回FALSEInitStack(S); curpos=start;〃设定''当前位置〃为''入 口 位置”
curst叩二1;〃探藁第一步do{
if(Pass(curpos,maze)){〃当前位置可以通过，即是未曾走过的通道块
FootPrint(cu rpos,maze); 〃留下足迹
e=(curstep,curpos,l);
Push(S,e);〃加入路径
if(curpos==end)retu「n(TRUE);〃到达终点(出 口)
curpos=NextPos(curposz 1); 〃下一位置是当前位置的东邻
cu rstep++;〃探集下一步
)//if
else{
〃当前位置不能通过
if(!StackEmpty(S)){
Pop(S,e);
while(e,di==4&&!StackEmpty(S)){
Pop ⑸ e);}//while
if(e.di<4){
e.di++; 〃换下一个方向探索
Push(S,e);
curpos=NextPos(e.pos,e.di);
〃设定当前位置是该新方向上的通道块
}//if(e.di<4)
}//if(!StackEmpty(S))
}//else
}while(!StackEmpty(S));
return(FALSE);
}//MazePath
StatusPass(PosTypepos,MazeTypemaze){
if(maze[pos.x] [pos.y]==0)returnOK;
elsereturnO;
)
voidFootPnnt(PosTypepos,MazeTypemaze){
maze[pos.x][pos.y]=2;//标记为已走过该方块
voidNextPos( PosT y pe&pos, i ntd i){
switch(di){
casel:(pos).y+=1; break;〃向东
case2:(pos).x+=1; break;〃向南
case3 :(pos) ,y-=l;break;〃向西
ca se4:(pos) .x-=l;break;〃向北
)
)算法3-13迷宫求解算法
4、栈与递归实现的关系4、栈与递归实现的关系
栈还有一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通 过一系列的调用语句间接地调用自己的函数，称作递归函数。
在程序设计中，递归是一个非常重要的工具。第一，有很多数学函数是通过 递归定义的，比方阶乘函数：
和 2 阶 Fibonacci 数歹(J：
等；第二，由于有的数据结构本身固有的递归特性，它们的操作可以通过递归进 行描述，比方二叉树、广义表等；第三，有的问题虽然本身不具备明显的递归结 构，但是运用递归进行问题的求解相比迭代方法更简单，比方八皇后问题、Hanoi 塔问题等。
作为递归函数，在其执行过程中，需要屡次进行自我调用。为了理解这个问 题，我们先看任意两个函数之间是如何进行调用的。在高级语言编制的程序中， 调用函数和被调用函数之间的链接及信息交换需要通过栈来进行。通常，当在一 个函数的运行期间调用另一个函数时，系统在运行被调用函数前要先完成以下工 作：(1)将所有的实在参数、返回地址等信息传递给被调用函数保存；(2)为 被调用函数的局部变量分配存储区；(3)将控制转移到被调用函数的入口。同 样，从被调用函数返回调用函数前，系统也需要完成一些工作：(1)保存被调 用函数的计算结果；(2)释放被调用函数的数据区；(3)依照被调用函数保存 的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照''后调 用先返回〃的原那么，上述函数之间的信息传递和控制转移必须通过栈来实现。系 统设置一个栈作为整个程序运行时所需的数据空间，每调用一个函数就为其在栈 顶分配一个存储区，每从一个函数退出时就释放其存储区，那么当前正运行的函数 的数据区必在栈顶。实际上，在调用函数和被调用函数之间不一定传递参数的值, 也可以传递参数的地址。通常，每个程序设计语言都有它自己的参数传递方法。 下面举一个例子来具体说明函数调用的工作原理。在图3,6(c)所示的程序段中, 主函数main中调用了函数first,而在函数first中又调用了函薮second,那么当前 系统正在执行函数second中某个语句时栈的状态如图3.6(a),从函数second 退出后正执行函数first中某个语句时栈的状态如图3.6(b)。注意，图中语句标 号表示返回地址。
一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函 数是同一个函数，因此，和每次调用相关的一个重要概念是递归函数运行的''层 次假设调用该递归函数的主函数为第0层，那么从主函数调用递归函数为进入 第1层；一般地，从第i层递归调用本函数为进入''下一层〃，即第i+1层。反之， 从第i+1层递归退出返回至''上一层〃，即第i层。
5、汉诺塔问题的算法5、汉诺塔问题的算法
(1)问题的提出
19世纪，欧洲出现了一个称为''汉诺塔〃的游戏，该游戏表示(毫无疑问是伪 造的)Brahma寺庙地下通道中的一个任务。在世界产生初期，牧师得到一个镶 嵌着3根钻石针的黄铜平台。第一根针上堆积着64个金圆盘，每一个金圆盘比 它下面的金圆盘稍微小一些(在欧洲流行的特殊版本为具有8个纸圆盘和3个木 质柱子)。牧师被赋予一项任务，将所有的金圆盘从第一根针移动到第三根针, 遵从的规那么是：每一次只能移动一个金圆盘，移动过程中可以借助第二根针，金 圆盘不能放在比它小的金圆盘之上。牧师还被告知当完成这64个金圆盘的移动 之后，将昭示着世界末日的到来。
当然，我们的任务是编写一个计算机程序，为牧师列出一个移动金圆盘的指 令列表。这个任务可以使用如下指令：
Move(64,xzy,z)
指令而含义是：
将64个圆盘从塔x移动到塔z,可以使用塔y作为临时存储器。
(2)解决方案
有一个解决方案的思想是，不要将注意力集中在第一步(第一步肯定是将顶 层圆盘移动到某处)，应该主要集中在最困难的步骤上：移动底层圆盘。在上面 的63个圆盘被移走前，无法到达最底层的圆盘，所以必须将上面的63个圆盘 都移动到塔b上，这样才能将底层圆盘从塔a移动到塔c。这是因为每次只能移 动一个圆盘，底层圆盘(最大的圆盘)不能在其他任何圆盘之上，因此当移动底 层圆盘时，其他任何圆盘都不能在塔a或塔c上。这样可以将汉诺塔的算法步骤 归结为：
Move(63,a,c,b);
printf("Movedisk64fromtoweratotowerc.\n");
Move(63,b,a,c);
现在离解决方案又近了一小步，仅仅是非常小的一步，因为仍然必须描述如 何移动上面的63个圆盘。虽然如此，这仍然是重要的一步，因为可以采用同样 的方法移动剩下的63个圆盘(事实上，必须采用同样的方法移动，因为每一次 都有一个最大的圆盘必须最后移动)。
这正是递归的思想。上面已经描述了递归的原理和主要步骤，将64个圆盘 的问题转变成63个圆盘的问题，那么剩下的解决步骤在实质上和前面是相同的。 (3)算法
根据以上分析，设把n个盘子从塔x搬到塔z,用塔y作为过渡，那么编写出 递归算法如下：
1 voidMove(intn,charx,chary,charz){if(n==l)
2 printf(u%d.Movedisk%dfrom%cto%c\n,,,++i,nzx,z);
〃当只有一个盘子时，直接由塔x搬到塔z后结束一次函数调用
〃其中i是初值为0的全局变量，表示搬动的步骤数。
3 else{
5
6
7
8
9
(4)
Move(n-l,x,z,y);
pnntf(u%d.Movedisk%dfrom%cto%c\n,,,++i,nzx/z);
Move(n-l,y,x,z);算法3-14 Hanoi塔问题求解算法
系统运行追踪
下面我们来看Move（3,a,b,c）语句执行过程（从主函数进入递归函数到退出递 归函数而返回至主函数）中，递归工作栈状态的变化情况：
递 归 层 次语句行
号
递归工作栈状态（返址,
n、x、y、z值）
塔与圆盘的状态1,2,4,5
0,3,a,b,c124,5
1,2,3,96,2,a,c,b
03 abe6」,a,b,c
6,2,a,c,b0,3,a,b,c

6,71,2,3,9
8,96,2,a,c,b
0,3,a,bzc8,l,c,a,b
6,2,a,c,b0,3,a,b,c
6z2,a,c,b0z3,azb,c

6,70,3,a,b,c
8z2,b,a,c0,3,a,b,c
124,5123,9
6,l,b,c,a8,2,b,a,c
0,3,a,b,c

6,71,2,3,9
8,98,2,b,a,c
0,3,a,b,c8,l,a,b,c
8,2,b,a,c0,3,a,b,c
8,2,b,a,c同上

0,3,a,b,c18,90,3,a,b,c同上
0栈空图3.8汉诺塔的递归函数调用示意图
(5)算法分析
现在介绍另一个分析递归调用的工具，该工具与程序追踪相比，在管理调用 的多样性方面具有更高的效率。这个工具称为递归树。
下面为Move(3,a,b,c)语句执行过程的递归树：
现在，计算一下在程序运行过程中，将进行多少次递归。Move函数第一次 调用时，n=64,然后每次递归调用n的值减去1。那么，绘制程序的调用递归 树时，从叶结点向上共有64级。除了叶结点之外，每个结点导致两个递归调用， 因此每一级中的结点数是上一级的两倍。
通过递归树，能够相当容易的计算出移动64个圆盘所需的指令数目。树中 的每一个结点对应一条指令。结点数目总共为：
1+2+4+...+263=20+21+22+...+263=264-1这是64个圆盘需要的总移动次数。
我们可以近似的估测一下这个数到底有多大？
103=1000<1024=210
一年大约有3,2*1。7秒。假设牧师移动汉诺塔的速度能以每秒一次的高速度 执行。由于264=24*260>24*1018=1.6*1019
总的任务花费大约5*10"年。如果天文学家估计宇宙年龄大约为200亿 (2*10ii)年，那么根据这个故事，世界将存在很长的时间——是现在已经存在的 时间的2.5倍！
应当特别注意的是，尽管没有计算机能够实现整个汉诺塔，原因在于缺乏时 间而导致失败，但肯定不是因为缺乏存储空间。所需要的空间仅仅是追踪64个 递归调用使用的空间，但所需的时间是进行264-1次计算花费的时间。
第三节队列
栈是一种具有''先进先出〃特性的线性表。这种特性对其操作有何影响呢？其 存储结构相对于一般线性表又会有哪些变化？本节将从队列的定义、抽象类型定 义、队列的顺序与链式存储结构等方面入手解答上述问题。
工、队列的定义1、队列的定义
队列(Queue)简称队，也是一种特殊的线性表，可定义为只允许在表的一 端进行插入，而在表的另一端进行删除的线性结构。队列允许插入的一端称为队 尾(Rear),允许删除的一端称为队首(Front) o向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素;
从队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。
由于队列的插入和删除分别在不同的两端进行，因而先插入者自然先从另一 端删除，所以队列具有''先进先出〃的特点，简称为FIFO (First-In,First-Out) o
队列在日常生活中十分常见，如在银行或餐厅中排队就是一个队列。在计算 机应用中队列可用于许多编程的场合，例如用来作为模拟事件的排序表以及I/O 缓冲。
假设队列为q=(ai,d2,…,加)，那么称ai为队首元素，而为队尾元素。队列中的 元素是按照ai,32,…,an的次序进入的，退出队列也只能按照这个次序依次退出， 即只有在aiM,…,a.都离开队列之后,an才能退出队列,如图3.10所示。
2、队列的抽象类型定义2、队列的抽象类型定义
在队列的抽象数据类型中，用Queue标识符来表示队列对象类型，操作局部 应包括初始化、元素进队、元素出队、读取队首元素、检查队列是否为空等。下 面给出队列的抽象数据类型的具体定义。
ADTQueue{数据对象：D={ai|aiGEIemSet,i=l,2,...,n,n>0}
数据关系:Rl={<ai-i,ai>|ai-izaiGD,i=2,...,n)约定其中ai端为队首，an端为队尾。
基本操作：
InitQueue(&Q)操作结果：构造一个空队列Q。
QueueEmpty(Q)初始条件：队列Q已存在。
操作结果：假设Q为空队列，那么返回TRUE,否那么FALSE。
QueueLength(Q)初始条件：队列Q已存在。
操作结果：返回Q的元素个数，即队列的长度。
EnQueue(&Q,e)初始条件：队列Q已存在。
操作结果：插入元素e为Q的新的队尾元素。
DeQueue(&Q,&e)初始条件：Q为非空队列。
操作结果：删除Q的队首元素，并用e返回其值。
GetHead(Q,&e)初始条件：Q为非空队列。
操作结果：用e返回Q的队首元素。
QueueT raverse(Q,visit())初始条件：Q已存在且非空。
操作结果：从队首到队尾，依次对Q的每个数据元素调用函数visit。。一旦visit。失败, 那么操作失败。
ClearQueue(&Q)初始条件：队列Q已存在。
操作结果：将Q清为空队列。
DestroyQueue(&Q)初始条件：队列Q已存在。
操作结果：队列Q被销毁，不再存在。
}ADTQueue3、循环队列的数据类型描述
3、循环队列的数据类型描述
在队列的顺序存储结构中，和顺序栈相类似，用一组地址连续的存储单元依 次存放从队首到队尾的元素，同时附设两个指针front和rear分别指示队首元素 及队尾元素的位置。在本书中，我们约定：初始化建空队列时，令front=rear=0, 每当插入新的队尾元素时，将新元素插入到队尾指针指向的位置后，尾指针增1； 每当删除队首元素时，头指针增1。因此，在非空队列中，头指针始终指向队首 元素，而尾指针始终指向队尾元素的下一个位置，如图3.11所示。
假设当前为队列分配的最大空间为6,那么当队列处于图3.11 (d)的状态时 不能再继续插入新的队尾元素，否那么会因数组下标越界而破坏程序。但此时队列 的实际可用空间并未占满，如果同顺序栈那样，继续分配存储单元扩大数组空间 将会导致更大的浪费。为了解决这个问题，我们可以使顺序队列变成一个首尾相 接的环状的空间，指针和队列元素之间的关系不变，如图3.12所示，称之为循 环队列。
在图3.13 (a)所示的循环队列中，队首元素是33,队尾元素是35。假设元素 36、汨、38相继插入，那么队列空间被占满，如图3.13 (b)所示，此时存在关系 Q.front==Q.rear；相反地,假设元素市、14和为相继从图3.13 (a)的队列中删 除，那么队列为空，如图3.13 (c)所示，此时也存在关系Q.f「ont==Q.rea「。因 此，假设仅凭等式Q.front==Q,rear无法判断队列空间是''空〃还是''满〃。解决方案 有两个：一个方案是另外设置一个标志位以区别队列是''空〃还是''满〃；另一个方 案是少用一个存储单元，以''队列头指针在队列尾指针的下一位置上〃作为队列为 ''满〃的标志。本书在下面的算法中采用第二种方法进行各操作的处理。
循环队列所需要的具体数据类型描述如下：
#defineMAXQSIZE100〃最大队列长度typedef struct{
ElemType *base; 〃初始化的动态分配存储空间int front;〃头指针，假设队列不空，指向队首元素
int rear;〃尾指针，假设队列不空，指向队尾元素的下一个位置
}SqQueue;
4、循环队列的操作
4、循环队列的操作(循环队列的生成算法、循环队列元素个数的求解算法、循 环队列的入队算法、循环队列的出队算法、循环队列的遍历算法) 生成循环队列
循环队列的生成算法主要是为其准备所需要的存储空间(这可通过malloc 函数申请空间实现)，同时令front=rear=0,形成空队列。
StatusInitQueue(SqQueue&Q){ 〃构造一个空队列 QQ.base=(ElemType*)malloc(MAXQSIZE*sizeof(ElemType));
if (! Q. base)exit(OVE RFLO W);〃存储分配失败Q.front=Q.rear=0;
returnOK;
假设栈S=(al,a2,…,an),那么称al为栈底元素，an为栈顶元素。栈中元素按 al,a2,...,an的次序进栈，如图3.1所不。
2、栈的抽象类型定义2、栈的抽象类型定义
在栈的抽象数据类型定义中，用Stack标识符来表示栈对象类型，操作局部 应包括初始化、元素进栈、元素出栈、读取栈顶元素、检查栈是否为空等。下面 给出栈的抽象数据类型的具体定义。
ADTStack{数据对象:D={ai|aiGEIemSetzi=l,2,...,n,n>0}
数据关系：R={<ai.i,ai>|ai-i,aiED,i=2,...,n)约定an端为栈顶，di端为栈底。
基本操作：
InitStack(&S)操作结果：构造一个空栈S。
Push(&S,e)初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&S,&e)初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
GetTop(S,&e)初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
StackEmpty(S)初始条件：栈S已存在。
操作结果：假设S为空栈，贝U返回TRUE,否那么返回FALSE。
StackLength(S)初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
StackTraverse(S, visit())初始条件：栈S已存在且非空。
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit。。一旦visit。失败，那么 操作失败。
ClearStack(&S)初始条件：栈S已存在。
操作结果：将S清为空栈。
DestroyStack(&S)初始条件：栈S已存在。
操作结果：栈S被销毁。
}ADTStack 3、顺序栈的数据类型描述 3、顺序栈的数据类型描述栈的顺序存储结构，即顺序栈，和线性表的顺序存储结构类似，是利用一组 连续的存储单元依次存放自栈底到栈顶的数据元素，同时通过指针top指示栈顶
算法3-15循环队列的生成算法返回队列元素个数
在存储结构中，假设尾指针在后，头指针在前，那么直接通过Q.rear・Q.front返 回队列长度。但是由于循环队列的特点，可能出现尾指针在前，头指针在后的情 况,此时通过 MAXQSIZE・(Q.front・Q,rear)即 Q.rear-Q.front+MAXQSIZE 返回队 列长度。这两种情况可以统一利用表达式：
(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE 来表示。
intQueueLength(SqQueueQ){ 〃返回Q的元素个数，即队列的长度 return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;)
算法3-16循环队列元素个数的求解算法插入新的队尾元素
首先由条件等式判断循环队列是否为''满假设满那么返回出错信息。否那么插入 元素e,并使尾指针沿环指向下一位置。本算法时日复杂度为0(1)。_StatusEnQueue(SqQueue&Q,ElemTypee){ 〃插入元素 e 为 Q 的新的队尾元素 if((Q.rear+l)%MAXQSIZE==Q.front)returnERROR; 〃队列满
Q.base[Q.rear]=e;Q.rear=(Q,rear+l)%MAXQSIZE;
returnOK;)
算法3-17循环队列的入队算法删除队首元素并返回
首先由条件等式判断循环队列是否为''空〃，假设空那么返回出错信息。否那么用e 返回队首元素值，并使头指针沿环指向下一位置。本算法时间复杂度为0(1)。 StatusDeQueue(SqQueue&Q,ElemType&e){〃假设队列不空，那么删除Q的队首元素，用e返回其值，并返回0K；
〃否那么返回ERROR；if(Q.front==Q.rear)returnERROR;
e=Q.base[Q.front];Q.front=(Q.front+l)%MAXQSIZE;
returnOK;)
算法3-18循环队列的出队算法返回队首元素值
首先由条件等式判断循环队列是否为''空〃，假设空那么返回出错信息。否那么用e返回队首元素值。本算法时间复杂度为0(1)。
StatusGetHead(SqQueueQ,ElemType&e){〃假设队列非空，那么用e返回Q的队首元素值，并返回0K。
〃否那么返回ERROR；if(Q.front==Q.rear)returnERROR;
e=Q.base[Q.front];returnOK;
算法3-19循环队列队首元素的求解算法循环队列的遍历
本算法从队首元素开始，通过pos=(pos+l)%MAXQSIZE向队尾循环，对队 列元素使用visit函数，直到队尾循环结束。该算法的主要操作和影响算法效率 的步骤为循环遍历队列的元素，频数和队列长度相等，所以本算法的时间复杂度 为 0(n)。
StatusQueueTraverse(SqQueueQ,Status(*visit)(ElemType)){if(Q.front==Q,rear)returnERROR;
pos=Q.front;〃取得队首位置while(pos!=Q.rear){〃由队首向队尾进行循环
visit(Q.base[pos]);pos=(pos+l)%MAXQSIZE;
))
算法3-20循环队列的遍历算法5、链队列的数据类型描述
5、链队列的数据类型描述应用中有时用到队列的链接存储结构。我们把用链表表示的队列简称为链队
列，如图3.14所示。
下面只考虑单链存储结构，由于要经常操作队列的队首结点和队尾结点，需 要有两个指针分别指向队首和队尾，即头指针front和尾指针rear。为了操作方 便，给链队列添加了一个头结点，并令头指针指向头结点，头结点的指针域指向 队首结点。由此，链队列为空的判断条件为头指针和尾指针均指向头结点，如图 3.15 (a)所示。但是不需要判别队列是否为满。链队列的操作即为单链表的插 入和删除操作的特殊情况，只是还需修改尾指针或头指针，图3.15 (b)〜(d) 展示了这两种操作进行时指针的变化情况。
假定链队列中的结点类型为QNode,那么头和尾指针为QNode*指针类型。 假设把一个链队列的头指针和尾指针定义在一个结构体类型中，并假定该结构体类 型用标识符LinkQueue表示，那么链队列所需要的具体数据类型描述如下： typedefstructQNode{ElemType data; 〃值域
struct QNode *next; 〃链接指针域}QNode,*QueuePtr;
typedefstruct{QueuePtr front;〃头指针
QueuePtr rear;〃尾指针}LinkQueue;
6、链队列的操作 6、链队列的操作(链队列的生成算法、链队列元素个数的求解算法、链队列的入队算法、链队列的出队算法、链队列的遍历算法) 生成链队列
链队列的生成算法主要是为其头结点准备所需要的存储空间(这可通过 malloc函数申请空间实现)，同时令头指针和尾指针均指向头结点。
StatusInitQueue(LinkQueue&Q) {
〃构造一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);〃存储分配失败Q.front- > next=NULL;
returnOK;)
算法3-21链队列的生成算法插入新的队尾元素
当元素e入队时，首先创造链队列元素结点，并使原来的队尾元素结点的指 针指向该元素结点，同时使尾指针也指向该元素结点，使该元素成为新的队尾元 素。本算法的时间复杂度为0(1)。
StatusEnQueue(LinkQueue&Q,ElemTypee) {〃插入元素e为队列Q的新的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);〃存储分配失败
p->data=e;p->next=NULL;
Q.rear->next=p;Q.rear=p;
returnOK;)
算法3-22链队列的入队算法删除队首元素并返回
当删除链队列的队首元素时，首先检查队列是否为空，如果为空，那么返回错 误。假设队列不为空，取出队首元素，使头结点的指针指向原队首元素结点的指针 域所指向的结点，然后释放该结点空间。本算法的时间复杂度为0(1)。
StatusDeQueue(LinkQueue&Q,ElemType&e) {
〃假设队列不空，那么删除队列的队首元素，用e返回其值，并返回0K,否那么返回 ERROR
if(Q.front==Q.rear)returnERROR;
p=Q.front->next;
e=p->data;
Q.front- > next=p-> next;if(Q.rear==p)Q.rear=Q.front;
free(p);returnOK;
)算法3-23链队列的出队算法
返回队首元素的值
首先检查链队列是否为空，如果为空，那么返回错误。假设队列不为空，那么直接 使用e返回队首元素的数据即可。本算法的时间复杂度为0(1)。
StatusGetHead(LinkQueueQzElemType&e) {
〃假设队列不空，那么用e返回队首元素的值，并返回0K,否贝I」返回ERROR if(Q.front==Q.rear)returnERROR;
p=Q.front->next; e=p->data;
returnOK;算法3-24链队列队首元素的求解算法
链队列的遍历
本算法从队首元素开始，通过队列元素的指针域向队尾循环，对队列元素使 用visit函数，直到对队尾使用visit函数循环结束。该算法的主要操作和影响算 法效率的步骤为循环遍历队列的元素，频数和队列的元素个数相同，所以本算法 的时间复杂度为0(n)。
StatusQueueTraverse(LinkQueueQ,Status(*visit)(ElemType)){if(Q.front==Q,rear)returnERROR;
p=Q.front->next〃取得队首元素结点的位置while(p){〃由队首向队尾进行循环
visit(p->data);p=p->next;
))
算法3-25链队列的遍历算法第四节队列的应用举例
计算机解决具有先进先出特性问题时，队列为首选数据结构。本节以舞伴问 题为例来说明队列的应用。
舞伴问题求解算法
假设在周末舞会上，男士和女士进入舞厅时，各自排成一队。跳舞开始时， 依次从男队和女队的队首各自出一人配成舞伴。假设两队初始人数不相同，那么较长 的那一队中未配对者等待下一轮舞曲。先入队的男士或女士先出队配成舞伴，因 此该问题具有典型的先进先出(FIFO)特性，可用队列作为算法的数据结构。
在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫 描该数组的各元素，并根据性别标识来决定是进入男队还是女队。当这两个队列 构造完成之后，依次将两队当前的队首元素出队来配成舞伴，直至其中某一队列 变空为止。此时，假设另一队仍有等待配对者，算法输出此队列中等待者的人数及 排在队首的等待者的名字，他或她将是下一轮舞曲开始时第一个可获得舞伴的人。
typedefstruct{charname[20];
charsex;〃性别，F表示女性，表示男性}Person;
typedefPersonElemType;〃队列中元素的数据类型ElemType定义为Person
voidDancePartner(Persondancer[],intnum){〃结构数组dancer中存放跳舞的男女，num是跳舞的人数。
InitQueue(Mdancers);〃男士队列初始化InitQueue(Fdancers);〃女士队列初始化
for(i=0;i<NUM;span<i++){>依次将跳舞者依其性别入
p=dancer[i];if(p.sex==,F,)
EnQueue(Fdancerszp);〃排入女队else
EnQueue(Mdancerszp); 〃排入男队)
prlntf("舞队是:\n\n“)；while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers)){
〃女士出队
〃打印出队女士名
〃男士出队
〃打印出队男士名
〃输出女士剩余人数及队首女士的
〃依次输入男女舞伴名 DeQueue(Fdancers,p); p「intf(“％s”,p.name); DeQueue(Mdancers,p); printf(H%s\nn,p.name);
) if(!QueueEmpty(Fdancers)){ 名字
p「intf(“\n还有％d个女士等下一轮.\n”,QueueLength(Fdancers));
GetHead(Fdancers,p);〃取队首printf(”％sw 川 bethefirsttogetapartner.\n”,p・name);
)elseif(!QueueEmpty(Mdancers)){〃输出男队剩余人数及队首者名
字printf(M\n还有％d个男士等下一
轮.\n”,QueueLength(Mdancers));GetHead(Mdancers,p);
p「intf(”%sw 川 bethefirsttogetapa「tne「.\rT,p.name);
) )算法3-26舞伴问题求解算法
元素在顺序栈中的位置。由于很难估计栈在使用过程中所需要的最大空间的大小, 所以通常利用C语言中动态分配的一组连续的存储单元作为顺序栈所需要的存 储空间。首先定义一个指针表示存储空间的基地址，且定义一个指针指示栈顶元 素的位置，此外还需要定义一个整型变量指示顺序栈当前分配的存储空间大小， 即当前顺序栈的最大容量。在应用过程中，当栈的空间不够用而需要继续扩大分 配其空间时，通过定义一个整型变量表示栈的动态分配增量。顺序栈所需要的具 体数据类型描述如下：
#defineMAXLEN
100
#defineSTACK INCREASE 10

#defineSTACK INCREASE 10
〃顺序栈存储空间的动态分配增量

typedefstruct{ ElemType *base; ElemType *top; int maxsize;
〃栈的存储空间的基地址，即栈底指针
〃栈顶指针〃栈当前分配的存储容量
}SqStack;
其中，maxsize指示栈当前可使用的最大容量；base为栈底指针，在顺序栈 中，它始终指向栈底的位置，假设base=NULL,那么说明栈结构不存在；top为栈顶 指针，起初值为栈底指针值，即top=base,这也可作为栈空的标记。栈插入新 元素时，将新元素插入到栈顶指针所指向的位置，同时指针top增1,删除栈顶 元素时，指针top减1。因此，如图3.2所示，栈顶指针始终指向栈顶元素的下 一个位置。
4、顺序栈的操作4、顺序栈的操作(顺序栈的生成算法、顺序栈的入栈算法、顺序栈的出栈算法、
顺序栈求栈顶元素算法、顺序栈的遍历算法) 生成栈S
顺序