第3章 堆棧與隊列

3.1棧（Stack）基本概念、抽象數(shù)據(jù)類型、順序表示和實現(xiàn)、鏈式表示和實現(xiàn)3.2棧的應用3.4隊列（Queue）

基本概念、抽象數(shù)據(jù)類型、順序隊列、順序循環(huán)隊列、鏈式隊列、隊列的應用第三章棧和隊列11.定義一、堆棧的基本概念與線性表相同，仍為一對一(1:1)關系。用順序棧或鏈棧存儲均可，但以順序棧更常見只能在棧頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則。關鍵是編寫入棧和出棧函數(shù)，具體實現(xiàn)依順序?；蜴湕５拇鎯Y構有別而不同。3.存儲結構4.運算規(guī)則5.實現(xiàn)方式2.邏輯結構限定只能在表的一端進行插入和刪除操作的線性表。特點：后進先出?；静僮饔校航?、判斷棧滿或?？铡⑷霔?、出棧、讀棧頂元素值等等。2在棧滿時還進行入棧運算，必定會產生空

間的溢出7、?！跋乱纭?、?！吧弦纭碑敆？諘r仍進行出棧運算，必定會產生空間的溢出。3棧是僅在表尾進行插入、刪除操作的線性表。表尾(即an端)稱為棧頂/top;表頭(即a1端)稱為棧底/base例如：棧S=(a０,a2,a3,……….,an-1,an

)插入元素到棧頂?shù)牟僮?，稱為入棧。從棧頂刪除最后一個元素的操作，稱為出棧。an稱為棧頂元素a1稱為棧底元素強調：插入和刪除都只能在表的一端（棧頂）進行！注：堆棧可以完成比較復雜的數(shù)據(jù)元素特定序列的轉換任務，但它不能完成任何輸入輸出序列的轉換任務。4圖3.1棧5例1：棧是什么？它與一般線性表有什么不同？堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進行插入和刪除運算。與一般線性表的區(qū)別：僅在于運算規(guī)則不同。一般線性表堆棧邏輯結構：1:1邏輯結構：1:1存儲結構：順序表、鏈表存儲結構：順序棧、鏈棧運算規(guī)則：隨機存取運算規(guī)則：后進先出(LIFO)“進”＝插入=壓入“出”＝刪除=彈出6二、堆棧抽象數(shù)據(jù)類型ADTStack{數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,…,n，n≥0}數(shù)據(jù)關系：R={<ai-1,ai>|ai-1，ai∈D,i=2,3,…,n}基本操作：(1)InitStack(&S)

初始化堆棧S

(2)StackEmpty(S)

堆棧S非空否

(3)Push(&S,e)

入棧

(4)Pop(&S,&e)

出棧

(5)GetTop(S,&e)

取棧頂數(shù)據(jù)元素等 ……}ADTStack7三、堆棧的順序表示和實現(xiàn)1、順序（堆）棧

順序存儲結構的堆棧。2、順序棧的存儲結構

它是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時設指針top指示棧頂元素的當前位置。據(jù)數(shù)組是否可以根據(jù)需要增大，可分為靜態(tài)順序棧和動態(tài)順序?！綮o態(tài)順序棧實現(xiàn)簡單，但不能根據(jù)需要增大棧的存儲空間；◆動態(tài)順序棧可以根據(jù)需要增大棧的存儲空間，但實現(xiàn)稍復雜。8采用動態(tài)一維數(shù)組來存儲棧。所謂動態(tài)，指的是棧的大小可以根據(jù)需要增加。◆用base表示棧底指針，棧底固定不變的；棧頂則隨著進棧和退棧操作而變化。用top(稱為棧頂指針)指示當前棧頂位置。◆用top=base作為?？盏臉擞?，每次top指向棧頂數(shù)組中的下一個存儲位置。◆

結點進棧：首先將數(shù)據(jù)元素保存到棧頂(top所指的當前位置)，然后執(zhí)行top加1，使top指向棧頂?shù)南乱粋€存儲位置;◆結點出棧：首先執(zhí)行top減1，使top指向棧頂元素的存儲位置，然后將棧頂元素取出。3.1.2.1

