第3章堆栈和队列

1、第第3章章 堆栈和队列堆栈和队列 3.1 堆栈堆栈 3.2 堆栈的应用举例堆栈的应用举例3.3 队列队列 3.4 队列的应用举例队列的应用举例 3.1 堆栈堆栈3.1.1 堆栈的基本概念堆栈的基本概念 3.1.2 顺序栈及其操作顺序栈及其操作 3.1.3 链栈及其操作链栈及其操作3.1.1 堆栈的基本概念堆栈的基本概念1. 堆栈的定义堆栈的定义 2. 堆栈与线性表的区别与联系堆栈与线性表的区别与联系3. 堆栈的特征堆栈的特征 4. 堆栈的抽象数据类型堆栈的抽象数据类型 1. 堆栈的定义堆栈的定义堆栈堆栈（stack）是一种特殊的线性）是一种特殊的线性表，这种表只能在固定的一端进行插表，这种表只

2、能在固定的一端进行插入与删除操作。入与删除操作。通常称固定插入与删除的一端为通常称固定插入与删除的一端为栈 顶栈 顶 ( t o p ) ， 而 另 一 端 称 为， 而 另 一 端 称 为 栈 底栈 底(bottom)，位于栈顶和栈底的元素分，位于栈顶和栈底的元素分别称为顶元和底元，当表中无元素时，别称为顶元和底元，当表中无元素时，称为称为空栈空栈。2. 堆栈与线性表的区别与联系堆栈与线性表的区别与联系 栈是特殊的线性表。栈是特殊的线性表。 栈的插入与删除运算只能在栈的插入与删除运算只能在栈栈顶顶进行，而线性表的插入和删除运算进行，而线性表的插入和删除运算可在线性表中的可在线性表中的任意位置

3、任意位置进行。进行。3. 堆栈的特征堆栈的特征 根据堆栈的定义，每次进栈的数根据堆栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素。这样，最元素都是原当前栈顶元素。这样，最后入栈的数据元素总是最先退出堆栈，后入栈的数据元素总是最先退出堆栈，因此，堆栈也称为因此，堆栈也称为后进先出表后进先出表(LIFO) ，见见图图3.1。堆栈的操作过程演示堆栈的操作过程演示 图图3.1图图3.1 3.1 堆栈的操作示意图堆栈的操作示意图 4. 堆栈的抽象数据类型堆栈的抽象数据类型ADT

4、Stack Data： 堆栈中的数据元素具有相同类型及先进后出特性，相邻元素具堆栈中的数据元素具有相同类型及先进后出特性，相邻元素具有前驱和后继的关系。有前驱和后继的关系。 Operation： InitStack(&S, maxsize, incresize) 操作结果：构造一个容量为操作结果：构造一个容量为maxsize的空栈的空栈S。 ClearStack(&S) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：将栈操作结果：将栈S清为空栈。清为空栈。 StackLength(S) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：返回操作结果：返回S的元素个数

5、，即栈的长度。的元素个数，即栈的长度。 Push(&S，e) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：插入元素操作结果：插入元素e为新的栈顶元素。为新的栈顶元素。 Pop(&S，&e) 初始条件：栈初始条件：栈S已存在且非空。已存在且非空。 操作结果：删除操作结果：删除S的栈顶元素并用的栈顶元素并用e返回其值。返回其值。 GetTop(S，&e) 初始条件：栈初始条件：栈S已存在且非空。已存在且非空。 操作结果：用操作结果：用e返回返回S的栈顶元素。的栈顶元素。 StackTraverse(S) 初始条件：栈初始条件：栈S已存在且非空。已存在且非空

6、。 操作结果：从栈底到栈顶依次输出操作结果：从栈底到栈顶依次输出S中的各个数据元素。中的各个数据元素。 StackEmpty(S) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：若栈操作结果：若栈S为空栈，则返回为空栈，则返回true；否则返回；否则返回false。 DestroyStack(&S) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：栈操作结果：栈S被撤销。被撤销。ADT Stack3.1.2 顺序栈及其操作顺序栈及其操作1. 顺序栈的定义顺序栈的定义2. 上溢与下溢上溢与下溢3. 判空与判满判空与判满 4. 顺序栈的结构描述顺序栈的结构描述5. 顺序栈的基

7、本操作顺序栈的基本操作6. 多栈共享邻接空间多栈共享邻接空间1. 顺序栈的定义顺序栈的定义：即栈的顺序存储结构，它是利用一组地址：即栈的顺序存储结构，它是利用一组地址连续的存储单元依次存放自栈底到栈顶之间的数据元素，连续的存储单元依次存放自栈底到栈顶之间的数据元素，同时附设指针同时附设指针top指标栈顶元素在顺序栈中的位置。如指标栈顶元素在顺序栈中的位置。如图图3.2所示。所示。注意：注意：由于顺序栈都是在栈顶的位置上进行相关操作，因由于顺序栈都是在栈顶的位置上进行相关操作，因而栈顶指针而栈顶指针top的当前位置是非常重要的。在对顺序栈进的当前位置是非常重要的。在对顺序栈进行初始化时，行初始化

