第三章 栈和队列

1、栈 队列 递归第三章栈和队列第三章栈和队列1栈 ( Stack )定义:是限定仅在表尾进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点：后进先出 (LIFO)a1topbottoman.进栈进栈 出栈出栈2栈的抽象数据类型定义为： ADT Stack ADT Stack 数据对象：D D a ai i|a|ai iElemSetElemSet, , i i=1,2,.,n, n0 =1,2,.,n, n0 数据关系：R1R1 a | a | ai-1i-1 , , a ai i D, D, i i=2,.,n =2,.,n 约定an端为栈顶

2、,a1端为栈底。 基本操作：基本操作： . ADT Stack ADT Stack template class Stack public: Stack ( int sz = 10 ); /构造函数 void Push ( Type& item); /进栈 Type Pop ( ); /出栈 Type GetTop ( ); /取栈顶元素 void MakeEmpty ( ); /置空栈 int IsEmpty ( ) const; /判栈空否 int IsFull ( ) const; /判栈满否栈的表示和实现顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素

3、，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈a 进栈b 进栈aabtopbasetopbasetop5toptopabcdee 进栈abcdef 进栈溢出abde 出出栈cbasebasebasetop6顺序栈的定义及存储表示顺序栈的定义及存储表示# #define STACK_INIT_SIZE 100define STACK_INIT_SIZE 100/栈存储空间的初始分配量栈存储空间的初始分配量# #define STACKINCREMENT 10define STACKINCREMENT 10/ / 栈存储空间的分配增量栈存储空间的分

4、配增量typedeftypedef structstruct SElemTypeSElemType * *base;base;/栈空间基址称为栈底指针，指向栈底位置栈空间基址称为栈底指针，指向栈底位置SElemTypeSElemType * *top top /栈顶指针栈顶指针, ,约定栈顶指针指向栈顶元素的约定栈顶指针指向栈顶元素的 /下（后面）一个位置；下（后面）一个位置； intint stacksizestacksize; ; / /当前分配的栈空间大小当前分配的栈空间大小 /（以（以sizeofsizeof( (SElemTypeSElemType) )为单位）为单位） SqStac

