第三章-棧和隊(duì)列

1、棧 隊(duì)列 遞歸,第三章棧和隊(duì)列,1,棧 ( Stack ),定義:是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表。允許插入和刪除的一端稱(chēng)為棧頂(top)，另一端稱(chēng)為棧底(bottom)特點(diǎn)：后進(jìn)先出 (LIFO),,a1,,,,,,,top,bottom,,,an....,進(jìn)棧,出棧,2,棧的抽象數(shù)據(jù)類(lèi)型定義為： ADT Stack {　數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet, i=1,2,...,

2、n, n≥0 }　數(shù)據(jù)關(guān)系：R1＝{ | ai-1 , ai ∈D, i=2,...,n }　　　　　約定an端為棧頂,a1端為棧底。 基本操作： …….} ADT Stack,棧的抽象數(shù)據(jù)類(lèi)型 （C語(yǔ)言）,template class Stack {public: Stack ( int sz = 10 ); //構(gòu)造函數(shù) void Push ( Type&am

3、p; item); //進(jìn)棧 Type Pop ( ); //出棧 Type GetTop ( ); //取棧頂元素 void MakeEmpty ( ); //置空棧 int IsEmpty ( ) const; //判棧空否 int IsFull ( ) const;

4、 //判棧滿(mǎn)否},棧的抽象數(shù)據(jù)類(lèi)型 （C++）,棧的表示和實(shí)現(xiàn),順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)，利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針top指向棧頂元素在順序棧中的下一個(gè)位置，base為棧底指針，指向棧底的位置。,5,6,順序棧的定義及存儲(chǔ)表示,#define STACK_INIT_SIZE 100//棧存儲(chǔ)空間的初始分配量#define STACKINCREMENT 10// 棧存儲(chǔ)空

5、間的分配增量typedef struct{SElemType *base;//?？臻g基址稱(chēng)為棧底指針，指向棧底位置SElemType *top //棧頂指針,約定棧頂指針指向棧頂元素的 //下（后面）一個(gè)位置； int stacksize; //當(dāng)前分配的棧空間大小 //（以sizeof(SElemType)為單位）}SqSta

6、ck;// SqStack:：結(jié)構(gòu)類(lèi)型名,7,初始化操作參數(shù)：S是存放棧的結(jié)構(gòu)變量功能：建立一個(gè)空棧S,Status InitStack_Sq(SqStack &S) { //構(gòu)造一個(gè)空棧S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType)); //為順序棧動(dòng)態(tài)分配存儲(chǔ)空間 if (! S. b

7、ase) exit(OVERFLOW); //存儲(chǔ)分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack_Sq,8,取棧頂操作功能：取棧頂元素，并用e返回,Status GetTop_Sq(SqStack S, SelemType &e) { // 若棧不空

8、，則用e返回S的棧頂元素，并返回OK；//否則返回ERROR if (S.top= =S.base) return ERROR; //若棧為空 e = * (S.top-1); return OK;}//GetTop_Sq,9,進(jìn)棧操作Push功能：元素e進(jìn)棧,Status Push(SqStack &S, SElemType e) { //將元素e插入棧成為新的

9、棧頂元素,要考慮上溢情況 if (S.top-S.base>=S.stacksize) {//棧滿(mǎn)，追加存儲(chǔ)空間 S.base= (SElemType * )realloc(S.base, (S.stacksize +STACKINCREMENT) sizeof(ElemType)); if (! S. base) exit(OVERFLOW

10、); //存儲(chǔ)分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; //元素e 插入棧頂，修改棧頂指針 return OK; }//Push,10,出棧操作Pop功能：棧頂元素退棧，并用e返回,Status Pop(SqStack &S, SElemTyp