8、时，top的初值决定了堆栈的状态及对其操作的的初值决定了堆栈的状态及对其操作的语句顺序，一般语句顺序，一般top的初值可以置的初值可以置0或或-1，图，图3.2中中top的初的初值为值为-1（堆栈中有一个元素）。（堆栈中有一个元素）。图图3.2图图3.2 3.2 顺序栈存储示意图顺序栈存储示意图 2. 上溢与下溢上溢与下溢设存储栈元素的数组长度为设存储栈元素的数组长度为stacksize ，top的初值为的初值为-1，则：，则： 当当top= stacksize-1 时，表示系统作为栈时，表示系统作为栈用的存储空间已满，如用的存储空间已满，如图图3.3(b)。如果还有元素。如果还有元素要求进栈

9、，则栈要溢出，即要求进栈，则栈要溢出，即上溢上溢，这时需要进行，这时需要进行栈满处理。栈满处理。当当top=-1时，表示系统作为栈用的存贮区时，表示系统作为栈用的存贮区已空，栈中无任何元素，如已空，栈中无任何元素，如图图3.3(a)。这时若还。这时若还要做出栈运算，则发生要做出栈运算，则发生下溢下溢。通常用栈空来作为。通常用栈空来作为控制转移的条件，表明数据已处理完毕。控制转移的条件，表明数据已处理完毕。图图3.3图图3.3 3.3 栈空和栈满的存储示意图栈空和栈满的存储示意图 3. 判空与判满判空与判满一般来说，在对顺序栈进行插入元素一般来说，在对顺序栈进行插入元素之前，要判断栈是否之前，要

10、判断栈是否“栈满栈满”，而对顺序，而对顺序栈进行删除元素之前要判栈是否栈进行删除元素之前要判栈是否“栈空栈空”。栈满栈满： top= stacksize-1 栈空栈空： top=-14. 顺序栈的结构描述顺序栈的结构描述# define STACK_INIT_SIZE 100 # define STACKINCREMENT 10 typedef struct ElemType *stack; int top; int stacksize; int incrementsize; SqStack; 说明：说明： 由于堆栈在使用过程中所需最大空间的大小很难估计，因此，由于堆栈在使用过程中所需最大空间

11、的大小很难估计，因此，一 般 来 说 ， 在 初 始 化 先 为 栈 分 配 一 个 基 本 容 量一 般 来 说 ， 在 初 始 化 先 为 栈 分 配 一 个 基 本 容 量 ( 默 认 的 为默 认 的 为STACK_INIT_SIZE )，然后在应用过程中，当堆栈的空间不够使用，然后在应用过程中，当堆栈的空间不够使用时再逐步扩大（默认的为时再逐步扩大（默认的为STACKINCREMENT）。5. 顺序栈的基本操作顺序栈的基本操作初始化初始化 求栈的长度求栈的长度进栈进栈 出栈出栈 取栈顶元素取栈顶元素 判栈空否判栈空否撤销顺序栈撤销顺序栈总结总结初始化初始化void InitStack