5、kSqStack; ;/ / SqStackSqStack: :：结构类型名结构类型名7初始化操作初始化操作参数：参数：S是存放栈的结构变量是存放栈的结构变量功能：建立一个空栈功能：建立一个空栈SStatus Status InitStack_SqInitStack_Sq( (SqStackSqStack &S) &S) /构造一个空栈构造一个空栈S S S.baseS.base=(=(SElemTypeSElemType * * ) )mallocmalloc(STACK_INIT_SIZE (STACK_INIT_SIZE * * sizeofsizeof( (SElemTypeSElem

6、Type);); /为顺序栈动态分配存储空间为顺序栈动态分配存储空间 if (! S. base) exit(OVERFLOW); if (! S. base) exit(OVERFLOW); /存储分配失败存储分配失败 S.topS.top= =S.baseS.base; ; S.stacksizeS.stacksize=STACK_INIT_SIZE;=STACK_INIT_SIZE; return OK; return OK; /InitStack_SqInitStack_Sq8取栈顶操作取栈顶操作功能：取栈顶元素，并用功能：取栈顶元素，并用e返回返回Status Status GetT

7、op_SqGetTop_Sq( (SqStackSqStack S, S, SelemTypeSelemType &e) &e) / / 若栈不空，则用若栈不空，则用e e返回返回S S的栈顶元素，并返回的栈顶元素，并返回OKOK；/否则返回否则返回ERROR ERROR if ( if (S.topS.top= = =S.baseS.base) return ERROR; ) return ERROR; /若栈为空若栈为空 e = e = * * (S.top-1); (S.top-1); return OK; return OK; /GetTop_SqGetTop_Sq9进栈操作进栈操作P

8、ush功能：元素功能：元素e进栈进栈Status Push(Status Push(SqStackSqStack &S, &S, SElemTypeSElemType e) e) / /将元素将元素e e插入栈成为新的栈顶元素插入栈成为新的栈顶元素, ,要考虑上溢情况要考虑上溢情况 if (if (S.top-S.baseS.top-S.base=S.stacksizeS.stacksize) ) /栈满，追加存储空间栈满，追加存储空间 S.baseS.base= (= (SElemTypeSElemType * * ) )reallocrealloc( (S.baseS.base, , (

9、(S.stacksizeS.stacksize +STACKINCREMENT) +STACKINCREMENT) sizeofsizeof( (ElemTypeElemType); ); if (! S. base) exit(OVERFLOW); if (! S. base) exit(OVERFLOW); /存储分配失败存储分配失败 S.topS.top= =S.base+S.stacksizeS.base+S.stacksize; ; S.stacksizeS.stacksize+=STACKINCREMENT; +=STACKINCREMENT; * *S.topS.top+=e;

10、+=e; /元素元素e e 插入栈顶，修改栈顶指针插入栈顶，修改栈顶指针 return OK; return OK; /Push/Push10出栈操作出栈操作Pop功能：栈顶元素退栈，并用功能：栈顶元素退栈，并用e返回返回Status Pop(Status Pop(SqStackSqStack &S, &S, SElemTypeSElemType &e) &e) / /若栈不空，则删除若栈不空，则删除S S的栈顶元素，用的栈顶元素，用e e 返回其值并返回返回其值并返回OK OK /否则返回否则返回ERRORERROR if ( if (S.topS.top= = = = S.baseS.ba

11、se) return ERROR; ) return ERROR; /栈空，返回栈空，返回ERRORERROR e = e = * * - -S.topS.top; ; /删除栈顶元素，用删除栈顶元素，用e e 返回其值，并修改栈顶指针返回其值，并修改栈顶指针 return OK;return OK; /Pop/Pop11#include template class Stack private: int top; /栈顶指针 Type *elements; /栈元素数组 int maxSize; /栈最大容量public: Stack ( int sz = 10 ); /构造函数 Stack

12、 ( ) delete elements; void Push ( Type & item ); /进栈 Type Pop ( ); /出栈 Type GetTop ( ); /取栈顶 void MakeEmpty ( ) top = -1; /置空栈 int IsEmpty ( ) const return top = -1; int IsFull ( ) const return top = maxSize-1; template Stack :Stack ( int s ) : top (-1), maxSize (s) elements = new TypemaxSize; asser

13、t ( elements != NULL ); /断言template void Stack :Push ( Type & item ) assert ( !IsFull ( ) ); /先决条件断言 elements+top = item; /加入新元素template int stack :Pop ( ) if ( IsEmpty ( ) ) return 0; /栈空不退栈 top-; return 1; /退出栈顶元素 template Type stack:GetTop ( ) assert ( !IsEmpty ( ) ); /先决条件断言 return elementstop;

14、/取出栈顶元素b0 t0 t1 b10 maxSize-1V程序中定义多个栈程序中定义多个栈（1）定义共享栈数据结构）定义共享栈数据结构#define MAX 100 int stackMAX,top1=0,top2=MAX-1;栈1top1top2栈216(2)共享进栈算法共享进栈算法 void push1(int x) if (top1top2) printf(“overflow”); else stacktop1=x;top1+; void push2(int x) if(top1top2) printf(“overflow”); else stacktop2=x;top2-;17(3)

15、共享出栈算法共享出栈算法 int pop1()if top1=0)printf(“underflow”);return(NULL);top1-;return(stacktop1);int pop2()if(top2=MAX-1)printf(“underflow”);return(NULL): top2+;return(stacktop2);18链式栈:栈的链接表示 链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作top1920typedef struct LNode ElemType data; struct LNode *next;* SLink;typ

16、edef struct SLink top; /栈顶指针 int length; /栈中元素个数LStack;21void InitStack ( LStack &S ) / 构造一个空栈 SS.top = NULL; / 设栈顶指针的初值为空S.length = 0; / 空栈中元素个数为0 / InitStackStatus GetTop(LStack S, SelemType &e) / 若栈空则返回ERROR ,否则返回OK if (S-next= =NULL) return ERROR; /若栈为空 e = * (S-next-data); return OK;/GetTop22vo

17、id Push ( LStack &S, ElemType e )/ 在栈顶之上插入元素 e 为新的栈顶元素p = (LNode *)malloc(sizeof(LNode); / 建新的结点if(!p) exit(1);/ 存储分配失败p - data = e;p - next = S.top;/ 链接到原来的栈顶S.top = p; / 移动栈顶指针+S.length; / 栈的长度增1 / Push 23bool Pop ( LStack &S, ElemType &e ) / 若栈不空，则删除S的栈顶元素，用 e 返回其值，/ 并返回 TRUE；否则返回 FALSEif ( !S.to

18、p )return FALSE; else e = S.top - data; / 返回栈顶元素 q = S.top; S.top = S.top - next;/ 修改栈顶指针 -S.length; / 栈的长度减1 delete q; / 释放被删除的结点空间 return TRUE; / Pop template class Stack;template class StackNode friend class Stack;private: Type data; /结点数据 StackNode *link; /结点链指针public: StackNode ( Type d = 0, St

19、ackNode *l = NULL ) : data ( d ), link ( l ) ; template class Stack private: StackNode *top; /栈顶指针public: Stack ( ) : top ( NULL ) Stack ( ); void Push ( const Type & item); /进栈 int Pop ( ); /退栈 Type *GetTop ( ); /读取栈顶元素 void MakeEmpty ( ); /实现与Stack( )同 int IsEmpty ( ) return top = NULL; template S

20、tack :Stack ( ) StackNode *p; while ( top != NULL ) /逐结点回收 p = top; top = top-link; delete p; template void Stack :Push ( const Type &item ) top = new StackNode ( item, top ); /新结点链入*top之前, 并成为新栈顶template int Stack :Pop ( ) if ( IsEmpty ( ) ) return 0; StackNode *p = top; top = top-link; /修改栈顶指针 del

21、ete p; return 1; /释放template Type Stack:GetTop ( ) assert ( !IsEmpty ( ) ); return top-data; 栈的应用举例栈的应用举例数制转换数制转换行编辑程序行编辑程序迷宫求解迷宫求解表达式求值表达式求值28数制转换十进制数转换为八进制数。采用对十进制数除8取余的方法，可得到八进制数的倒序。 N = (N div d)d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序计算顺序输

22、出顺序输出顺序29void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion30行编辑程序行编辑程序在用户输入一行的过程中，允许在用户输入一行的过程中，允许 用户输入用户输入出差错，并在发现有误时可以及时更正。出差错，并在发现有误时可以及时更正。设立一个输入缓冲区，用以接受用户输入设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区的一行字符，然后逐

23、行存入用户数据区; 并假设并假设“#”为退格符，为退格符，“”为退行符。为退行符。假设从终端接受两行字符：假设从终端接受两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);实际有效行为：实际有效行为： while (*s) putchar(*s+);31Void LineEdit()InitStack(s);ch=getchar();while (ch != EOF) /EOF为全文结束符为全文结束符while (ch != EOF & ch != n) switch (ch) case # : Pop(S, ch); break; case : Clear

24、Stack(S); break;/ 重置重置S为空栈为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符从终端接收下一个字符 /while32将从栈底到栈顶的字符传送至调用过程的将从栈底到栈顶的字符传送至调用过程的数据区；数据区；ClearStack(S); / 重置重置S为空栈为空栈if (ch != EOF) ch = getchar(); /whileDestroyStack(s);33v迷宫求解迷宫求解通常用的是通常用的是“穷举求解穷举求解”的方法的方法# #$# #$# $# # # # # #34v迷宫路径算法

25、的基本思想若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。35设定当前位置的初值为入口位置；设定当前位置的初值为入口位置； do 若当前位置可通，若当前位置可通， 则将当前位置插入栈顶；则将当前位置插入栈顶； 若该位置是出口位置，则算法结束；若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的否则切换当前位置的东邻方块为新的 当前位置；当前位置； . 36否则否则 若栈不空且栈顶位置尚有其他方向未被探索，若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为则设定新的当前位置为: 沿顺

26、时针方向旋转沿顺时针方向旋转 找到的栈顶位置的下一相邻块；找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，若栈不空但栈顶位置的四周均不可通，则则删去栈顶位置；删去栈顶位置；/ 从路径中删去该通道块从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空直至找到一个可通的相邻块或出栈至栈空;while (栈不空）；栈不空）；37typedef struct int ord;/序号PosTypeseat;/坐标int di;/方向SElemType;/栈元素Status MazePath (MazeType ma

27、ze, PosType start, PosType end) InitStack(S); curpos=start;/当前位置curstep=1;38do if (Pass(curpos) /可通过且未走过FootPrint(curpos);/记已通过标记e=(curstep, curpos, 1);Push (S, e);if (curpos = end) return (TRUE);curpos = NextPos ( curpos, 1);curstep+;/if39else if (!StackEmpty(S) Pop(S, e);while (e.di=4 & !StackEmpt

28、y(S) MarkPrint(e.seat); Pop(S,e);/记不能通过标记/whileif(e.di4) e.di+; Push(S, e);curpos = NextPos(e.seat, e.di);/if/if/elsewhile (!StackEmpty(S);return (FALSE);/MazePath40限于二元运算符的表达式定义限于二元运算符的表达式定义: 表达式表达式 := (操作数操作数) + (运算符运算符) + (操作数操作数) 操作数操作数 := 简单变量简单变量 | 表达式表达式 简单变量简单变量 : = 标识符标识符 | 无符号整数无符号整数Exp =

29、S1 + OP + S2前缀表示法前缀表示法OP + S1 + S2中缀表示法中缀表示法 S1 + OP + S2后缀表示法后缀表示法 S1 + S2 + OP表达式求值表达式求值41例如例如: Exp = a b + (c d / e) f前缀式前缀式: + a b c / d e f中缀式中缀式: a b + c d / e f后缀式后缀式: a b c d e / f + 表达式标识方法表达式标识方法b-ca/*def*+42rst1rst2rst3rst4rst5rst6rst1rst2rst3rst4rst5rst6n顺序扫描表达式的每一项，根据它的类型做如下相应操作：u若该项是操作

30、数，则将其压栈；u若该项是操作符，则连续从栈中退出两个操作数Y和X，形成运算指令XY，并将计算结果重新压栈。n当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。步步 输入输入类类 型型动动 作作栈内容栈内容1置空栈置空栈空空2A操作数操作数 进栈进栈A3B操作数操作数 进栈进栈AB4C操作数操作数 进栈进栈ABC5D操作数操作数 进栈进栈ABCD6- -操作符操作符 D、C 退栈退栈, 计算计算C- -D, 结果结果 r1 进栈进栈ABr17*操作符操作符 r1、B 退栈退栈, 计算计算B*r1, 结果结果 r2 进栈进栈Ar28+操作符操作符 r2、A 退栈退栈, 计算计算A+

31、r2, 结果结果 r3 进栈进栈r3步步 输入输入类类 型型动动 作作栈内容栈内容9E操作数操作数 进栈进栈r3E10F操作数操作数 进栈进栈r3EF11操作符操作符 F、E 退栈退栈, 计算计算EF, 结果结果 r4 进栈进栈r3r412G操作数操作数 进栈进栈r3r4G13/操作符操作符 G、r4 退栈退栈, 计算计算r4/E, 结果结果 r5 进栈进栈r3r514+ +操作符操作符 r5、r3 退栈退栈, 计算计算r3+r5, 结果结果 r6 进栈进栈r6void Calculator : Run ( ) char ch; double newoperand; while ( cin c

32、h, ch != = ) switch ( ch ) case + : case - - : case * * : case / / : DoOperator ( ch ); break; /计算计算 default : cin.putback ( ch ); /将字符放回输入流将字符放回输入流 cin newoperand; /读操作数读操作数 AddOperand ( newoperand ); 算符间优先级 / ( ) #（）# =c2栈外c1栈内52从中缀式求得后缀式方法从中缀式求得后缀式方法1) 设立暂存设立暂存运算符运算符的的栈栈;2) 设表达式的结束符为设表达式的结束符为“#”,

33、 予设予设运算符栈运算符栈的的栈底为栈底为“#”3) 若若当前字符当前字符是操作数是操作数，则，则直接发送给后缀直接发送给后缀式式;(后缀与前缀式操作数的顺序是相同的后缀与前缀式操作数的顺序是相同的)4) 若若当前当前运算符的运算符的优先数高优先数高于栈顶运算符，于栈顶运算符，则则进栈进栈;5) 否则，退出栈顶运算符发送给后缀式否则，退出栈顶运算符发送给后缀式;6) “(” 对它之前后的运算符对它之前后的运算符起隔离作用起隔离作用，“)”为自左括弧开始的表达式的结束符。为自左括弧开始的表达式的结束符。54void postfix ( expression e ) stack s; char c

34、h, op; s.Push ( # ); cin.Get ( ch ); while ( ! s.IsEmpty( ) & ch != # ) if ( isdigit ( ch ) ) cout ch; cin.Get ( ch ); else if ( isp ( s.GetTop( ) ) icp ( ch ) ) op = s.GetTop ( ); s.Pop( ); cout op; else op = s.GetTop ( ); s.Pop( ); if ( op = ( ) cin.Get ( ch ); 为实现算符优先算法，在这里用了两个工作栈。一个存放算符OPTR，另一个存

35、放数据OPND。算法思想是：（1）首先置数据栈为空栈，表达式起始符“”为算符栈的栈底元素（2）自左向右扫描表达式，读到操作数进OPND栈，读到运算符，则和OPTR栈顶元素比较（栈顶元素为c1，读到的算符为c2);若c1c2,则将c1出栈，并在操作数栈取出两个元素a和b按c1做运算，运算结果进OPND.重复直到表达式求值完毕。56例如：表达式3*(7-2),求值过程如下表：步骤步骤OPTROPTR栈栈OPNDOPND栈栈输入字符输入字符主要操作主要操作13*(7-2)#PUSH(OPND,3)23*(7-2)#PUSH(OPTR,*)3 3(7-2)#PUSH(OPTR,()4 （37-2)#P

36、USH(OPND,7)5 （3 7-2)#PUSH(OPTR,-)6 （ - 3 72)#PUSH(OPND,2)7 （3 7 2)#operate(7,-,2)8 （3 5)#POP(OPTR)消消去括号去括号9 15 #operate(3,*,5)10 15 #PUSH(OPTR,*)57为使两个算符比较方便,给算符设置优先级,如下表,其中c1为栈内元素,c2为栈外元素算算符符栈内优先级栈内优先级栈外优先级栈外优先级* /43+ -21(05)50#-1-158算符比较算法char Precede(char c1,char c2)int c_temp1,c_temp2; switch(c1

37、) case *: case /:c_temp1=4;break;case +: case -:c_temp1=2;break; case (:c_temp1=0;break; case ):c_temp1=5;break; case #:c_temp1=-1;59switch(c2) case *: case /:c_temp2=3;break; case +: case -:c_temp2=1;break; case (:c_temp2=5;break; case ):c_temp2=0;break; case #:c_temp2=-1;if(c_temp1c_temp2) return(

38、c_temp2) return();switch(c1) case *: case /:c_temp1=4;break;case +: case -:c_temp1=2;break; case (:c_temp1=0;break; case ):c_temp1=5;break; case #:c_temp1=-1;60OperandType EvaluateExpression() InitStack (OPTR); Push ( OPTR,#);InitStack (OPND); c=getchar();while (c!=#| GetTop(OPTR)!=#) if(!In(c,OP)Pu

39、sh(OPND,c);c=getchar();elseswitch(Precede(GetTop(OPTR),c)case :/退栈并计算Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a);Push(OPND, Operate(a,theta,b);break;/switch/whilereturn GetTop(OPND);/EvaluateExpression62队列定义:只允许在表的一端进行插入，而在另一端删除元素的线性表。在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为对头(front)。特点：先进先出 (FIFO) a1 ，a2， a3，a

40、n出队列出队列入队列入队列队队头头队队尾尾63链队列：队列的链式表示链队列中，有两个分别指示队头和队尾的指针。链式队列在进队时无队满问题，但有队空问题。data nextfrontreardata nextfrontrear64frontrearx元素元素x入队入队frontrearxy元素元素y入队入队frontrearxy元素元素x出队出队frontrear空队列空队列frontrearNULL空队列空队列65typedef struct QNode /链队列结点的类型定义 QElemType data; /用于存放队列元素 struct QNode *next; /用于存放元素直接后继

41、/结点的地址QNode,*QueuePtr;typedef struct /链队列的表头结点的的类型定义QueuePtr front; /队头指针，指向链表的头结点QueuePtr rear; /队尾指针，指向队尾结点LinkQueue;Status InitQueue_L(LinkQueue &Q) /建一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); /为链队列的头结点分配空间 if (!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK; /InitQueue_LStatus D

42、estroyQueue_L(LinkQueue &Q) /销毁队列Q while(Q.front) Q.rear = Q.front-next; free(Q.front); Q.front = Q.rear; return OK; /DestroyQueue_LStatus DestroyQueue_L(LinkQueue &Q) /销毁队列Q if (!Q.front) return ERROR; / 链队列不存在 while(Q.front-next) / 回收链队列的所有元素结点空间 p=Q.front-next; Q.front-next=p-next; free(p); free(

43、Q.front ); / 回收链队列头结点空间 Q.front=Q.rear=null; return OK;/DestroyQueue_LStatus EnQueue_L(LinkQueue &Q, QElemType ) /在链队列Q队尾，插入新的队尾结点 p=(QueuePtr)malloc(sizeof(QNode); /为新元素e分配结点空间 if (!p) exit (OVERFLOW); /存储分配失败 p-date=e; p-next=NULL; Q.rear-next=p; /修改队尾指针，插入新队尾结点 Q.rear=p; return OK; Status DeQueue

44、_L(LinkQueue &Q, QElemType &e) /若队列不空，则删除Q的队头元素结点，用e返回其值，并返回OK；否则返回ERROR if (Q.front = =Q.rear) return ERROR; /若队列空，返回ERROR p=Q.front-next; / p指向队头元素结点 e=p-data; Q.front-next=p-next; / 修改链队列头结点指针 if(Q.rear= =p) Q.rear=Q.front; / 对于链队列只有一个元素结点的情况,要同时修改队尾指针 free(p); return OK;template class Queue;temp

45、late class QueueNode friend class Queue;private: Type data; /队列结点数据 QueueNode *link; /结点链指针public: QueueNode ( Type d=0, QueueNode *l = NULL ) : data (d), link (l) ; template class Queue private: QueueNode *front, *rear; /队头、队尾指针指针public: Queue ( ) : rear ( NULL ), front ( NULL ) Queue ( ); void EnQ

46、ueue ( const Type & item ); int DeQueue ( ); Type *GetFront ( ); void MakeEmpty ( ); /实现与Queue( )同 int IsEmpty ( ) const return front = NULL; ;template Queue : Queue ( ) /队列的析构函数 QueueNode *p; while ( front != NULL ) /逐个结点释放 p = front; front = front-link; delete p; template void Queue : EnQueue ( co

47、nst Type& item ) /将新元素item插入到队列的队尾 if ( front = NULL ) /创建第一个结点front = rear = new QueueNode ( item, NULL ); else /队列不空, 插入 rear = rear-link = new QueueNode ( item, NULL );template int Queue : DeQueue ( ) if ( IsEmpty ( ) ) return 0; /判队空 QueueNode *p = front; front = front-link; delete p; return 1;t

48、emplate Type *Queue : GetFront ( ) if ( IsEmpty( ) ) return NULL; return & front-data; 循环队列 (Circular Queue)顺序队列队列的顺序存储表示。用一组地址连续的存储单元依次存放从队列头到队列尾的元素，指针front和rear分别指示队头元素和队尾元素的位置。插入新的队尾元素，尾指针增1，rear = rear + 1，删除队头元素，头指针增1， front = front + 1，因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。 队满时再进队将溢出 解决办法

49、：将顺序队列臆造为一个环状的空间，形成循环(环形)队列76队列的进队和出队frontrear空队列空队列frontrearA,B,C, D进队进队A B C DfrontrearA,B出队出队C DfrontrearE,F,G进队进队C D E F GC D E F GfrontrearH进队进队,溢出溢出77循环队列 (Circular Queue)队头、队尾指针加1，可用取模(余数)运算实现。队头指针进1: front = (front+1) %maxsize;队尾指针进1: rear = (rear+1) % maxsize;队列初始化：front = rear = 0;队空条件：fro

50、nt = rear;队满条件：(rear+1) % maxsize = front;01234567循环队列循环队列frontrearMaxsizerontBCDrear一般情况一般情况AC01234567队满队满(错误错误)frontrearDEFGABCH01234567rear空队列空队列frontC01234567队满队满(正确正确)frontrearDEFGABC79#define MAXSIZE 100 / 最大队列长度typedef struct QElemType *base; /初始化时动态分配存储空间的基址 int front; /队头指针，指向队

51、头元素 int rear; /队尾指针，指向队尾元素的下一个位置SqQueue;Status InitQueue_Sq(SqQueue &Q) /构造一个空队列Q Q.base=(ElemType * )malloc (MAXSIZE*sizeof (ElemType); if (!Q.base) exit (OVERFLOW); /存储分配失败 Q.front = Q.rear=0; Return OK; / InitQueue_SqStatus EnQueue_Sq(SqQueue &Q, QElemType e ) /将元素e插入队尾 if (Q.rear+1)%MAXSIZE= =Q.

52、front) return ERROR ; Q.baseQ.rear = e ; / 将元素e插入队尾 Q.rear= (Q.rear+1)%MAXSIZE; / 修改队尾指针 return OK; / EnQueue_SqStatus DeQueue_Sq(SqQueue &Q, QElemType &e ) /删除队头元素，用e返回其值,并返回OK；否 /则返回ERROR if (Q.rear= =Q.front) return ERROR ; e =Q.baseQ.front ; Q.front= (Q.front+1)%MAXSIZE; / 修改队头指针 return OK; / En

53、Queue_Sq#include template class Queue private: int rear, front;/队尾, 队头指针 Type *elements; /队列元素数组 int maxSize; /最大元素个数public: Queue ( ); Queue ( ) delete elements; void EnQueue ( const Type & item); /进队 int DeQueue ( ); /退队 Type *GetFront ( ); /取队头元素 void MakeEmpty ( ) front = rear = 0; int IsEmpty (

54、 ) const return front = rear; int IsFull ( ) const return (rear+1) % maxSize = front; int Length ( ) const return (rear-front+maxSize) % maxSize;template Queue: Queue ( int sz ) : front (0), rear (0), maxSize (sz) elements = new TypemaxSize; assert ( elements != NULL );template void Queue:EnQueue (

55、const Type & item ) assert ( !IsFull ( ) ); elementsrear = item; rear = (rear+1) % MaxSize;template int Queue : DeQueue ( ) if ( IsEmpty ( ) ) return 0; front = ( front+1) % MaxSize; return 1;template Type Queue : GetFront ( ) assert ( !IsEmpty ( ) ); return elementsfront;队列应用举例队列应用举例 打印二项展开式打印二项展开式

56、 (a + b)i 的系数的系数杨辉三角形杨辉三角形 (Pascals triangle) 1 1 i = 1 1 2 1 2 1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 87分析第分析第 i 行元素与第行元素与第 i+1行元素的关系行元素的关系目的是从前一行的数据可以计算下一行的数据目的是从前一行的数据可以计算下一行的数据88从第从第 i 行数据计算并存放第行数据计算并存放第 i+1 行数据行数据89void YANGHUI ( int n ) Queue q; /队列初始化队列初始化 q.MakeEmpty ( ); q

57、.EnQueue (1); q.EnQueue (1);/预放入第一行的两个系数预放入第一行的两个系数 int s = 0;for ( int i=1; i=n; i+ ) /逐行处理逐行处理 cout endl;/换行换行 q.EnQueue (0); for ( int j=1; j=i+2; j+ ) /处理第处理第i行的行的i+2个系数个系数 int t = q.DeQueue ( );/读取系数读取系数 q.EnQueue ( s+t );/计算下一行系数，并进队列计算下一行系数，并进队列 s = t; if ( j != i+2 ) printf(“%d ”, s); 打印一个系数

58、，第打印一个系数，第 i+2个为个为0 90 任任务务编编号号 1 2 3 4 5 优优先先权权 20 0 40 30 10 执执行行顺顺序序 3 1 5 4 2优先级队列 (Priority Queue)优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素例如下表：任务的优先权及执行顺序的关系数字越小，优先权越高，设不存在同优数字越小，优先权越高，设不存在同优先级元素先级元素91#include #include #include const int maxPQSize = 50; /缺省元素个数缺省元素个数template class PQueue pub

59、lic: PQueue ( ); PQueue ( ) delete pqelements; void PQInsert ( const Type & item ); Type PQRemove ( ); 优先队列的类定义优先队列的类定义(C+)92 void makeEmpty ( ) count = -1; int IsEmpty ( ) const return count = -1; int IsFull ( ) const return count = maxPQSize; int Length ( ) const return count; / /优先级队列元优先级队列元素个数素个

60、数private: Type *pqelements;/存放数组（优先级队列数组）存放数组（优先级队列数组） int count; /队列元素计数队列元素计数 93template PQueue:PQueue ( ) : count (- -1) pqelements = new TypemaxPQSize; assert ( pqelements != 0 ); /分配断言分配断言/创建优先级队列创建优先级队列template void PQueue :PQInsert ( const Type & item ) assert ( !IsFull ( ) ); /判队满断言判队满断言 cou