棧的動態(tài)順序存儲表示9問：順序表和順序棧的操作有何區(qū)別？表頭表尾低地址高地址寫入：S[i]=ai讀出：e=S[i]壓入(PUSH):

S[top++]=an彈出(POP):e=S[--top]低地址高地址S[i]a0a1

aian-1……順序表S……

an以線性表

S=(a0,a1,….,an-2,an-1)為例棧底base棧頂top前提：一定要預設棧頂指針top棧頂topa0a1……an-1順序棧Sai……10棧不存在的條件：base=NULL;棧為空的條件：base=top;棧滿的條件：top-base=MaxSize;a0a1……an-1順序棧Sai……低地址高地址an棧底base棧頂top入?？谠E：堆棧指針top“先壓后加”:S[top++]=an出棧口訣：堆棧指針top“先減后彈”:

e=S[--top]11問：為什么要設計堆棧？它有什么獨特用途？調用函數(shù)或子程序非它莫屬；遞歸運算的有力工具；用于保護現(xiàn)場和恢復現(xiàn)場；簡化了程序設計的問題。下面用3個例子來幫助理解堆棧：12voidtest(int&sum){intx;scanf(“%d”,&x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}斷點地址入棧例1、閱讀下列遞歸過程，說明其功能。輸入x1≠0輸入x5＝0輸入x2輸入x3輸入x4輸出sum＝0輸出sum＝0+x4輸出sum＝x4+x3輸出sum＝x4+x3+x2輸出sum＝x4+x3+x2+x1注意：最先輸入的數(shù)據(jù)

x1

最后才被累加程序功能：對鍵盤輸入數(shù)據(jù)求和，直到輸入0結束13例2、一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現(xiàn)嗎？12345的輸出呢？答：43512不可能實現(xiàn)，主要是其中的12順序不能實現(xiàn)；12345的輸出可以實現(xiàn)，每壓入一數(shù)便立即彈出即可。思考：有無通用的判別原則？14例3、設依次進入一個棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA）、D）可以，B）、C）不行。討論：有無通用的判別原則？有！若輸入序列是…,Pj…Pk…Pi…(Pj<Pk<Pi)，一定不存在這樣的輸出序列…,Pi…Pj…Pk…答：即對于輸入序列1，2，3，不存在輸出序列3，1，2153、順序棧的操作實現(xiàn)1

棧的類型定義#defineSTACK_SIZE100/*棧初始向量大小*/#defineSTACKINCREMENT10/*存儲空間分配增量*/typedefintSElemType;typedefstructsqstack{SElemType*base;/*棧不存在時值為NULL*/SElemType*top;/*棧頂指針*/intstacksize;/*當前已分配空間，以元素為單位*/}SqStack;162棧的初始化

StatusInit_Stack(SqStack&s){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;/*?？諘r棧頂和棧底指針相同*/S.stacksize=STACK_INIT_SIZE;returnOK;}17

3壓棧(元素進棧)Statuspush(SqStack&S,SElemTypee)

{if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));/*棧滿，追加存儲空間*/if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;/*棧頂指針加1，e成為新的棧頂*/returnOK;}184

彈棧(元素出棧)Statuspop(SqStack&S,ElemType&e)/*彈出棧頂元素*/{if(S.top==S.base)returnERROR;

/*棧空，返回失敗標志*/e=*--S.top;returnOK;}

19采用靜態(tài)一維數(shù)組來存儲棧。棧底固定不變的，而棧頂則隨著進棧和退棧操作變化的，◆棧底固定不變的；棧頂則隨著進棧和退棧操作而變化，用一個整型變量top(稱為棧頂指針)來指示當前棧頂位置?！粲胻op=0表示棧空的初始狀態(tài)若棧的數(shù)組有Maxsize個元素，則top=Maxsize時棧滿。

3.1.2.2

棧的靜態(tài)順序存儲表示20基本操作的實現(xiàn)1棧的類型定義#defineMAX_STACK_SIZE100/*棧向量大小*/#typedefintSElemType;typedefstructsqstack{SElemTypestack_array[MAX_STACK_SIZE];inttop;}SqStack;212棧的初始化SqStackInit_Stack(void){SqStackS;