12、_Sq(SqStack &S, int maxsize=STACK_INIT_SIZE, int incresize=STACKINCREMENT) S.stack=(ElemType *)malloc(maxsize*sizeof(ElemType); if(!S.stack) exit(1); S.top=-1; S.stacksize=maxsize; S.incrementsize=incresize; / InitStack_Sq 求栈的长度求栈的长度int StackLength_Sq(SqStack S)return S.top+1;/ StackLength_Sq进栈进

13、栈bool Push_Sq(SqStack &S,ElemType e) if(S.top=S.stacksize-1) S.stack =(ElemType *)realloc(S.stack,(S.stacksize+ S.incrementsize)*sizeof(ElemType); if(!S.stack) return false; S.stacksize+=S.incrementsize; S.stack+S.top=e; return true; / Push_Sq出栈出栈bool Pop_Sq(SqStack &S,ElemType &e) if(S.

14、top=-1) return false; e=S.stackS.top-; return true; / Pop_Sq取栈顶元素取栈顶元素bool GetTop_Sq(SqStack S, ElemType &e) if(S.top=-1) return false; e=S.stackS.top; return true; / GetTop_Sq判栈空否判栈空否 bool StackEmpty_Sq(SqStack S) if(S.top=-1) return true; else return false;/ StackEmpty_Sq 撤销顺序栈撤销顺序栈void Destro

15、yStack_Sq(SqStack &S ) free(S.stack); S.stacksize=0; S.top=-1;/ DestroyStack_Sq总结总结对于顺序栈对于顺序栈S的相关操作，归纳起的相关操作，归纳起来主要有以下来主要有以下4个要素：个要素：栈空条件：栈空条件：S.top=-1栈满条件：栈满条件：S.top=S.stacksize-1进栈操作：进栈操作：S.top+；元素进栈；元素进栈出栈操作：元素退栈，出栈操作：元素退栈，S.top-6. 多栈共享邻接空间多栈共享邻接空间两个栈共享邻接空间两个栈共享邻接空间多栈共享邻接空间多栈共享邻接空间两个栈共享邻接空间两个

16、栈共享邻接空间共享原理共享原理两栈共享空间的判空与判满两栈共享空间的判空与判满两栈共享空间的结构描述两栈共享空间的结构描述两个共享空间的基本操作两个共享空间的基本操作共享原理共享原理 两个栈共享空间是利用堆栈两个栈共享空间是利用堆栈“栈栈底位置不变栈顶位置动态变化底位置不变栈顶位置动态变化”的特的特性。假设一个程序中需设两个栈，令性。假设一个程序中需设两个栈，令其共享一维数组空间其共享一维数组空间stackStackSize， 则两个栈底可分别为则两个栈底可分别为-l和和StackSize (见见图图3.4)。 由于两个栈顶均为动态变化，可由于两个栈顶均为动态变化，可互补余缺，因此使得每个栈的

17、最空间互补余缺，因此使得每个栈的最空间均大于均大于StackSize /2。 图图3.4图图3.4 3.4 两个栈共享空间示意图两个栈共享空间示意图 两栈共享空间的判空与判满两栈共享空间的判空与判满栈空：栈空：top10 左栈空左栈空top2= StackSize 右栈空右栈空栈满：栈满：当当top1+1 =top2两栈共享空间的结构描述两栈共享空间的结构描述# define StackSize 100 typedef struct ElemType stackStackSize; int top1,top2; SqStack_Du;两个共享空间的基本操作两个共享空间的基本操作v初始化初始化v

18、进栈进栈v出栈出栈初始化初始化void InitStack_DuSq(SqStack_Du &S) S.top1=-1; S.top2=StackSize;/ InitStack_DuSq进栈进栈bool Push_DuSq(SqStack_Du &S,char WhichStack, ElemType e) if(S.top1=S.top2-1) cout栈已满栈已满!endl; return false; if(WhichStack!=L& WhichStack!=R) cout参数错误参数错误!endl; return false; if(WhichStack=L

19、) S.stack+S.top1=e; else S.stack-S.top2=e; return true; / Push_DuSq出栈出栈bool Pop_DuSq(SqStack_Du &S,char WhichStack,ElemType &e) if(WhichStack!=L&WhichStack!=R) cout参数错误参数错误!endl; return false; if(WhichStack=L) if(S.top10) cout左栈已空左栈已空!=StackSize) cout右栈已空右栈已空!next; return k;/ StackLength

20、_L进栈进栈bool Push_L( LinkStack &S, ElemType e) LinkStack p; if(p=(LNode *)malloc(sizeof(LNode)=NULL) return false; p-data=e; p-next=S; S=p; return true;/ Push_L图图3.6图图3.6图图3.6 3.6 链栈的入栈操作示意图链栈的入栈操作示意图 出栈出栈bool Pop_L( LinkStack &S, ElemType &e) LinkStack p; if(S) p=S;S=S-next; e=p-data; fre

21、e(p); return true; else return false; / Pop_L图图3.73.7图图3.7图图3.7 3.7 链栈的出栈操作示意图链栈的出栈操作示意图 取栈顶元素取栈顶元素bool GetTop_L(LinkStack S,ElemType &e) if(S) e=S-data; return true; else return false; / GetTop_L判栈空否判栈空否bool StackEmpty_L(LinkStack S) if(!S) return true; else return false;/ StackEmpty_L撤销链栈撤销链栈v

22、oid DestroyStack_L(LinkStack &S ) LinkStack p,p1; p=S; while(p) p1=p; p=p-next; free(p1); S=NULL; / DestroyStack_L 总结总结对于链栈对于链栈S S的相关操作，归纳起的相关操作，归纳起来主要有以下来主要有以下3 3个要素：个要素：栈空条件：栈空条件：S=NULLS=NULL进栈操作：创建新结点进栈操作：创建新结点p p，插，插入新结点：入新结点：p-next=S; S=p;p-next=S; S=p;出栈操作：修改栈顶指针，释出栈操作：修改栈顶指针，释放栈顶结点空间：放栈顶结

23、点空间：p=S;S=S-next;p=S;S=S-next;3.2 堆栈的应用举例堆栈的应用举例例例3.1 数制转换问题数制转换问题例例3.2 表达式求值表达式求值例例3.3 背包问题背包问题例例3.1 数制转换问题数制转换问题 十进制数十进制数N和其他和其他d进制数的转换是计算机实现计算的基本问进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理题，其解决方法很多，其中一个简单算法基于下列原理: N=(N div d)d+N mod d 例如例如:(1348)10 =(2504)8，其运算过程如下，其运算过程如下: N N div 8 N mod 8 1348

24、 168 4 168 21 0 21 2 5 2 0 2 由于上述计算过程是从低位到高位顺序产生由于上述计算过程是从低位到高位顺序产生d进制数的各个数进制数的各个数位，而打印输出时，一般来说应从高位到低位进行，恰好和计算过位，而打印输出时，一般来说应从高位到低位进行，恰好和计算过程相反，所以此问题适合利用堆栈来解决程相反，所以此问题适合利用堆栈来解决 。具体实现如具体实现如算法算法3.18所所示。示。 算法算法3.18void TransFrom(long N,int d ) LinkStack S; int x; InitStack_L(S); while(N) Push_L(S,N % d

25、); N=N/d; while(!StackEmpty_L(S) Pop_L(S,x); coutx; cout-*/(#=算法思想算法思想 设置一运算符栈，栈顶预置为“#” x1：栈顶运算符，x2：当前扫描到的运算符（输入运算符） 算法结束且退栈且与继续比较退栈并输出读下一个单词进栈赋值给运算符读下一个单词输出操作数操作数当前单词, #2#11,)2(1121211:122:122:xxxxxxxxx，xxxx，xxxx，操作示例操作示例步骤步骤 中缀表达式中缀表达式 STACKSTACK 输出输出 步骤步骤 中缀表达式中缀表达式 STACKSTACK 输出输出 1 1 A+A+（B B-

26、-C/DC/D）*E*E # # 9 9 )*E#)*E# #+(#+(- -/ / ABCDABCD 2 2 + +（B B- -C/DC/D）*E*E # # A A 1010 *E#*E# #+(#+(- - ABCD/ABCD/ 3 3 （B B- -C/DC/D）*E*E #+#+ A A 1111 *E#*E# #+(#+( ABCD/ABCD/- - 4 4 B B- -C/DC/D）*E*E #+(#+( A A 1212 *E#*E# #+#+ ABCD/ABCD/- - 5 5 - -C/DC/D）*E*E #+(#+( ABAB 1313 E#E# #+*#+* ABCD

27、/ABCD/- - 6 6 C/DC/D）*E*E #+(#+(- - ABAB 1414 # # #+*#+* ABCD/ABCD/- -E E 7 7 /D/D）*E*E #+(#+(- - ABCABC 1515 # # #=#= ABCD/ABCD/- -E*E* 8 8 D D）*E*E #+(#+(- -/ / ABCABC 1616 # # # # ABCD/ABCD/- -E*+E*+ 算法描述算法描述bool Postfix(char *Mid_Expression,char *Post_Expression) SqStack S; char x1,x2,x,y; int i

28、=0,j=0; InitStack_Sq(S); Push_Sq(S,#); x2=Mid_Expressionj; if(!GetTop_Sq(S,x1) exit(0); while(1) if(x2!=+&x2!=-&x2!=*&x2!=/&x2!=(&x2!=)&x2!=#) Post_Expressioni+=x2; x2=Mid_Expression+j; else if(Proceed(x1,x2)=) if(!Pop_Sq(S,x) exit(0); Post_Expressioni+=x; if(!GetTop_Sq(S,x1)

29、 exit(0); else if(Proceed(x1,x2)=&x1=(&x2=) if(!Pop_Sq(S,y) exit(0); if(!GetTop_Sq(S,x1) exit(0); x2=Mid_Expression+j; else if(Proceed(x1,x2)=&x1=#&x2=#) Post_Expressioni=0; return true; else if(Proceed(x1,x2)= ) break; cout错误错误endl; return false;/ Postfix比较比较x1和和x2的优先级的优先级char Proce

30、ed(char x1,char x2) char Result; char MidString2; Result=; else if(x1=(&x2=)|(x1=#&x2=#) Result=; else if(x1=(&x2=#)|(x1=)&x2=()|(x1=#&x2=) Result= ; return Result;/ Proceed 后缀表达式的求解后缀表达式的求解算法思想算法思想：设置一个堆栈，从前到后依次扫描后设置一个堆栈，从前到后依次扫描后缀表达式，每读到一个操作数就将其压入缀表达式，每读到一个操作数就将其压入堆栈；每读到一个运算符，就

31、从栈顶取出堆栈；每读到一个运算符，就从栈顶取出两个操作数施以该运算符所代表的操作，两个操作数施以该运算符所代表的操作，并把计算结果作为一个新的操作数压入堆并把计算结果作为一个新的操作数压入堆栈（即栈（即图图3.8中的中的Ti入栈），一直到后缀表入栈），一直到后缀表达式读完。达式读完。 图图3.8图图3.8 3.8 后缀表达式的求值过程后缀表达式的求值过程 例例3.3 背包问题背包问题1.1.问题描述问题描述2.2.算法思想算法思想3.3.算法描述算法描述1. 问题描述问题描述假设有一个能装入总体积为假设有一个能装入总体积为T的背包和的背包和n件件体积分别为体积分别为w1，w2，wn的物品，能否

32、从的物品，能否从n件件物品中挑选若干件恰好装满背包，即使物品中挑选若干件恰好装满背包，即使w1+w2+wn=T，求找出所有满足上述条件的，求找出所有满足上述条件的解。例如：当解。例如：当T=l0，各件体积为（，各件体积为（1，8，4，3，5，2）时，可找到下列）时，可找到下列4组解：（组解：（1，4，3，2）、）、（1，4，5）、（）、（8，2）和（）和（3，5，2）。）。 2. 算法思想算法思想对物品进行顺序编号：对物品进行顺序编号：0,1,0,1, ,n-1 ,n-1，堆，堆栈初始化；栈初始化；从从0 0号物品起顺序选取，若可以装入背包，号物品起顺序选取，若可以装入背包，则将该物品号则将该

33、物品号“入栈入栈”；若恰好装满背包（找到一组解）或尚未求若恰好装满背包（找到一组解）或尚未求得解时已无物品可选，则从栈顶退出最近装入的得解时已无物品可选，则从栈顶退出最近装入的物品号（假设为物品号（假设为k k），之后继续从第），之后继续从第k+1k+1件物品起件物品起挑选。挑选。若栈非空或者还有物品可选，重复若栈非空或者还有物品可选，重复和和。3. 算法描述算法描述void knapsack( int w, int T, int n ) SqStack S; int k; InitStack_Sq(S); k=0; do while (T0 & k=0 ) Push_Sq(S,k);

34、 T-=wk; k+; if(T=0) Print(S,w,6); / 输出一组解输出一组解 Pop_Sq(S,k ); T+= wk; k+; while (!StackEmpty_Sq(S)|k!=n );/ knapsack输出一组解输出一组解void Print(SqStack S,int w,int n) int k=S.top; while(k=0) coutwS.stackk- ; cout=maxsize队空队空：rear=front图图3.10图图3.10 3.10 队列的操作示意图队列的操作示意图4. 假溢出假溢出 ：当队尾指针当队尾指针rear=maxsize时，时，而队

35、首指针而队首指针front0，即这时，即这时rear已指向数已指向数组的最后一个元素的下一个位置，而组的最后一个元素的下一个位置，而front前面还有空闲的空间，前面还有空闲的空间，但按前面的判满算但按前面的判满算法不能做进队操作，这现象叫假溢出，如法不能做进队操作，这现象叫假溢出，如图图3.12所示。所示。 解决解决假溢出的方法主要有：假溢出的方法主要有：修改出队修改出队列算法列算法、修改进队列算法修改进队列算法和和顺序循环队列顺序循环队列。图图3.12图图3.12 3.12 顺序队列的假溢出顺序队列的假溢出修改出队列算法修改出队列算法 使每次出队列后都把队列中的使每次出队列后都把队列中的剩

36、剩余数据元素向队头方向移动一个位置余数据元素向队头方向移动一个位置。 在这种出队算法的前提下，队列在这种出队算法的前提下，队列中可以不要队首指示器，因队首指示中可以不要队首指示器，因队首指示器固定指在队列的最前端。此算法时器固定指在队列的最前端。此算法时间复杂度为间复杂度为O(n) 。修改进队列算法修改进队列算法 当为真溢出时返回当为真溢出时返回false；当为假；当为假溢出时，则把顺序队列中的所有数据溢出时，则把顺序队列中的所有数据元素向队头方向移动元素向队头方向移动front个位置，使个位置，使队首元素位于队列的最前端后再完成队首元素位于队列的最前端后再完成新数据元素的入队列操作；此算法的

37、新数据元素的入队列操作；此算法的时间复杂度亦为时间复杂度亦为O(n)。5. 顺序循环队列顺序循环队列顺序循环队列的定义顺序循环队列的定义判空和判满判空和判满顺序循环队列的结构描述顺序循环队列的结构描述顺序循环队列的基本操作顺序循环队列的基本操作顺序循环队列的定义顺序循环队列的定义 方法是把顺序队列构造成一方法是把顺序队列构造成一个头尾相连的循环表，即允许队列直接从个头尾相连的循环表，即允许队列直接从数组中下标最大的位置延续到下标最小的数组中下标最大的位置延续到下标最小的位置，位置，使用取模操作可以很容易地实现它。使用取模操作可以很容易地实现它。在这种方法中，当队列的第在这种方法中，当队列的第m

38、axsize-1个位个位置被占用后，只要队列的前端还有可用的置被占用后，只要队列的前端还有可用的空间，则新的数据元素加入队列的下标为空间，则新的数据元素加入队列的下标为0的位置的位置，见，见图图3.13。 图图3.13图图3.13 3.13 顺序循环队列一般示意图顺序循环队列一般示意图 判空和判满判空和判满 顺序循环队列非常好地解决了假溢出，顺序循环队列非常好地解决了假溢出，但但在顺序循环队列中当条件：在顺序循环队列中当条件：rear=front成立时，队列可能为空，也可能为满，即成立时，队列可能为空，也可能为满，即满队列和空队列无法区分，见满队列和空队列无法区分，见图图3.14。解。解决方法

39、主要有以下几种：决方法主要有以下几种： 少用一个存储单元少用一个存储单元 设置一个标志位设置一个标志位 设置一个计数器设置一个计数器图图3.14图图3.14 3.14 顺序循环队列指针的三种情况顺序循环队列指针的三种情况少用一个存储单元少用一个存储单元 进队操作时，队尾指针进队操作时，队尾指针“依环状依环状增增1”，如果此时队尾指针等于队首指，如果此时队尾指针等于队首指针，则说明队列中无可利用空间，即针，则说明队列中无可利用空间，即此时队满。如果在没有执行进队和出此时队满。如果在没有执行进队和出队操作的前提下，队首指针和队尾指队操作的前提下，队首指针和队尾指针指向同一位置，则表明队列为空针指向

40、同一位置，则表明队列为空（图图3.15)。队满队满： (rear+1)% maxsize=front队空队空：rear=fron图图3.15图图3.15 3.15 顺序循环队列的判空与判满顺序循环队列的判空与判满设置一个标志位设置一个标志位 设置一个标志位设置一个标志位tag，并置初值为，并置初值为0，每当进队操作成功时就置，每当进队操作成功时就置tag=1;每每当出队操作成功时就置当出队操作成功时就置tag=0 ，则：，则： 队满：队满： tag=1且且rear=front 队空：队空： tag=0且且rear=front 设置一个计数器设置一个计数器 设置一个计数器设置一个计数器count

41、，并置初始，并置初始为为0，每当进队操作成功时就置每当进队操作成功时就置count=1;每当出队操作成功时就置每当出队操作成功时就置count=0 ，则：，则： 队满：队满：count0且且rear=front 队空：队空：count=0顺序循环队列的结构描述顺序循环队列的结构描述# define QUEUE_INIT_SIZE 100 # define QUEUEINCREMENT 10 typedef struct ElemType *queue; int front; int rear; int queuesize; int incrementsize; SqQueue;顺序循环队列的基

42、本操作顺序循环队列的基本操作初始化初始化求队列的长度求队列的长度进队进队出队出队取队首元素取队首元素判队空否判队空否撤销顺序循环队列撤销顺序循环队列总结总结初始化初始化void InitQueue_Sq(SqQueue &Q, int maxsize=QUEUE_INIT_SIZE, int incresize=QUEUEINCREMENT) Q.queue=(ElemType *)malloc(maxsize*sizeof(ElemType); if(!Q.queue) exit(1); Q.front=Q.rear=0; Q.queuesize=maxsize; Q.increme

43、ntsize=incresize; / InitQueue_Sq求队列的长度求队列的长度int QueueLength_Sq(SqQueue Q) return (Q.rear-Q.front+Q.queuesize) % Q.queuesize;/ QueueLength_Sq 进队进队bool EnQueue_Sq(SqQueue &Q,ElemType e) if(Q.rear+1)%Q.queuesize=Q.front) Q.queue=(ElemType *)realloc(Q.queue, (Q.queuesize+Q.incrementsize)*sizeof(Elem

44、Type); if(!Q.queue) return false; if(Q.frontQ.rear) for(int i=Q.queuesize;i=Q.front;i-) Q.queuei+Q.incrementsize=Q.queuei; Q.front+=Q.incrementsize; Q.queuesize+=Q.incrementsize; Q.queueQ.rear=e; Q.rear=(Q.rear+1) %Q.queuesize; return true;/ EnQueue_Sq说明说明： “ 扩 容扩 容 ” 操 作 是 在 原 队 列 的 最 大 下 标 之 后 增 加

45、操 作 是 在 原 队 列 的 最 大 下 标 之 后 增 加Q.incrementsizeQ.incrementsize个数据元素的空间，这时，若队首指针在队尾指个数据元素的空间，这时，若队首指针在队尾指针的后面，则需要移动部分元素，重新确定队首指针的位置。具体针的后面，则需要移动部分元素，重新确定队首指针的位置。具体操 作 是 将 队 首 指 针 至 最 大 下 标 之 间 的 所 有 元 素 后 移操 作 是 将 队 首 指 针 至 最 大 下 标 之 间 的 所 有 元 素 后 移Q.incrementsizeQ.incrementsize个数据元素的位置，同时队首指针也后移个数据元素

46、的位置，同时队首指针也后移Q.incrementsizeQ.incrementsize个位置；若队首指针在队尾指针的前面，则不需个位置；若队首指针在队尾指针的前面，则不需要移动任何元素。要移动任何元素。队列的队列的“扩容扩容”操作导致了部分元素的移动，也就增加了算操作导致了部分元素的移动，也就增加了算法的时间开销。所以一般在大多数的问题中常常根据问题的规模和法的时间开销。所以一般在大多数的问题中常常根据问题的规模和性质估计出顺序循环队列的尺寸大小，并在进队的算法设计中，队性质估计出顺序循环队列的尺寸大小，并在进队的算法设计中，队满时的处理是中止算法的执行，这样不仅不需要移动队列中的元素，满时的

47、处理是中止算法的执行，这样不仅不需要移动队列中的元素，而且进队算法也非常简单。如果实在无法预先估计所用队列可能达而且进队算法也非常简单。如果实在无法预先估计所用队列可能达到的最大容量时，最好还是采用队列的链式存储。到的最大容量时，最好还是采用队列的链式存储。出队出队bool DeQueue_Sq(SqQueue &Q,ElemType &e) if(Q.front=Q.rear) return false; e=Q.queueQ.front; Q.front=(Q.front+1) %Q.queuesize; return true;/ DeQueue_Sq取队首元素取队首元素

48、bool GetHead_Sq(SqQueue Q, ElemType &e) if(Q.front=Q.rear) return false; e=Q.queueQ.front; return true; / GetHead_Sq 判队空否判队空否bool QueueEmpty_Sq(SqQueue Q) return Q.rear=Q.front; / QueueEmpty_Sq撤销顺序循环队列撤销顺序循环队列void DestroyQueue_Sq(SqQueue &Q ) free(Q.queue); Q.queuesize=0; Q.front=Q.rear=0;/

49、DestroyQueue_Sq 总结总结对于顺序循环队列对于顺序循环队列Q Q的相关操作，归纳起来主要有以的相关操作，归纳起来主要有以下下4 4个要素：个要素：队空条件：队空条件：Q.rear=Q.frontQ.rear=Q.front队满条件：队满条件：(Q.rear+1)% (Q.rear+1)% maxsize=Q.front=Q.front进队操作：进队操作：Q.rear=(Q.rear+1) %Q.queuesizeQ.rear=(Q.rear+1) %Q.queuesize; ;元素进队元素进队出队操作：出队操作：Q.front=(Q.front+1) %Q.queuesize;

50、元素出队元素出队 3.3.3 链队及其操作链队及其操作1. 链队的定义链队的定义2. 链队的结构描述链队的结构描述 3. 链队的基本操作链队的基本操作1. 链队的定义链队的定义队列的链式存储结构简称为队列的链式存储结构简称为链队链队，它，它实际上也是通过由结点构成的单链表实现实际上也是通过由结点构成的单链表实现的，不同之处在于只允许在单链表的表尾的，不同之处在于只允许在单链表的表尾进行插入和在单链表的表头进行删除，因进行插入和在单链表的表头进行删除，因此，在一个链队中需要两个指针：此，在一个链队中需要两个指针：队首指队首指针针frontfront和和队尾指针队尾指针rearrear。其中。其中

51、frontfront指向指向队列的当前队首结点位置，队列的当前队首结点位置，rearrear指向队列指向队列的当前队尾结点位置。见的当前队尾结点位置。见图图3.163.16。图图3.16图图3.16 3.16 链队存储示意图链队存储示意图 2. 链队的结构描述链队的结构描述链队中的结点结构描述也与单链表一样。因而链队链队中的结点结构描述也与单链表一样。因而链队的结点结构可定义如下：的结点结构可定义如下：typedef LinkList QueuePtr; 因为链队的操作位置由队首指针和队尾指针所指示，因为链队的操作位置由队首指针和队尾指针所指示，在描述链队时，常常把队首指针和队尾指针定义在一个

52、在描述链队时，常常把队首指针和队尾指针定义在一个结构体类型中，如结构体类型中，如图图3.173.17所示（所示（Q Q为为LinkQueueLinkQueue变量），变量），则则LinkQueueLinkQueue定义如下：定义如下：typedef struct QueuePtr front; QueuePtr rear; LinkQueue; 图图3.173.17图图3.17 3.17 链队中队首指针和队尾指针构成结构体链队中队首指针和队尾指针构成结构体 3. 链队的基本操作链队的基本操作 初始化初始化求链队的长度求链队的长度进队进队出队出队取队首元素取队首元素判队空否判队空否撤消链队撤消链

53、队总结总结初始化初始化void InitQueue_L(LinkQueue &Q) Q.front=Q.rear=NULL; / InitQueue_L求链队的长度求链队的长度int QueueLength_L(LinkQueue Q) int k=0; QueuePtr p=Q.front; while(p) k+; p=p-next; return k;/ QueueLength_L 进队进队bool EnQueue_L (LinkQueue &Q, ElemType e) QueuePtr s; if(s=(LNode *)malloc(sizeof(LNode)=NUL

54、L) return false; s-data = e; s-next = NULL; if(Q.rear=NULL) Q.front=Q.rear=s; else Q.rear=Q.rear-next=s; return true;/ EnQueue_L 注意注意： 在链队的进队操作中，要考虑的特殊情况是队列是否为空队，在链队的进队操作中，要考虑的特殊情况是队列是否为空队，若队列为空队，则新结点作为新的队首结点和队尾结点若队列为空队，则新结点作为新的队首结点和队尾结点(如如图图3.18)；否则将新结点链接队列的未尾，作为否则将新结点链接队列的未尾，作为新新的队尾的队尾结点结点(如如图图3.1

55、9) 。图图3.18图图3.18 3.18 链队为空时的进队情况链队为空时的进队情况 图图3.19图图3.19 3.19 链队非空时的进队情况链队非空时的进队情况 出队出队 bool DeQueue_L(LinkQueue &Q, ElemType &e) QueuePtr p; if (Q.front=NULL) return false; p=Q.front; e=p-data; Q.front = p-next; if (Q.front=NULL) Q.rear = NULL; free(p); return true;/ DeQueue_L 注意注意： 在链队的出队操作

56、中，要考虑的特殊情况是队列是否为空队，在链队的出队操作中，要考虑的特殊情况是队列是否为空队，若队列为空队，则无法进行删除操作；若队列非空，还要考虑出队若队列为空队，则无法进行删除操作；若队列非空，还要考虑出队后队列是否为空，若出队后队列为空，则队尾指针也置后队列是否为空，若出队后队列为空，则队尾指针也置NULLNULL，如，如图图3.203.20和和图图3.213.21。 图图3.20图图3.20 3.20 链队出队后队非空情况链队出队后队非空情况 图图3.21图图3.21 3.21 链队出队后队空情况链队出队后队空情况 取队首元素取队首元素bool GetHead_L(LinkQueue Q

57、,ElemType &e) if(Q.front) e=Q.front-data; return true; else return false; / GetHead_L判非空否判非空否bool QueueEmpty_L(LinkQueue Q) if(!Q.front) return true; else return false;/ QueueEmpty_L撤销链队撤销链队void DestroyQueue_L(LinkQueue &Q ) QueuePtr p,p1; p=Q.front; while(p) p1=p; p=p-next; free(p1); Q.fron

58、t=Q.rear=NULL;/ DestroyQueue_L总结总结对于链队对于链队Q Q的相关操作，归纳起来主要的相关操作，归纳起来主要有以下有以下4 4个要素：个要素：队空条件：队空条件：Q.rear=Q.front=NULLQ.rear=Q.front=NULL进队操作：创建新结点进队操作：创建新结点s s，将其插入，将其插入到队尾到队尾出队操作：出队操作：修改队首指针，释放队修改队首指针，释放队首结点空间首结点空间3.3.4 其他队列其他队列双端队列双端队列是所有的插入和删除工作在线性表的两端是所有的插入和删除工作在线性表的两端进行。它可以看成是底元连在一起的两个栈。它与两栈进行。它可

59、以看成是底元连在一起的两个栈。它与两栈共享存储空间不同的是，两个栈的栈顶指针是往两端延共享存储空间不同的是，两个栈的栈顶指针是往两端延伸的，如伸的，如图图3.223.22所示。所示。优先级队列优先级队列是带有优先级的队列。队列是数据元素是带有优先级的队列。队列是数据元素的先进先出表，即最先进入队列的元素将最先被删除。的先进先出表，即最先进入队列的元素将最先被删除。但在有些软件系统中，有时也要求把进入队列中的元素但在有些软件系统中，有时也要求把进入队列中的元素分优先级，出队列时首先选择优先级最高的元素出队列分优先级，出队列时首先选择优先级最高的元素出队列（即优先级高的元素被先服务），对优先级相同

60、的元素（即优先级高的元素被先服务），对优先级相同的元素则按先进先出的原则出队列。显然，优先级队列和一般则按先进先出的原则出队列。显然，优先级队列和一般队列的主要区别是：优先级队列的出队列操作不是把队队列的主要区别是：优先级队列的出队列操作不是把队头元素出队列，而是把队列中优先级最高的数据元素出头元素出队列，而是把队列中优先级最高的数据元素出队列。队列。图图3.223.22图图3.22 3.22 双端队列示意图双端队列示意图 3.4 队列的应用举例队列的应用举例例例3.4 运动会比赛日程安排，即划分无冲突子集问题。运动会比赛日程安排，即划分无冲突子集问题。某运动会设立某运动会设立N N个比赛项目，每个运动员可以参加个比赛项目，每个运动员可以参加1 13 3个项目。个项目。试问如何安排比赛日程，既可以使同一运动员参加的项目不安排在试问如何安排比赛日程，既可以使同一运动员参加的项目不安排在同一单位时间进行，又使总的竞赛日程最短同一单位时间进行，又使总的竞赛日程最短? ? 例例3.53.5 事件规划问题。事件规划问题。 有一个渡口，每条渡轮一次能装载有一个渡口，每条渡轮一次能