第第3 3章章 栈和队列栈和队列 3.2 3.2 队列队列3.1 3.1 栈栈 本章小结本章小结13.1.1 3.1.1 栈的基本概念栈的基本概念 3.1.2 3.1.2 栈的顺序存储结构栈的顺序存储结构 3.1.3 3.1.3 栈的链式存储结构栈的链式存储结构3.1 3.1 栈栈 2 栈是一种特殊的线性表，这种线性表上的插入栈是一种特殊的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。表中允许进和删除运算限定在表的某一端进行。表中允许进行插入、删除操作的一端称为行插入、删除操作的一端称为栈顶栈顶；另一端称为；另一端称为栈底栈底。 处于栈顶位置的数据元素称为处于栈顶位置的数据元素称为栈顶元素栈顶元素。不含。不含任何数据元素的栈称为任何数据元素的栈称为空栈空栈。 栈栈的的插插入入操操作作通通常常称称为为进进栈栈或或入入栈栈,栈栈的的删删除除操作通常称为操作通常称为退栈退栈或或出栈出栈。3.1.1 3.1.1 栈的基本概念栈的基本概念 3 栈栈的的特特点点是是后后进进先先出出。举举一一个个例例子子说说明明栈栈结结构构的的特特征征，假假设设有有一一个个很很窄窄的的死死胡胡同同，胡胡同同里里能能容容纳纳若若干干人人，但但每每次次只只能能容容许许一一个个人人进进出出。现现有有五五个个人人，分分别别编编号号为为，按按编编号号的的顺顺序序依依次次进进入入此此胡胡同同，如如图图3.1所所示示。此此时时若若编编号号为为的的人人要要退退出出胡胡同同，必必须须等等退退出出后后才才可可以以。若若要要退退出出，则则必必须须等等到到、依依次次都都退退出出后后才才行行。这这里里，人人进进出出胡胡同的原则是后进去的先出来。同的原则是后进去的先出来。 图图3.1死胡同示意图死胡同示意图4 栈可以比作这里的死胡同，栈顶相当于胡栈可以比作这里的死胡同，栈顶相当于胡同口，栈底相当于胡同的另一端，进、出胡同口，栈底相当于胡同的另一端，进、出胡同可看作栈的插入、删除运算。插入、删除同可看作栈的插入、删除运算。插入、删除运算都在栈顶进行，相当于进出都经过胡同运算都在栈顶进行，相当于进出都经过胡同口。这表明栈修改的原则是口。这表明栈修改的原则是先进后出先进后出（或（或后后进先出进先出）。因此栈又称为后进先出线性表。）。因此栈又称为后进先出线性表。5栈顶栈顶栈底栈底出栈出栈进栈进栈栈栈示意图示意图6 例例1 设设有有4个个元元素素a、b、c、d进进栈栈,给给出出它它们们所有可能的出栈次序。所有可能的出栈次序。 答答:所有可能的出栈次序如下所有可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba7 例例2 设设一一个个栈栈的的输输入入序序列列为为A,B,C,D,则则借借助助一一个栈所得到的输出序列不可能是个栈所得到的输出序列不可能是 。(A) A,B,C,D(B) D,C,B,A (C) A,C,D,B(D) D,A,B,C 答答:可以简单地推算可以简单地推算,得容易得出得容易得出D,A,B,C是是不可能的不可能的,因为因为D先出来先出来,说明说明A,B,C均在栈中均在栈中,按照入栈顺序按照入栈顺序,在栈中顺序应为在栈中顺序应为D,C,B,A,出栈的出栈的顺序只能是顺序只能是D,C,B,A。所以本题答案为所以本题答案为D。8 例例3 已已知知一一个个栈栈的的进进栈栈序序列列是是1,2,3,n,其其输输出出序序列是列是p1,p2,pn,若若p1=n,则则pi的值的值 。(A) i (B) n-i (C) n-i+1 (D) 不确定不确定 答答:当当p1=n时时,输出序列必是输出序列必是n,n-1,3,2,1,则有则有: p2=n-1, p3=n-2, , pn=1推断出推断出pi=n-i+1,所以本题答案为所以本题答案为C。9 例例4 设设n个个元元素素进进栈栈序序列列是是1,2,3,n,其其输输出出序序列是列是p1,p2,pn,若若p1=3,则则p2的值的值 。(A) 一定是一定是2(B) 一定是一定是1(C) 不可能是不可能是1 (D) 以上都不对以上都不对 答答:当当p1=3时时,说说明明1,2,3先先进进栈栈,立立即即出出栈栈3,然然后后可可能能出出栈栈,即即为为2,也也可可能能4或或后后面面的的元元素素进进栈栈,再再出出栈栈。因因此此,p2可可能能是是2,也也可可能能是是4,n,但但一一定定不不能能是是1。所所以本题答案为以本题答案为C。10栈的基本运算至少应包括以下栈的基本运算至少应包括以下5种种: (1)(1)初始化栈初始化栈InitStack(stInitStack(st):):构造一个空栈构造一个空栈stst。 (2)(2)进栈进栈Push(st,xPush(st,x):):将元素将元素x x插入到栈插入到栈stst中作为中作为栈顶元素。栈顶元素。 (3)(3)出栈出栈Pop(st,xPop(st,x):):其作用是当栈其作用是当栈stst不空时，将不空时，将栈顶元素赋给栈顶元素赋给x,x,并从栈中并从栈中删除当前栈顶删除当前栈顶。 (4)(4)取栈顶元素取栈顶元素GetTop(st,xGetTop(st,x):):若若stst不空，由不空，由x x返返回当前的栈顶元素回当前的栈顶元素, ,当栈当栈stst为空时，结果为一特殊标为空时，结果为一特殊标志志( (。 (5)(5)判断栈是否为空判断栈是否为空StackEmpty(stStackEmpty(st):):若栈若栈stst为为空空, ,则返回则返回1 1；否则返回；否则返回0 0。11例例3.3 3.3 利用栈的基本运算，编写一个算法输入若干整数，以利用栈的基本运算，编写一个算法输入若干整数，以0 0标识输入结束。然后按与输入相反次序输出这些整数。标识输入结束。然后按与输入相反次序输出这些整数。解：使用一个栈实现本例要求，先将输入的整数进栈，然后出栈并输出。对应的算法解：使用一个栈实现本例要求，先将输入的整数进栈，然后出栈并输出。对应的算法如下：如下： void Invert()void Invert() intint n; n; coutcout n; n; if (n=0) break; / if (n=0) break; /输入值输入值n n为为0 0时退出循环时退出循环 Push(st,nPush(st,n); /n); /n进栈进栈 coutcout “输出序列：输出序列：”； while (!while (!StackEmpty(stStackEmpty(st) /) /栈不空时循环栈不空时循环 Pop(st,nPop(st,n); /); /出栈出栈n n coutcout n n “ ”; /; /输出输出n n 12 3.1.2 3.1.2 栈的顺序存储结构栈的顺序存储结构 栈的顺序存储结构称为顺序栈。顺序栈通常由一栈的顺序存储结构称为顺序栈。顺序栈通常由一个个一维数组一维数组和和一个记录栈顶元素位置的变量一个记录栈顶元素位置的变量组成。习组成。习惯上将栈底放在数组下标小的那端。假设用一维数组惯上将栈底放在数组下标小的那端。假设用一维数组sq5sq5表示一个栈，则需使用一个变量表示一个栈，则需使用一个变量toptop记录当前栈记录当前栈顶下标值。顶下标值。 图图 (a)(a)表示顺序栈为栈空，这也是初始化运算得表示顺序栈为栈空，这也是初始化运算得到的结果。此时栈顶下标值到的结果。此时栈顶下标值top=-1top=-1。如果作出栈运算，如果作出栈运算，则会则会“下溢下溢”。13顺序栈进栈和出栈示意图顺序栈进栈和出栈示意图top-1toptoptop14顺序栈类型定义如下：顺序栈类型定义如下：顺序栈被定义为一个结构体类型，它有两个域：顺序栈被定义为一个结构体类型，它有两个域：datadata和和toptop。DataData为一个一维数组，用于存储栈中元素，为一个一维数组，用于存储栈中元素，ElemTypeElemType为栈元为栈元素的数据类型，可以根据需要而指定为某种具体的类型。素的数据类型，可以根据需要而指定为某种具体的类型。toptop为为intint型，它的实际取值范围为型，它的实际取值范围为0 0 StackSize-1StackSize-1。top=-1top=-1表示栈空；表示栈空；top=StackSize-1top=StackSize-1表示栈满。表示栈满。const const intint StackSizeStackSize=100; /=100; /顺序栈的初始分配空间顺序栈的初始分配空间 typedeftypedef structstruct sqstsqst ElemTypeElemType dataStackSizedataStackSize ；/保存栈中元素保存栈中元素 intint top top； /栈指针栈指针 SqStackSqStack；15顺序栈的基本运算算法如下顺序栈的基本运算算法如下:(1)初始化栈运算算法初始化栈运算算法 此此算算法法主主要要用用于于创创建建一一个个空空栈栈, ,并并将将栈栈顶顶下下标标toptop初始化为初始化为-1-1。 void InitStack(SqStack &st) /st为为引引用用型型参参数数 st.top=-1; 16 (2)进栈运算算法进栈运算算法 其其主主要要操操作作是是：栈栈顶顶下下标标加加1,将将进进栈栈元元素素放放进进栈栈顶下标所指的位置上。顶下标所指的位置上。 int Push(SqStack &st, ElemType x) if (st.top=StackSize-1) /栈满栈满 return 0; else st.top+; st.datast.top=x; return 1; 17 (3)出栈运算算法出栈运算算法 其其主主要要操操作作是是：先先将将栈栈顶顶元元素素取取出出，然然后后将将栈栈顶顶下标减下标减1。 int Pop(SqStack &st, ElemType &x) /x为引用型参数为引用型参数 if (st.top=-1) return 0; else x=st.datast.top; st.top-; return 1; 18 (4)取栈顶元素运算算法取栈顶元素运算算法 其其主主要要操操作作是是：将将栈栈中中top处处的的元元素素取取出出赋赋给给变变量量x。 int GetTop(SqStack st, ElemType &x) if (st.top=-1) /栈空栈空 return 0; else x=st.datasq.top; return 1; 19 (5)判断栈空运算算法判断栈空运算算法 其其主主要要操操作作是是：若若栈栈为为空空（top=-1）则则返返回回值值1，否则返回，否则返回0。 int StackEmpty(SqStack st) if (st.top=-1) return 1; else return 0; 20 例例3.4 设设计计一一个个算算法法，判判断断一一个个表表达达式式中中符符号号“（”与与“）”、“”与与“”、“”与与“”是是否匹配。若匹配，则返回否匹配。若匹配，则返回1；否则返回；否则返回0。 解解:设置一个栈设置一个栈st,用用i扫描表达式扫描表达式exps：遇到遇到(、和和时，将其进栈时，将其进栈,遇到）、遇到）、和和时时,判断栈顶是判断栈顶是否是匹配的括号。若不是，则退出扫描过程，返否是匹配的括号。若不是，则退出扫描过程，返回回0；否则直到；否则直到exps扫描完毕为止。若扫描完毕为止。若top=0，则则返回返回1。对应算法如下：。对应算法如下：(以下为完整程序）以下为完整程序）#include const int Max=100; int match(char *exps) char stMax,top=-1,i=0; int nomatch=0; while (expsi!=0& nomatch=0)21 switch(expsi) case (: sttop=expsi;top+;break; case : sttop=expsi;top+;break; case : sttop=expsi;top+;break; case ): if(sttop=() top-; else nomatch=1; break; case : if(sttop=) top-; else nomatch=1; break; case : if(sttop=) top-; else nomatch=1; break; 22 i+; if (nomatch=0)&top=-1 /栈空且符号匹配栈空且符号匹配则返回则返回1 return 1; else return 0; /否则返回否则返回0 void main()char exp=3-1+2*(5+3)/2;if (match(exp)=1)printf(表达式表达式%s括号配对括号配对n,exp);elseprintf(表达式表达式%s括号不配对括号不配对n,exp);233.1.3 3.1.3 栈的链式存储结构栈的链式存储结构 栈的链式存储结构是以某种形式的链表作为栈的栈的链式存储结构是以某种形式的链表作为栈的存储结构，栈的链式存储结构简称为链栈，其组织形存储结构，栈的链式存储结构简称为链栈，其组织形式与单链表类似。如图式与单链表类似。如图3.43.4所示。其中，单链表的第所示。其中，单链表的第一个节点就是链栈栈顶结点，一个节点就是链栈栈顶结点，lsls称为栈顶指针称为栈顶指针。24链栈链栈示意图示意图 lslsa1 an a2 栈底结点栈底结点栈顶结点栈顶结点 栈由栈顶指针栈由栈顶指针lsls唯一确定。栈中的其他结点唯一确定。栈中的其他结点通过它们的通过它们的nextnext域链接起来。栈底结点的域链接起来。栈底结点的nextnext域域为为NULLNULL。因链栈本身没有容量限制，故在用户内因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况。存空间的范围内不会出现栈满情况。25 链栈的类型定义如下链栈的类型定义如下: typedef struct stnode ElemType data;/存储结点数据存储结点数据 struct stnode *next;/指针域指针域 LinkStack;26在在链栈中链栈中, ,栈的基本运算算法如下栈的基本运算算法如下: : (1) (1)初始化栈运算算法初始化栈运算算法 其主要操作是：创建一个头结点其主要操作是：创建一个头结点* *lsls, , 用用lsls=NULL=NULL标识栈为空栈。标识栈为空栈。 void void InitStack(LinkStackInitStack(LinkStack *& *&lsls) ) lsls=NULL; =NULL; 27 (2)进栈运算算法进栈运算算法 其其主主要要操操作作是是：先先创创建建一一个个新新节节点点，其其data域域值值为为x；然后将该结点插入到然后将该结点插入到*ls结点之后作为栈顶结点。结点之后作为栈顶结点。 void Push(LinkStack *&ls,ElemType x) /ls为为引引用用型型参参数数 LinkStack *p;p=(LinkStack *)malloc(sizeof(LinkStack);p-data=x;p-next=ls;ls=p; 28 (3)出栈运算算法出栈运算算法 其主要操作是：将栈顶结点（即其主要操作是：将栈顶结点（即ls-next所指结点所指结点 ）的的data域值赋给域值赋给x，然后删除该栈顶结点。然后删除该栈顶结点。int Pop(LinkStack *&ls,ElemType &x) /ls为引用型参数为引用型参数 LinkStack *p;if (ls=NULL) /栈空，下溢出栈空，下溢出 return 0; else p=ls; x=p-data; ls=p-next; free(p); return 1; 29 (4)取栈顶元素运算算法取栈顶元素运算算法 其其主主要要操操作作是是：若若栈栈为为空空（即即ls-next所所指指结结点点 ）的的data域值赋给域值赋给x。 int GetTop(LinkStack *ls,ElemType &x) if (ls=NULL) /栈空，下溢出栈空，下溢出 return 0; else x=ls-data; return 1; 30 (5)判断栈空运算算法判断栈空运算算法 其其主主要要操操作作是是：若若栈栈为为空空（ls-next=NULL）,则返回值则返回值1，否则返回，否则返回0。 int StackEmpty(LinkStack *ls) if (ls=NULL) return 1; else return 0; 31例例3.5 3.5 假设以假设以I I和和O O分别表示进栈和出栈操作，分别表示进栈和出栈操作，栈的初态和终态均为空，进栈和出栈的操栈的初态和终态均为空，进栈和出栈的操作序列可表示为仅由作序列可表示为仅由I I和和O O组成的序列。组成的序列。 下面所示的序列中哪些是合法的？下面所示的序列中哪些是合法的？ A.IOIIOIOO B.IOOIOIIO A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO C.IIIOIOIO D.IIIOOIOO 通过对通过对的分析，写出一个算法判定所的分析，写出一个算法判定所给的操作序列是否合法。若合法返回给的操作序列是否合法。若合法返回1 1；否；否则返回则返回0 0。（假设被判定的操作序列已存入。（假设被判定的操作序列已存入一维数组中）一维数组中）32解：解： A A、D D均合法，而均合法，而B B、C C不合法。因为在不合法。因为在B B中，先进栈一次，立即出栈中，先进栈一次，立即出栈2 2次，这会造成栈次，这会造成栈下溢。在下溢。在C C中共进栈中共进栈5 5次，出栈次，出栈3 3次，栈的终态次，栈的终态不为空。不为空。 本例用一个链栈来判断操作序列是否合本例用一个链栈来判断操作序列是否合法，其中法，其中A A为存放操作序列的字符数组，为存放操作序列的字符数组，n n为为该数组的元素个数（这里的该数组的元素个数（这里的ElemTypeElemType类型设类型设定为定为charchar。）。）33int Judge(char A ,int n) int i; ElemType x; LinkStack *ls; InitStack(ls); for (i=0;inext=NULL); /栈为栈为空空时时返回返回1，否，否则则返回返回0343.2 3.2 队列队列 3.2.1 3.2.1 队列的基本概念队列的基本概念 返回返回 3.2.2 3.2.2 队列的顺序存储结构队列的顺序存储结构 3.2.3 3.2.3 队列的链式存储结构队列的链式存储结构35 队列也是一种运算受限的线性表队列也是一种运算受限的线性表,在这种线性在这种线性表上，插入限定在表的某一端进行，删除限定在表表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为的另一端进行。允许插入的一端称为队尾队尾，允许删，允许删除的一端称为除的一端称为队头队头。 3.2.1 3.2.1 队列的基本概念队列的基本概念 a1 a2 a3 an出队列出队列入队列入队列队头队头队尾队尾36 队列与现实生活中人们为得到某种服务（如购队列与现实生活中人们为得到某种服务（如购物、购票等）而排队十分相似。排队的规则是不允物、购票等）而排队十分相似。排队的规则是不允许许“插队插队”，新加入的成员只能排在队尾，而且队，新加入的成员只能排在队尾，而且队中全体成员只能按顺序向前移动，当到达队头（并中全体成员只能按顺序向前移动，当到达队头（并得到服务）后离队。队列的特点是得到服务）后离队。队列的特点是先进先出先进先出，因此，因此，队列又称为先进先出线性表。队列又称为先进先出线性表。37队列以线性表为逻辑结构，其基本运算如下：队列以线性表为逻辑结构，其基本运算如下：v 初始化队列初始化队列InitQueue(qu)v 入队列入队列EnQueue(qu,x)v 出队出队DeQueue(qu,x)v 取队头元素取队头元素GetHead(qu,x)v 判断队列空判断队列空QueueEmptyq(qu)383.2.2 3.2.2 队列的顺序存储结构队列的顺序存储结构v队列的顺序存储结构简称为顺序队，它由一个一维队列的顺序存储结构简称为顺序队，它由一个一维数组（用于存储队列中元素）及两个分别指示队头数组（用于存储队列中元素）及两个分别指示队头和队尾的变量组成，和队尾的变量组成，v这两个变量分别称为这两个变量分别称为“队头指针队头指针”和和“队尾指针队尾指针”（注意它们并非指针变量，而是数组的下标）。（注意它们并非指针变量，而是数组的下标）。v队尾指针（队尾指针（real）指示队尾元素在一维数组中的指示队尾元素在一维数组中的当当前位置前位置，v队头指针（队头指针（front）指示队头元素在一维数组中的当指示队头元素在一维数组中的当前位置的前位置的前一个位置前一个位置。39顺序队列的类型定义如下顺序队列的类型定义如下: const int QueueSize=20; /队列的容量队列的容量 typedef struct sqqueue ElemType dataQueueSize； /保存队中元素保存队中元素 int front, rear； /队队头头和和队队尾尾指指针针 SqQueue 其中其中data为存储队列中元素的一维数组。为存储队列中元素的一维数组。 队队头头指指针针front和和队队尾尾指指针针rear定定义义为为整整型型变变量，实际取值范围是量，实际取值范围是0QueueSize-1。40队列的入队和出队操作示意图队列的入队和出队操作示意图 4 3 2 1 0front,rear(a)(a)空队空队 DC B A frontrear ( (b b) )A,B,C,DA,B,C,D入队入队 43210DCB frontrear (c)(c)出队一次出队一次 4 32 1 0 front rear (d)(d)出队出队 4 4 次次 4 3 21 0 41 从从 前前 图图 中中 看看 到到 ,图图 (a)为为 队队 列列 的的 初初 始始 状状 态态 ,有有front=rear成立成立,该条件可以作为队列空的条件。该条件可以作为队列空的条件。 那那么么能能不不能能用用rear=QueueSize-1作作为为队队满满的的条条件件呢呢？显显然然不不能能,在在图图(d)中中,队队列列为为空空,但但仍仍满满足足该该条条件件。这这时时入入队队时时出出现现“上上溢溢出出”,这这种种溢溢出出并并不不是是真真正正的的溢溢出出,在在data数数组组中中存存在在可可以以存存放放元元素素的的空空位位置置,所所以以这这是一种假溢出。是一种假溢出。 为为了了能能够够充充分分地地使使用用数数组组中中的的存存储储空空间间,把把数数组组的的前前端端和和后后端端连连接接起起来来,形形成成一一个个环环形形的的顺顺序序表表,即即把把存存储队列元素的表从逻辑上看成一个环储队列元素的表从逻辑上看成一个环,称为称为环形队列环形队列。42 环形队列首尾相连环形队列首尾相连,当队首当队首front指针满足指针满足 front=QueueSize-1后后,再前进一个位置就自动到再前进一个位置就自动到0,这这可以利用除法取余的运算可以利用除法取余的运算(MOD)来实现来实现: 队头指针进队头指针进1: front=(front+1) MOD QueueSize 队队尾指针进尾指针进1: rear=(rear+1)MOD QueueSize 环环形形队队列列的的队队头头指指针针和和队队尾尾指指针针初初始始化化时时都都置置0:front=rear=0。在在队队尾尾插插入入新新元元素素和和删删除除队队头头元元素素时时,指针都按逆时针方向进指针都按逆时针方向进1。43 为了区别于队列空条件，用为了区别于队列空条件，用 (rear+1)MOD QueueSize=front来判断是否队已满，也就是说，让来判断是否队已满，也就是说，让rear指到指到front的前的前一位置就认为队列已满。此时，因队头指针指示实际一位置就认为队列已满。此时，因队头指针指示实际队头的前一个位置所以在队列满时实际空了一个元素队头的前一个位置所以在队列满时实际空了一个元素位置。位置。 如果不留这个空位置，让队尾指针如果不留这个空位置，让队尾指针rear一直存到这一直存到这个位置，必然有个位置，必然有rear=front，则队列空条件和队列满则队列空条件和队列满条件就混淆了。条件就混淆了。44循环队的入队和出队操作示意图循环队的入队和出队操作示意图rear 0 1 2 3 4 front (a)空队空队 (b)A,B,C入队入队 rear 0 1 2 3 4 front ABC rear 0 1 2 3 4 A B C D front (c)D入队入队,队满队满 rear 0 1 2 3 4 C D front (d)出队出队2次次 rear 0 1 2 3 4 front (e)出队出队2次次,队空队空 45环形队列qu的4要素：v队空条件：队空条件：qu.front=qu.rearv队满条件：队满条件：(qu.rear+1)%QueueSize=qu.frontv进队操作：进队操作：qu.rear循环进循环进1；元素进队。；元素进队。v出队操作：出队操作：qu.front循环进循环进1；元素出队。；元素出队。46 在环形队列中在环形队列中,实现队列的基本运算算法如下实现队列的基本运算算法如下: (1)初始化队列运算算法初始化队列运算算法 其其主主要要操操作作是是：创创建建一一个个队队列列结结点点，用用sq指指向向该该队列结点，并指定队列结点，并指定sq-front=sq-rear=0 void InitQueue(SqQueue *&sq) /qu为引用型参数为引用型参数 sq=(SqQueue *)malloc (sizeof(SqQueue);sq-front=sq-rear=0; /指针初始化指针初始化 47 (2)入队运算算法入队运算算法 其其主主要要操操作作是是：先先判判断断队队列列是是否否已已满满，若若不不满满，将队尾指针增将队尾指针增1,在该位置存放在该位置存放x。对应算法如下对应算法如下: int EnQueue(SqQueue *&sq,ElemType x) if (sq-rear+1)%QueueSize=sq-front) /队满队满return 0;sq-rear=(sq-rear+1)%QueueSize; /队队尾尾循循环环进进1sq-datasq-rear=x;return 1; 48 (3)出队运算算法出队运算算法 其其主主要要操操作作是是：先先判判断断队队列列是是否否已已空空,若若不不空空，让让队队头指针增头指针增1,将该位置的元素值赋给将该位置的元素值赋给x。 int DeQueue(SqQueue *sq,ElemType &x) if (sq-rear=sq-front) return 0;sq-front=(sq-front+1)%QueueSize; /队头循环进队头循环进1x=sq-datasq-front;return 1; 49 (4)取队头元素运算算法取队头元素运算算法 其其主主要要操操作作是是：先先判判断断队队列列是是否否已已空空,若若不不空空，让让队队头指针上一个位置的元素值赋给头指针上一个位置的元素值赋给x。 int GetHead(SqQueue *sq,ElemType &x) if (sq-rear=sq-front) return 0;x=sq-data(sq-front+1 )%QueueSize;return 1; 50 (5)判断队列是否为空判断队列是否为空 若若队队列列q满满足足q-front=q-rear条条件件,则则返返回回1；否则返回否则返回0。对应算法如下。对应算法如下: int QueueEmpty(SqQueue *q) return(q-front=q-rear); 51 例例3.8 对于环形队列，写出求队列中元素个数的公式。对于环形队列，写出求队列中元素个数的公式。解：根据环形队列的特点，有以下情况：解：根据环形队列的特点，有以下情况： 0 队空，即队空，即front=rear元素个数元素个数= rear-front 若若rearfront rear+QueueSize-front 若若rearfront=qu-count=0; int EnQueue(SqQueue *sq,ElemType x) /进队进队 if(sq-count=QueueSize) return 0; sq-count+; sq-data(sq-front+sq-count)%QueueSize=x; return 1; 54int DeQueue(SqQueue *sq,ElemType &x) /出队出队 if(sq-count=0) return 0; sq-count-; sq-front=(sq-front+1)%QueueSize; x= sq-datasq-front; return 1; int GetHead(SqQueue *sq,ElemType &x) /取队头取队头 if(sq-count=0) return 0; x= sq-data(sq-front+1)%QueueSize; return 1;55int QueueEmpty(SqQueue *sq) /判断队空判断队空 if(sq-count=0) return 1; else return 0;56 队队列列的的链链式式存存储储结结构构简简称称为为链链队队，它它实实际际上上是是一一个个同同时时带带有有首首指指针针和和尾尾指指针针的的单单链链表表。首首指指针针指指向向队队头头结结点点，尾尾指指针针指指向向队队尾尾结结点点即即单单链链表表的最后一个结点。的最后一个结点。3.2.3 3.2.3 队列的链式存储结构队列的链式存储结构57链列的入队和出队操作示意图链列的入队和出队操作示意图58链队的类型定义如下链队的类型定义如下: typedef struct QNode ElemType data;struct QNode *next; QType; /链队中结点的类型链队中结点的类型 typedef struct qptr QType *front; *rear; LinkQueue; /链队类型链队类型 在这样的队列中，队空的条件是在这样的队列中，队空的条件是 lqlq-front=-front=lqlq-rear=NULL-rear=NULL。一般情况下，链队是不会出现队满的情况。一般情况下，链队是不会出现队满的情况。59 在链队上实现队列的基本运算算法如下在链队上实现队列的基本运算算法如下: (1)初始化队列运算算法初始化队列运算算法 其主要操作是：置结点其主要操作是：置结点lq*的的rear和和front均为均为NULL: void InitQueue(LinkQueue *&lq) lq-rear=lq-front=NULL; /初始情况初始情况 60 (2)入队运算算法入队运算算法 其其主主要要操操作作是是：创创建建一一个个新新结结点点，将将其其链链接接到到链链队队的的末末尾，并由尾，并由rear指向它。指向它。void EnQueue(LinkQueue *&lq,ElemType x) QType *s; s=(QType *)malloc(sizeof(QType);s-data=x;s-next=NULL; if (lq-front=NULL& lq-rear=NULL) lq-rear=q-front=s;else lq-rear-next=s; lq-rear=s; 61 (3)(3)出队运算算法出队运算算法 int DeQueue(LinkQueue *&lq, ElemType &x) QType *p;if (lq-front=NULL & lq-rear=NULL) return 0; p=lq-front;x=p-data ; if (lq- rear=lq- front) lq-rear=lq-front=NULL; else lq-front=p-next; free(p);return 1; 62 ( (4)4)取队头元素运算算法取队头元素运算算法 其主要操作是：将其主要操作是：将* *frontfront结点的结点的datadata域值赋给域值赋给x x。int GetHead(LinkQueue *&lq,ElemType &x) if (lq-front=NULL &lq-rear=NULL) return 0; x=lq-front-data ; return 1; 63 (5)判断队空运算算法判断队空运算算法 其其主主要要操操作作是是：若若链链队队为为空空，则则返返回回1；否否则则返返回回0。对应算法如下。对应算法如下: int QueueEmpty(LinkQueue *lq) if (lq-front=NULL& lq-rear=NULL) return 1;else return 0; 64例例3.10 3.10 若使用循环链表来表示队列，若使用循环链表来表示队列，p p是链表中一个是链表中一个指针。试基于此结构给出队列的入队（指针。试基于此结构给出队列的入队（EnQueueEnQueue）和出队（和出队（ DeQueueDeQueue ）算法，算法，p p为何值时队列空？为何值时队列空？解：这里使用的循环链表不带头结点，规定解：这里使用的循环链表不带头结点，规定p p始终指始终指向队尾结点向队尾结点, p-next, p-next即为队头结点。当即为队头结点。当p=NULLp=NULL时时队列为空。队列的入队和出队算法如下：队列为空。队列的入队和出队算法如下：typedeftypedef structstruct node node ElemTypeElemType data; data; structstruct QnodeQnode *next; *next; QnodeQnode; ;65void EnQueue(Qnode *&p,ElemType x) /入队 Qnode *s; s=(Qnode *)malloc(sizeof(QNode); s-data=x; if (p=NULL) p=s; p-next=p; else s-next=p-next; p-next=s; p=s; p-nextp-next p-next=sp-next=s s-next=p-nexts-next=p-nextpsx p 66int DeQueue(Qnode *&p,ElemType &x) /出队 Qnode *s; if (p=NULL) return 0; if ( p-next=p) /只有一个结点时 x=p-next-data; free(p); p=NULL; else s=p-next; x=s-data; p-next=s-next; free(s); return 1;67s=pnextpnextfree(s)释放空间释放空间ppnext=snextdatax=s-data68例例3.11 设计一个程序，反映病人到医院看病、排队看医生的情设计一个程序，反映病人到医院看病、排队看医生的情况。况。解：病人排队看医生采用先到先看的方式，所以要用到一个队解：病人排队看医生采用先到先看的方式，所以要用到一个队列，这里设计了一个带头结点的单链表作为队列。完整的程列，这里设计了一个带头结点的单链表作为队列。完整的程序如下：序如下：#include #include#includeTypedef struct QNode char data10; struct QNode *next;Qtype;Typedef struct qptr Qtype *front,*rear;LinkQueue;69void SeeDoctor () int sel,flag=1; LinkQueue *lq; Qtype *s; char name(10); lq=(LinkQueue *)malloc(sizeof(LinkQueue); lq-front=(Qtype *)malloc(sizeof(QType); lq-front-next=NULL; lq-rear=lq-front; while(flag=1) cout “1:排队排队 2:看医生看医生 3:查看排队查看排队 0:下班下班 请选择请选择:”; cin front!=lq-rear) cout 请排队的患者明天就医请排队的患者明天就医” endl; flag=0; break;case 1: cout 输入患者姓名输入患者姓名:”; cin name; s=(QType *)malloc(sizeof(QType); strcpy(s-data,name);s-next=NULL; lq-rear-next=s;lq-rear=s; break;case2: if(lq-front=lq-rear) cout 没有排队的患者没有排队的患者”front-next; if(lq-rear=s) lq-rear=lq-front; cout 患者患者”data “看医生看医生”front-next=s-next; free(s); break;case3: if(lq-front=lq-rear) cout 没有排队的患者没有排队的患者”front-next; cout 排队患者排队患者:”; while(s!=NULL) cout data next; cout 输入患者姓名输入患者姓名: :SmithSmith1:1:排队排队 2:2:看医生看医生 3:3:查看排队查看排队 0:0:下班下班 请选择请选择: :1 1 输入患者姓名输入患者姓名: :JohnJohn1:1:排队排队 2:2:看医生看医生 3:3:查看排队查看排队 0:0:下班下班 请选择请选择: :3 3 排队患者排队患者:Smith John:Smith John1:1:排队排队 2:2:看医生看医生 3:3:查看排队查看排队 0:0:下班下班 请选择请选择: :1 1 输入患者姓名输入患者姓名: :MaryMary1:1:排队排队 2:2:看医生看医生 3:3:查看排队查看排队 0:0:下班下班 请选择请选择: :2 2 患者患者SmithSmith看医生看医生1:1:排队排队 2:2:看医生看医生 3:3:查看排队查看排队 0:0:下班下班 请选择请选择: :2 2 患者患者JohnJohn看医生看医生1:1:排队排队 2:2:看医生看医生 3:3:查看排队查看排队 0:0:下班下班 请选择请选择: :0 0 请排队的患者就医请排队的患者就医74本章小结本章小结本章基本学习要点如下本章基本学习要点如下: (1)理理解解栈栈和和队队列列的的特特性性以以及及它它们们之之间间的的差差异异,知知道在何时使用哪种数据结构。道在何时使用哪种数据结构。 (2)重重点点掌掌握握在在顺顺序序栈栈上上和和链链栈栈上上实实现现栈栈的的基基本本运算算法运算算法,注意栈满和栈空的条件。注意栈满和栈空的条件。 (3)重重点点掌掌握握在在顺顺序序队队上上和和链链队队上上实实现现队队列列的的基基本运算算法本运算算法,注意环形队列上队满和队空的条件。注意环形队列上队满和队空的条件。 (4)灵灵活活运运用用栈栈和和队队列列这这两两种种数数据据结结构构解解决决一一些些综合应用问题。综合应用问题。75 作业：练习题作业：练习题3 3书面作业：书面作业：1，2，5。（修改部分数据）。（修改部分数据） 上机作业：上机作业：例例3.114，7，修改为：，修改为： ，表表示示输输入入结结束束，要要求求将将队队列列处处理理成成循循环环链链式式队列，队列，。76