S.top=0;return(S);}223壓棧(元素進棧)Statuspush(SqStack&S,SElemTypee)/*使數(shù)據(jù)元素e進棧成為新的棧頂*/{if(S.top==MAX_STACK_SIZE-1)returnERROR;/*棧滿，返回錯誤標志*/S.top++;/*棧頂指針加1*/S.stack_array[S.top]=e;/*e成為新的棧頂*/returnOK;/*壓棧成功*/}234

彈棧(元素出棧)Statuspop(SqStack&S,SElemType*e)/*彈出棧頂元素*/{if(S.top==0)returnERROR;/*棧空，返回錯誤標志*/*e=S.stack_array[S.top];S.top--;returnOK;}241棧的鏈式表示

棧的鏈式存儲結構稱為鏈棧，是運算受限的單鏈表。其插入和刪除操作只能在表頭位置上進行。因此，鏈棧沒有必要像單鏈表那樣附加頭結點，棧頂指針top就是鏈表的頭指針。圖3-4是棧的鏈式存儲表示形式。3.1.3

棧的鏈式存儲表示空棧top?非空棧top

a4

a3

a1?

a2圖3-4鏈棧存儲形式鏈棧的結點類型說明如下：typedefstructStack_Node{SElemTypedata;structStack_Node*next;}Stack_Node;252

鏈?；静僮鞯膶崿F(xiàn)(1)

棧的初始化Stack_Node*Init_Link_Stack(void){Stack_Node*top;top=(Stack_Node*)malloc(sizeof(Stack_Node));top->next=NULL;return(top);}26(2)壓棧(元素進棧)Statuspush(Stack_Node*top,ElemTypee){Stack_Node*p;p=(Stack_Node*)malloc(sizeof(Stack_Node));if(!p)exit(OVERFLOW);/*申請新結點失敗，返回錯誤標志*/p->data=e;p->next=top->next;top->next=p;/*鉤鏈*/returnOK;}27(3)

彈棧(元素出棧)Statuspop(Stack_Node*top,SElemType*e)/*將棧頂元素出棧*/{Stack_Node*p;SElemTypee;if(top->next==NULL)returnERROR;/*?？眨祷劐e誤標志*/p=top->next;e=p->data;/*取棧頂元素*/top->next=p->next;/*修改棧頂指針*/free(p);returnOK;}28在鏈棧中的頭結點對操作的實現(xiàn)影響不大，棧頂（表頭）操作頻繁，可不設頭結點鏈棧。一般不會出現(xiàn)棧滿情況；除非沒有空間導致malloc分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。采用鏈棧存儲方式的優(yōu)點是，可使多個棧共享空間；當棧中元素個數(shù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。幾點說明:293.2

棧的應用

由于棧具有的“后進先出”的固有特性，因此，棧成為程序設計中常用的工具和數(shù)據(jù)結構。以下是幾個棧應用的例子。303.2.1數(shù)制轉換

十進制整數(shù)N向其它進制數(shù)d(二、八、十六)的轉換是計算機實現(xiàn)計算的基本問題。轉換法則：該轉換法則對應于一個簡單算法原理:n=(ndivd)*d+nmodd其中：div為整除運算,mod為求余運算例如(1348)10=(2504)8，其運算過程如下：nndiv8nmod813481684168210212520231

采用靜態(tài)順序棧方式實現(xiàn)

voidconversion(intn,intd)/*將十進制整數(shù)N轉換為d(2或8)進制數(shù)*/{SqStackS;intk,e;InitStack(S);while(n>0){push(S,n%d);n=n/d;}

/*求出所有的余數(shù)，進棧*/while(!StackEmpty(S)=0)/*棧不空時出棧，輸出*/{pop(S,e);printf(“%1d”,e);}}

323.2.2括號匹配問題在文字處理軟件或編譯程序設計時，常常需要檢查一個字符串或一個表達式中的括號是否相匹配?匹配思想：從左至右掃描一個字符串(或表達式)，則每個右括號將與最近遇到的那個左括號相匹配。則可以在從左至右掃描過程中把所遇到的左括號存放到堆棧中。每當遇到一個右括號時，就將它與棧頂?shù)淖罄ㄌ?如果存在)相匹配，同時從棧頂刪除該左括號。設計思路：用棧暫存左括號.算法思想：設置一個棧，當讀到左括號時，左括號進棧。當讀到右括號時，則從棧中彈出一個元素，與讀到的左括號進行匹配，若匹配成功，繼續(xù)讀入；否則匹配失敗，返回FLASE。33算法描述#defineTRUE0#defineFLASE-1SqStackS;InitStack(S);/*堆棧初始化*/intMatch_Brackets(){charch,x;scanf(“%c”,&ch);while(asc(ch)!=13)34{if((ch==‘(’)||(ch==‘[’))push(S,ch);elseif(ch==‘]’&&!StackEmpty(S)){pop(S,x);if(x!=‘[’){printf(“’[’括號不匹配”);returnFLASE;}}elseif(ch==‘)’&&!StackEmpty(S)){pop(S,x);if(x!=‘(’){printf(“’(’括號不匹配”);returnFLASE;}}}35if(S.top!=0){printf(“括號數(shù)量不匹配！”);returnFLASE;}elsereturnTRUE;}363.3棧與遞歸調用的實現(xiàn)棧的另一個重要應用是在程序設計語言中實現(xiàn)遞歸調用。