11、e &e) { //若棧不空，則刪除S的棧頂元素，用e 返回其值并返回OK //否則返回ERROR if (S.top= = S.base) return ERROR; //?？眨祷谽RROR e = * --S.top; //刪除棧頂元素，用e 返回其值，并修改棧頂指針 return OK;} //Pop,11,#include template c

12、lass Stack {private: int top; //棧頂指針 Type *elements; //棧元素?cái)?shù)組 int maxSize; //棧最大容量public: Stack ( int sz = 10 ); //構(gòu)造函數(shù) ~Stack ( ) { delet

13、e [ ] elements; } void Push ( Type & item ); //進(jìn)棧,棧的數(shù)組表示 — 順序棧（C++）,Type Pop ( ); //出棧 Type GetTop ( ); //取棧頂 void MakeEmpty ( ) { top = -1; } //置空棧 in

14、t IsEmpty ( ) const { return top == -1; } int IsFull ( ) const { return top == maxSize-1; }}template Stack ::Stack ( int s ) : top (-1), maxSize (s) { elements = new Type[maxSize]; assert (

15、elements != NULL ); //斷言},template void Stack ::Push ( Type & item ) { assert ( !IsFull ( ) ); //先決條件斷言 elements[++top] = item; //加入新元素}template int stack ::Pop ( ) { if ( IsEmpty

16、 ( ) ) return 0; //?？詹煌藯?top--; return 1; //退出棧頂元素},template Type stack::GetTop ( ) { assert ( !IsEmpty ( ) ); //先決條件斷言 return elements[top]; //取出棧頂元素}雙棧共享一個(gè)棧空間,b[0]

17、 t[0] t[1] b[1],,,,,,,,0 maxSize-1,V,,,程序中定義多個(gè)棧,（1）定義共享?xiàng)?shù)據(jù)結(jié)構(gòu)#define MAX 100 int stack[MAX],top1=0,top2=MAX

18、-1;,,,,,,,,,,,,,,,,,,,,棧1,,top1,,top2,,棧2,16,(2)共享進(jìn)棧算法 void push1(int x) {if (top1>top2) printf(“overflow”); else {stack[top1]=x;top1++;}} void push2(int x) {if(top1>top2) printf(“overflow”

19、); else {stack[top2]=x;top2--;},17,(3)共享出棧算法 int pop1(){if top1==0){printf(“underflow”);return(NULL);}top1--;return(stack[top1]);}int pop2(){if(top2==MAX-1){printf(“underflow”);return(NULL):} top2++;return(s

20、tack[top2]);},18,鏈?zhǔn)綏?棧的鏈接表示,鏈?zhǔn)綏o(wú)棧滿(mǎn)問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作,top,,,,,,,,,,,,,,,,,,,19,20,鏈?zhǔn)綏?(LinkedStack)中結(jié)點(diǎn)的定義,鏈?zhǔn)綏?(LinkedStack)結(jié)構(gòu)定義,typedef struct LNode{ ElemType data; struct LNode *next;}*

21、SLink;,typedef struct{ SLink top; //棧頂指針 int length; //棧中元素個(gè)數(shù)}LStack;,21,鏈?zhǔn)綏?(LinkedStack)的基本操作,void InitStack ( LStack &S )　{ 　　// 構(gòu)造一個(gè)空棧 S　　S.top = NULL; 　// 設(shè)棧頂指針的初值為空　　S.length = 0; 　　// 空棧中

22、元素個(gè)數(shù)為0　} // InitStackStatus GetTop(LStack S, SelemType &e) { // 若?？談t返回ERROR ,否則返回OK if (S->next= =NULL) return ERROR; //若棧為空 e = * (S->next->data); return OK;}//GetTop,22,鏈?zhǔn)綏?

23、(LinkedStack)的基本操作,void Push ( LStack &S, ElemType e )　{　　// 在棧頂之上插入元素 e 為新的棧頂元素　　p = (LNode *)malloc(sizeof(LNode); 　　 // 建新的結(jié)點(diǎn)　　if(!p) exit(1);　　// 存儲(chǔ)分配失敗　　p -> data =

24、e;　　p -> next = S.top;　// 鏈接到原來(lái)的棧頂　　S.top = p; 　　　　// 移動(dòng)棧頂指針　　++S.length;　　　　 // 棧的長(zhǎng)度增1　} // Push,23,鏈?zhǔn)綏?(LinkedStack)的基本操作,bool Pop ( LStack &S, ElemType &e )　{ 　　// 若棧不空，則刪除S的棧頂元素，用 e 返回其值，　　// 并返回 TR

25、UE；否則返回 FALSE　　if ( !S.top )　　　return FALSE; 　　else 　　{　　 e = S.top -> data; 　　// 返回棧頂元素 　　 q = S.top; 　　 S.top = S.top -> next;　// 修改棧頂指針 　　 --S.length; 　　　　　 // 棧的長(zhǎng)度減1 　　 delete q;　　　　　 　// 釋放被刪除的結(jié)點(diǎn)空間　　

26、 return TRUE;　　}　} // Pop,template class Stack;template class StackNode {friend class Stack;private: Type data; //結(jié)點(diǎn)數(shù)據(jù) StackNode *link; //結(jié)點(diǎn)鏈指針public: StackNode ( Typ

27、e d = 0, StackNode *l = NULL ) : data ( d ), link ( l ) { }};,鏈?zhǔn)綏?(LinkedStack)類(lèi)的定義（C++）,template class Stack {private: StackNode *top; //棧頂指針public: Stack ( ) : top ( NULL ) { } ~Stack ( )

28、; void Push ( const Type & item); //進(jìn)棧 int Pop ( ); //退棧 Type *GetTop ( ); //讀取棧頂元素 void MakeEmpty ( ); //實(shí)現(xiàn)與~Stack( )同 int IsEmpty ( ) { return

29、top == NULL; }},template Stack ::~Stack ( ) { StackNode *p; while ( top != NULL ) //逐結(jié)點(diǎn)回收 { p = top; top = top->link; delete p; }}template void Stack ::Push ( const Type &item ) {

30、top = new StackNode ( item, top ); //新結(jié)點(diǎn)鏈入*top之前, 并成為新棧頂},template int Stack ::Pop ( ) { if ( IsEmpty ( ) ) return 0; StackNode *p = top; top = top->link; //修改棧頂指針 delete p; return

31、 1; //釋放}template Type Stack::GetTop ( ) { assert ( !IsEmpty ( ) ); return top->data;},,棧的應(yīng)用舉例,數(shù)制轉(zhuǎn)換行編輯程序迷宮求解表達(dá)式求值,28,數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)。采用對(duì)十進(jìn)制數(shù)除8取余的方法，可得到八進(jìn)制數(shù)的倒序。 N = (N div d)×d + N mod

32、 d 例如：（1348)10 = (2504)8 ，其運(yùn)算過(guò)程如下：N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,29,void conversion () { InitStack(S); scan

33、f ("%d",N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); }} // conversion,30,行編輯程序在用戶(hù)輸入一行的過(guò)程中，允許 用戶(hù)輸入出差錯(cuò)，并在

34、發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶(hù)輸入的一行字符，然后逐行存入用戶(hù)數(shù)據(jù)區(qū); 并假設(shè)“#”為退格符，“@”為退行符。假設(shè)從終端接受兩行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++);實(shí)際有效行為： while (*s) putchar(*s++);,31,Void LineEdit(){InitStac

35、k(s);ch=getchar();while (ch != EOF) { //EOF為全文結(jié)束符while (ch != EOF && ch != '\n') { switch (ch) {case '#' : Pop(S, ch); break; case '@': ClearStack(S); break;

36、// 重置S為空棧 default : Push(S, ch); break; } ch = getchar(); // 從終端接收下一個(gè)字符 }//while,32,將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；ClearStack(S); // 重置S為空棧if (ch != EOF) ch = getchar();} //while

37、DestroyStack(s);},33,迷宮求解通常用的是“窮舉求解”的方法,34,迷宮路徑算法的基本思想,若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。,,,35,設(shè)定當(dāng)前位置的初值為入口位置； do｛ 若當(dāng)前位置可通， 則｛將當(dāng)前位置插入棧頂； 若該位置是出口位置，則算法結(jié)束；

38、 否則切換當(dāng)前位置的東鄰方塊為新的 當(dāng)前位置； ｝………..,36,否則 {若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針?lè)较蛐D(zhuǎn) 找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；// 從路徑中刪去該通道塊 若棧不空，則重新測(cè)試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？?/p>