遞歸調用：一個函數(shù)(或過程)直接或間接地調用自己本身，簡稱遞歸(Recursive)。遞歸是程序設計中的一個強有力的工具。因為遞歸函數(shù)結構清晰，程序易讀，正確性很容易得到證明。為了使遞歸調用不至于無終止地進行下去，實際上有效的遞歸調用函數(shù)(或過程)應包括兩部分：遞推規(guī)則(方法)，終止條件。例如：求n!37Fact(n)=1當n=0時終止條件n*fact(n-1)當n>0時遞推規(guī)則

為保證遞歸調用正確執(zhí)行，系統(tǒng)設立一個“遞歸工作棧”，作為整個遞歸調用過程期間使用的數(shù)據(jù)存儲區(qū)。每一層遞歸包含的信息如：參數(shù)、局部變量、上一層的返回地址構成一個“工作記錄”。每進入一層遞歸，就產生一個新的工作記錄壓入棧頂；每退出一層遞歸，就從棧頂彈出一個工作記錄。38

從被調函數(shù)返回調用函數(shù)的一般步驟：(1)若棧為空，則執(zhí)行正常返回。⑵從棧頂彈出一個工作記錄。⑶將“工作記錄”中的參數(shù)值、局部變量值賦給相應的變量；讀取返回地址。⑷將函數(shù)值賦給相應的變量。(5)轉移到返回地址。391

隊列的基本概念

隊列(Queue)：也是運算受限的線性表。是一種先進先出(FirstInFirstOut，簡稱FIFO)的線性表。只允許在表的一端進行插入，而在另一端進行刪除。

隊首(front)

：允許進行刪除的一端稱為隊首。

隊尾(rear)

：允許進行插入的一端稱為隊尾。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進入隊列的成員總是先離開隊列。

3.4

隊列3.4.1

隊列及其基本概念40

隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,…,an之后，a1是隊首元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,…,an，即隊列的修改是依先進先出的原則進行的，如圖3-5所示。a1,a2,…,an出隊入隊隊尾隊首圖3-5隊列示意圖2

隊列的抽象數(shù)據(jù)類型定義ADTQueue{數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}41數(shù)據(jù)關系：R={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}約定a1端為隊首，an端為隊尾。基本操作：InitQueue()：構造一個空隊列；QueueEmpty()：若隊列為空，則返回true，否則返回flase；??EnQueue(&Q,e)：向隊尾插入元素e；DeQueue(&Q,&e)：刪除隊首元素,并用e返回其值；}ADTQueue423.4.2隊列的順序表示和實現(xiàn)

利用一組連續(xù)的存儲單元(一維數(shù)組)

依次存放從隊首到隊尾的各個元素，稱為順序隊列。對于隊列，和順序棧相類似，也有動態(tài)和靜態(tài)之分。本部分介紹的是靜態(tài)順序隊列，其類型定義如下：#defineMAX_QUEUE_SIZE100typedefstructqueue{QElemTypeQueue_array[MAX_QUEUE_SIZE];intfront;intrear;}SqQueue;433.4.2.1隊列的順序存儲結構

設立一個隊首指針front，一個隊尾指針rear

，分別指向隊首和隊尾元素。

◆初始化：front=rear=0。

◆入隊：將新元素插入rear所指的位置，然后rear加1。

◆出隊：刪去front所指的元素，然后加1并返回被刪元素。

◆隊列為空：front=rear?！絷牆M：rear=MAX_QUEUE_SIZE-1或front=rear。44

在非空隊列里，隊首指針始終指向隊頭元素，而隊尾指針始終指向隊尾元素的下一位置。

順序隊列中存在“假溢出”現(xiàn)象。因為在入隊和出隊操作中，頭、尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。因此，盡管隊列中實際元素個數(shù)可能遠遠小于數(shù)組大小，但可能由于尾指針巳超出向量空間的上界而不能做入隊操作。該現(xiàn)象稱為假溢出。如圖3-6所示是數(shù)組大小為5的順序隊列中隊首、隊尾指針和隊列中元素的變化情況。45

(a)空隊列Q.frontQ.rear入隊3個元素a3a2a1Q.frontQ.rear(c)出隊3個元素Q.frontQ.rear(d)入隊2個元素a5a4Q.frontQ.rear圖3-6隊列示意圖46順序隊列的“假溢出”問題(1)假溢出

順序隊列因多次入隊和出隊操作后出現(xiàn)的有存儲空間但不能進行入隊操作的溢出。(2)如何解決順序隊列的假溢出問題？可采取四種方法：采用循環(huán)隊列；按最大可能的進隊操作次數(shù)設置順序隊列的最大元素個數(shù)；修改出隊算法，使每次出隊列后都把隊列中剩余數(shù)據(jù)元素向隊頭方向移動一個位置；修改入隊算法，增加判斷條件，當假溢出時，把隊列中的數(shù)據(jù)元素向對頭移動，然后方完成入隊操作。47順序循環(huán)隊列的表示和實現(xiàn)１、順序循環(huán)隊列的基本原理

把順序隊列所使用的存儲空間構造成一個邏輯上首尾相連的循環(huán)隊列。當rear和front達到MaxQueueSize-1后，再前進一個位置就自動到０。

順序隊列:a3a2a1front(隊首)rear(隊尾)0123..N-1a3a2a10123N-1rearfront循環(huán)隊列:482、順序循環(huán)隊列的隊空和隊滿判斷問題新問題：在循環(huán)隊列中，空隊特征是front=rear；隊滿時也會有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；

判隊滿：count>0&&rear==front

判隊空：count==0②加設標志位，出隊時置０,入隊時置１,則可識別當前front=rear屬于何種情況

判隊滿：tag==1&&rear==front判隊空：tag==0&&rear==front③少用一個存儲單元

判隊滿：

front=＝(rear+1)%MaxQueueSize

判隊空：

rear==front49J5J0J1J2J3J4例：一循環(huán)隊列如下圖所示，若先刪除4個元素，接著再插入4個元素，請問隊頭和隊尾指針分別指向哪個位置?J2J3 J1J4

J5解：由圖可知，隊頭和隊尾指針的初態(tài)分別為front=1和rear=0。刪除4個元素后f=5；再插入4個元素后，r=(0+4)%6=4rear=0rear=0front=1front=5rear=450◆循環(huán)隊列為空：front=rear。◆循環(huán)隊列滿：(rear+1)%MAX_QUEUE_SIZE

=front。循環(huán)隊列的基本操作1循環(huán)隊列的初始化SqQueueInit_CirQueue(void){SqQueueQ;Q.front=Q.rear=0;return(Q);}51

2入隊操作StatusInsert_CirQueue(SqQueueQ,ElemTypee)/*將數(shù)據(jù)元素e插入到循環(huán)隊列Q的隊尾*/{if((Q.rear+1)%MAX_QUEUE_SIZE==Q.front)returnERROR;/*隊滿，返回錯誤標志*/Q.Queue_array[Q.rear]=e;/*元素e入隊*/Q.rear=(Q.rear+1)%MAX_QUEUE_SIZE;/*隊尾指針向前移動*/returnOK;/*入隊成功*/}52