39、;｝｝｝while (棧不空）；,37,typedef struct {intord;//序號(hào)PosTypeseat;//坐標(biāo)intdi;//方向}SElemType;//棧元素Status MazePath (MazeType maze, PosType start, PosType end) {InitStack(S); curpos=start;//當(dāng)前位置curstep=1;

40、,38,do {if (Pass(curpos)) {//可通過(guò)且未走過(guò)FootPrint(curpos);//記已通過(guò)標(biāo)記e=(curstep, curpos, 1);Push (S, e);if (curpos == end) return (TRUE);curpos = NextPos ( curpos, 1);curstep++;}//if,39,else {if

41、 (!StackEmpty(S)) {Pop(S, e);while (e.di==4 && !StackEmpty(S)) {MarkPrint(e.seat); Pop(S,e);//記不能通過(guò)標(biāo)記}//whileif(e.di<4) {e.di++; Push(S, e);curpos = NextPos(e.seat, e.di);

42、}//if}//if}//else}while (!StackEmpty(S));return (FALSE);}//MazePath,40,限于二元運(yùn)算符的表達(dá)式定義: 表達(dá)式 ::= (操作數(shù)) + (運(yùn)算符) + (操作數(shù)) 操作數(shù) ::= 簡(jiǎn)單變量 | 表達(dá)式 簡(jiǎn)單變量 :: = 標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù)Exp = S1 + OP + S2前綴表示法OP + S1 + S2中綴表示

43、法 S1 + OP + S2后綴表示法 S1 + S2 + OP,表達(dá)式求值,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 ? +,表達(dá)式標(biāo)識(shí)方法,42,表達(dá)式的中綴表示,a + b * (

44、 c - d ) - e ^ f / g表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋簝?yōu)先級(jí)高的先計(jì)算；優(yōu)先級(jí)相同的自左向右計(jì)算；當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開(kāi)始計(jì)算。,,rst1,,rst2,,rst3,,rst4,,rst5,,rst6,C++中操作符的優(yōu)先級(jí),優(yōu)先級(jí) 操作符 1 單目-、！ 2 *、/、% 3 +、-

45、 4 、>= 5 ==、!= 6 && 7 ||,一般表達(dá)式的操作符有4種類(lèi)型： 算術(shù)操作符 如雙目操作符（+、-、*、/ 和%）以及單目操作符（-）。 關(guān)系操作符 包括=、>。這些操作符主要用于比較。 邏輯操作符 如與(&&)、

46、或(||)、非(!)。 括號(hào)‘(’和‘)’ 它們的作用是改變運(yùn)算順序。,后綴表示法計(jì)算表達(dá)式的值,從左向右順序地掃描表達(dá)式，并用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。在后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)的優(yōu)先次序，括號(hào)在后綴表達(dá)式中不出現(xiàn)。計(jì)算例 a b c d - * + e f ^ g / -,,rst1,,rst2,,rst3,,rst4,,rst5,,rst6,通過(guò)后綴表示計(jì)算表達(dá)式值的過(guò)程,順序掃描表達(dá)式的每一項(xiàng)，

47、根據(jù)它的類(lèi)型做如下相應(yīng)操作：若該項(xiàng)是操作數(shù)，則將其壓棧；若該項(xiàng)是操作符，則連續(xù)從棧中退出兩個(gè)操作數(shù)Y和X，形成運(yùn)算指令XY，并將計(jì)算結(jié)果重新壓棧。當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計(jì)算結(jié)果。,void Calculator :: Run ( ) { char ch; double newoperand; while ( cin >> ch, ch != ‘=’ ) {

48、 switch ( ch ) { case ‘+’ : case ‘-’ : case ‘*’ : case ‘/’ : DoOperator ( ch ); break; //計(jì)算 default : cin.putback ( ch ); //將字符放回輸入流 ci

49、n >> newoperand; //讀操作數(shù) AddOperand ( newoperand ); } }},利用棧將中綴表示轉(zhuǎn)換為后綴表示,使用?？蓪⒈磉_(dá)式的中綴表示轉(zhuǎn)換成它的前綴表示和后綴表示。為了實(shí)現(xiàn)這種轉(zhuǎn)換，需要考慮各操作符的優(yōu)先級(jí)。,算符間優(yōu)先級(jí),,c2棧外,c1棧內(nèi),52,各個(gè)算術(shù)操作符的優(yōu)先級(jí),isp叫做棧內(nèi)(in stack prior

50、ity)優(yōu)先數(shù)icp叫做棧外(in coming priority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對(duì)或棧底的“#”號(hào)與輸入流最后的“#”號(hào)配對(duì)時(shí)。,從中綴式求得后綴式方法,設(shè)立暫存運(yùn)算符的棧;設(shè)表達(dá)式的結(jié)束符為“#”, 予設(shè)運(yùn)算符棧的棧底為“#”若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式;(后綴與前綴式操作數(shù)的順序是相同的)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;否則，退出棧頂運(yùn)算符發(fā)送給后綴式;“(” 對(duì)它

51、之前后的運(yùn)算符起隔離作用，“)”為自左括弧開(kāi)始的表達(dá)式的結(jié)束符。,54,void postfix ( expression e ) { stack s; char ch, op; s.Push ( ‘#’ ); cin.Get ( ch ); while ( ! s.IsEmpty( ) && ch != ‘#' ) if ( isdigit ( ch ) )

52、 { cout icp ( ch ) ) { op = s.GetTop ( ); s.Pop( ); cout << op; } else { op = s.GetTop ( ); s.Pop( ); if ( op == ‘(’ ) cin.Get ( ch ); } }

53、},為實(shí)現(xiàn)算符優(yōu)先算法，在這里用了兩個(gè)工作棧。一個(gè)存放算符OPTR，另一個(gè)存放數(shù)據(jù)OPND。算法思想是：（1）首先置數(shù)據(jù)棧為空棧，表達(dá)式起始符“?！睘樗惴麠５臈５自兀?）自左向右掃描表達(dá)式，讀到操作數(shù)進(jìn)OPND棧，讀到運(yùn)算符，則和OPTR棧頂元素比較（棧頂元素為c1，讀到的算符為c2);若c1c2,則將c1出棧，并在操作數(shù)棧取出兩個(gè)元素a和b按c1做運(yùn)算，運(yùn)算結(jié)果進(jìn)OPND.重復(fù)直到表達(dá)式求值完畢。,56,中綴算術(shù)表達(dá)式求值

54、,例如：表達(dá)式3*(7-2),求值過(guò)程如下表：,57,為使兩個(gè)算符比較方便,給算符設(shè)置優(yōu)先級(jí),如下表,其中c1為棧內(nèi)元素,c2為棧外元素,58,算符比較算法,char Precede(char c1,char c2){int c_temp1,c_temp2; switch(c1){ case ‘*’: case ‘/’:c_temp1=4;break;case ‘+’: case ‘-’:c_temp1=2;b

55、reak; case ‘(’:c_temp1=0;break; case ‘)’:c_temp1=5;break; case ‘#’:c_temp1=-1;},59,switch(c2){ case ‘*’: case ‘/’:c_temp2=3;break; case ‘+’: case ‘-’:c_temp2=1;break; case ‘(’:c_temp2=5;break;

56、 case ‘)’:c_temp2=0;break; case ‘#’:c_temp2=-1;}if(c_temp1c_temp2) return(‘>‘);},switch(c1){ case ‘*’: case ‘/’:c_temp1=4;break;case ‘+’: case ‘-’:c_temp1=2;break; case ‘(’:c_temp1=0;break; case

57、‘)’:c_temp1=5;break; case ‘#’:c_temp1=-1;},60,OperandType EvaluateExpression() {InitStack (OPTR); Push ( OPTR,’#’);InitStack (OPND); c=getchar();while (c!=‘#’|| GetTop(OPTR)!=‘#’) {if(!In(c,OP)){Push(OPND,c);

58、c=getchar();}elseswitch(Precede(GetTop(OPTR),c){case ‘<‘://棧頂元素優(yōu)先權(quán)低Push(OPTR,c); c=getchar();break;,算符優(yōu)先算法求表達(dá)式值,61,case ‘=‘://脫括號(hào)Pop(OPTR,x); c=getchar();break;case ‘>’://退棧并計(jì)算

59、Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a);Push(OPND, Operate(a,theta,b));break;}//switch}//whilereturn GetTop(OPND);}//EvaluateExpression,62,隊(duì)列,定義:只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線(xiàn)性表。在隊(duì)列中，允許插入的一端叫隊(duì)尾（r

60、ear），允許刪除的一端稱(chēng)為對(duì)頭(front)。特點(diǎn)：先進(jìn)先出 (FIFO),a1 ，a2， a3，…，an,,,出隊(duì)列,入隊(duì)列,,,隊(duì)頭,隊(duì)尾,63,鏈隊(duì)列：隊(duì)列的鏈?zhǔn)奖硎?鏈隊(duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿(mǎn)問(wèn)題，但有隊(duì)空問(wèn)題。,64,空隊(duì)列,65,typedef struct QNode{ //鏈隊(duì)列結(jié)點(diǎn)的類(lèi)型定義 QElemType data; //用于存放隊(duì)列元素 st

61、ruct QNode *next; //用于存放元素直接后繼 //結(jié)點(diǎn)的地址}QNode,*QueuePtr;typedef struct{ //鏈隊(duì)列的表頭結(jié)點(diǎn)的的類(lèi)型定義QueuePtr front; //隊(duì)頭指針，指向鏈表的頭結(jié)點(diǎn)QueuePtr rear; //隊(duì)尾指針，指向隊(duì)尾結(jié)點(diǎn)}LinkQueue;,鏈?zhǔn)疥?duì)列的表示及基本操作

62、(C語(yǔ)言),Status InitQueue_L(LinkQueue &Q) {//建一個(gè)空隊(duì)列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); //為鏈隊(duì)列的頭結(jié)點(diǎn)分配空間 if (!Q.front) exit(OVERFLOW); Q.front->next=NULL; return OK;} //InitQueue_LSta

63、tus DestroyQueue_L(LinkQueue &Q) {//銷(xiāo)毀隊(duì)列Q while(Q.front) { Q.rear = Q.front->next; free(Q.front); Q.front = Q.rear; } return OK;} //DestroyQueue_L,鏈?zhǔn)疥?duì)列的表示及基本操作(C語(yǔ)言

64、),Status DestroyQueue_L(LinkQueue &Q) { //銷(xiāo)毀隊(duì)列Q if (!Q.front) return ERROR; // 鏈隊(duì)列不存在 while(Q.front->next) { // 回收鏈隊(duì)列的所有元素結(jié)點(diǎn)空間 p=Q.front->next;

65、 Q.front->next=p->next; free(p); } free(Q.front ); // 回收鏈隊(duì)列頭結(jié)點(diǎn)空間 Q.front=Q.rear=null; return OK;}//DestroyQueue_L,鏈?zhǔn)疥?duì)列的表示及基本操作(C語(yǔ)言),S

66、tatus EnQueue_L(LinkQueue &Q, QElemType ) { //在鏈隊(duì)列Q隊(duì)尾，插入新的隊(duì)尾結(jié)點(diǎn) p=(QueuePtr)malloc(sizeof(QNode)); //為新元素e分配結(jié)點(diǎn)空間 if (!p) exit (OVERFLOW); //存儲(chǔ)分配失敗 p->date=e; p->next=NULL; Q.rear-

67、>next=p; //修改隊(duì)尾指針，插入新隊(duì)尾結(jié)點(diǎn) Q.rear=p; return OK; },鏈?zhǔn)疥?duì)列的表示及基本操作(C語(yǔ)言),Status DeQueue_L(LinkQueue &Q, QElemType &e) { //若隊(duì)列不空，則刪除Q的隊(duì)頭元素結(jié)點(diǎn)，用e返回其值，并返回OK；否則返回ERROR if (

68、Q.front = =Q.rear) return ERROR; //若隊(duì)列空，返回ERROR p=Q.front->next; // p指向隊(duì)頭元素結(jié)點(diǎn) e=p->data; Q.front->next=p->next; // 修改鏈隊(duì)列頭結(jié)點(diǎn)指針 if(Q.rear= =p) Q.rear=

69、Q.front; // 對(duì)于鏈隊(duì)列只有一個(gè)元素結(jié)點(diǎn)的情況,要同時(shí)修改隊(duì)尾指針 free(p); return OK;},鏈?zhǔn)疥?duì)列的表示及基本操作(C語(yǔ)言),template class Queue;template class QueueNode {friend class Queue;private: Type data; //隊(duì)列結(jié)點(diǎn)數(shù)據(jù)