3出隊操作StatusDelete_CirQueue(SqQueueQ,ElemType*x

)/*將循環(huán)隊列Q的隊首元素出隊*/{if(Q.front+1==Q.rear)returnERROR;/*隊空，返回錯誤標志*/*x=Q.Queue_array[Q.front];/*取隊首元素*/Q.front=(Q.front+1)%MAX_QUEUE_SIZE;

/*隊首指針向前移動*/returnOK;}53下次講課內容鏈式隊列(重點入隊、出隊算法）隊列的應用（編程序判斷一個字符序列是否是回文。熟練應用入棧、出棧和入隊列、出隊列等算法）優(yōu)先級隊列的概念和入隊算法本章復習541隊列的鏈式存儲表示

隊列的鏈式存儲結構簡稱為鏈隊列，它是限制僅在表頭進行刪除操作和表尾進行插入操作的單鏈表。需要兩類不同的結點：數(shù)據(jù)元素結點，隊列的隊首指針和隊尾指針的結點，如圖3-8所示。3.4.2.2

隊列的鏈式表示和實現(xiàn)數(shù)據(jù)元素結點類型定義：typedefstructQnode{QElemTypedata;structQnode*next;}QNode;數(shù)據(jù)元素結點data指針結點front

rear圖3-8鏈隊列結點示意圖55指針結點類型定義：typedefstructlink_queue{QNode*front,*rear;}Link_Queue;2鏈隊運算及指針變化

鏈隊的操作實際上是單鏈表的操作，只不過是刪除在表頭進行，插入在表尾進行。插入、刪除時分別修改不同的指針。鏈隊運算及指針變化如圖3-9所示。56圖3-9隊列操作及指針變化(a)空隊列front

rear∧(b)x入隊

x∧front

rear(c)y再入隊

y∧front

rear

x(d)x出隊

y∧

xfront

rear57

3鏈隊列的基本操作⑴

鏈隊列的初始化LinkQueue*Init_LinkQueue(void){LinkQueue*Q;QNode*p;p=(QNode*)malloc(sizeof(QNode));/*開辟頭結點*/p->next=NULL;Q=(LinkQueue*)malloc(sizeof(LinkQueue));

/*開辟鏈隊的指針結點*/Q.front=Q.rear=p;return(Q);}58

⑵

鏈隊列的入隊操作

在已知隊列的隊尾插入一個元素e，即修改隊尾指針(Q.rear)。StatusInsert_CirQueue(LinkQueue*Q,ElemTypee)/*將數(shù)據(jù)元素e插入到鏈隊列Q的隊尾*/{p=(QNode*)malloc(sizeof(QNode));if(!p)returnERROR;/*申請新結點失敗，返回錯誤標志*/p->data=e;p->next=NULL;/*形成新結點*/Q.rear->next=p;Q.rear=p;/*新結點插入到隊尾*/returnOK;}59

⑶鏈隊列的出隊操作StatusDelete_LinkQueue(LinkQueue*Q,ElemType*x)

{QNode*p;if(Q.front==Q.rear)returnERROR;/*隊空*/p=Q.front->next;/*取隊首結點*/*x=p->data;Q.front->next=p->next;/*修改隊首指針*/if(p==Q.rear)Q.rear=Q.front;

/*當隊列只有一個結點時應防止丟失隊尾指針*/free(p);returnOK;}60

⑷

鏈隊列的撤消voidDestroy_LinkQueue(LinkQueue*Q)

/*將鏈隊列Q的隊首元素出隊*/{while(Q.front!=NULL){Q.rear=Q.front->next;/*令尾指針指向隊列的第一個結點*/free(Q.front);/*每次釋放一個結點*//*第一次是頭結點，以后是元素結點*/Q.ront=Q.rear;}}61隊列的應用例：編程序判斷一個字符序列是否是回文。

編程思想：

設字符數(shù)組str中存放了要判斷的字符串。把字符數(shù)組中的字符逐個分別存入隊列和堆棧，然后逐個出隊列和退棧并比較出隊列的字符和退棧的字符是否相等，若全部相等則該字符序列是回文，否則就不是回文。62#include<stdio.h>#include<string.h>#defineMaxQueueSize100#defineMaxStackSize100typedefcharDataType; #include"SeqCQueue.h"#include"SeqStack.h“voidHuiWen(charstr[]){ SeqCQueuemyQueue; SeqStackmyStack; charx,y; inti,length;63length=strlen(str);QueueInitiate(&myQueue);StackInitiate(&myStack);for(i=0