第3章 棧和隊列

第三章棧和隊列3.1棧3.2隊列3.3迷宮問題

棧和隊列是操作位置受限的線性表。即限定插入和刪除只能在表的“端點”進行的線性表。

線性表棧隊列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1

Delete(L,i)Delete(S,n)Delete(Q,

1)1≤i≤n棧和隊列是兩種常用的數(shù)據(jù)類型。3.1.1棧的定義3.1.2棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn)3.1.3棧的鏈式存儲結(jié)構(gòu)及其基本運算實現(xiàn)3.1.4棧的應(yīng)用例子

棧是一種只能在一端進行插入或刪除操作的線性表。棧結(jié)構(gòu)具有后進先出（LIFO）的特性。

表中允許進行插入、刪除操作的一端稱為棧頂。由一個稱為棧頂指針的位置指示器指示。

表的另一端稱為棧底。

當棧中沒有數(shù)據(jù)元素時，稱為空棧。

棧的插入操作通常稱為進棧或入棧，棧的刪除操作通常稱為退?；虺鰲！?.1.1棧的定義43210(a)空棧(b)元素a入棧db(c)元素b、c、d入棧ca(d)元素d出棧(1)初始化棧InitStack(&s)：(2)銷毀棧ClearStack(&s)

：(3)求棧的長度StackLength(s)：(4)判斷棧是否為空StackEmpty(s)：

棧的幾種基本運算:構(gòu)造一個空棧s。釋放棧s占用的存儲空間。返回棧s中的元素個數(shù)。若棧s為空，則返回真；否則返回假。(5)入棧Push(&S,e)：將元素e插入到棧s中作為棧頂元素。a1a2ane

……(6)出棧Pop(&s,&e)：從棧s中退出棧頂元素，并將其值賦給e。a1a2anan-1

……(7)取棧頂元素GetTop(s,&e)：返回當前的棧頂元素，并將其值賦給e。(8)顯示棧中元素DispStack(s)：從棧頂?shù)綏５醉樞蝻@示棧中所有元素。a1a2an……3.1.2棧的順序存儲結(jié)構(gòu)及基本運算實現(xiàn)

假設(shè)棧的元素個數(shù)最大不超過正整數(shù)MaxSize,所有的元素都具有同一數(shù)據(jù)類型ElemType，則可用下列方式來定義棧類型SqStack：

typedef

struct

{

ElemType

elem[MaxSize]；

inttop； /*棧指針*/}SqStack；

例3.1設(shè)有4個元素a、b、c、d進棧，給出它們所有可能的出棧次序。

所有可能的出棧次序如下:

abcd

abdc

acbd

acdb

adcb

bacd

badc

bcad

bcda

bdca

cbad

cbda

cdba

dcba

例3.2設(shè)一個棧的輸入序列為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均在棧中，按照入棧順序，在棧中順序應(yīng)為D,C,B,A，出棧的順序只能是D,C,B,A。所以本題答案為D。

例3.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。

例3.4設(shè)n個元素進棧序列是1,2,3,…，其輸出序列是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。在順序棧中實現(xiàn)棧的基本運算算法:(1)初始化棧initStack(&s)

建立一個新的空棧s,實際上是將棧頂指針指向-1即可。

voidInitStack(SqStack*&s){

s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;

}

(2)銷毀棧ClearStack(&s)

釋放棧s占用的存儲空間。

voidClearStack(SqStack*&s){

free(s)；

}(3)求棧的長度StackLength(s)

返回棧s中的元素個數(shù)，即棧指針加1的結(jié)果。

int

StackLength(SqStack*s){

return(s->top+1);}(4)判斷棧是否為空StackEmpty(s)

棧S為空的條件是s->top==-1。

int

StackEmpty(SqStack*s){

return(s->top==-1);}(5)入棧Push(&s，e)

在棧不滿的條件下，先將棧指針增1，然后在該位置上插入元素e。

int

Push(SqStack*&s，ElemTypee){ if(s->top==MaxSize-1)return0; /*棧滿的情況，即棧上溢出*/

s->top++; s->elem[s->top]=e;

return1;

}(6)出棧Pop(&s,&e)

在棧不為空的條件下，先將棧頂元素賦給e，然后將棧指針減1。int

Pop(SqStack*&s，ElemType&e){ if(s->top==-1)return0; /*棧為空的情況，即棧下溢出*/

e=s->elem[s->top]; s->top--;

return1;}(7)取棧頂元素GetTop(s)

在棧不為空的條件下，將棧頂元素賦給e。int

GetTop(SqStack*s，ElemType&e){

if(s->top==-1)return0; /*棧為空的情況,即棧下溢出*/ e=s->elem[s->top];

return1;}(8)顯示棧中元素DispStack(s)

從棧頂?shù)綏５醉樞蝻@示棧中所有元素。voidDispStack(SqStack*s){

inti; for(i=s->top;i>=0;i--)

printf("%c",s->elem[i]);

printf("\n");}

1.3棧的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn)

采用鏈式存儲的棧稱為鏈棧，用單鏈表實現(xiàn)。

鏈棧的優(yōu)點：

按規(guī)定棧的所有操作都是在單鏈表的表頭。進行的頭結(jié)點為*lhead的鏈棧，第一個數(shù)據(jù)結(jié)點是棧頂結(jié)點，最后一個結(jié)點是棧底結(jié)點。將序列{a1，a2，…，an}中的元素依次插入空鏈棧中。不存在棧滿上溢。棧頂指針鏈棧∧a1an注意:鏈棧中指針的方向an-1∧空鏈棧將序列{a1，a2，…，an}中的元素依次插入空棧鏈棧中數(shù)據(jù)結(jié)點的類型LiStack定義如下:typedef

struct

linknode{

ElemTypedata; /*數(shù)據(jù)域*/

struct

linknode*next; /*指針域*/}LiStack;

在鏈棧中，棧的基本運算算法如下:(1)初始化棧initStack(&s)

建立一個空棧s。實際上是創(chuàng)建鏈棧的頭結(jié)點，并將其next域置為NULL。對應(yīng)算法如下:voidInitStack(LiStack*&s){

s=(LiStack*)malloc(sizeof(LiStack)); s->next=NULL;}(2)銷毀棧ClearStack(&s)

釋放棧s占用的全部存儲空間。voidClearStack(LiStack*&s){ LiStack*p=s->next;

while(p!=NULL) { free(s); s=p; p=p->next; }}(3)求棧的長度StackLength(s)

從第一個數(shù)據(jù)結(jié)點開始掃描單鏈表，用i記錄訪問的數(shù)據(jù)結(jié)點個數(shù)，最后返回i值。int

StackLength(LiStack*s){

inti=0;

LiStack*p;

p=s->next; while(p!=NULL) {i++;p=p->next;}

return(i);}(4)判斷棧是否為空StackEmpty(s)

棧S為空的條件是s->next==NULL，即單鏈表中沒有數(shù)據(jù)結(jié)點。int

StackEmpty(LiStack*s){

return(s->next==NULL);}(5)入棧Push(&s，e)

將新數(shù)據(jù)結(jié)點插入到頭結(jié)點之后。voidPush(LiStack*&s，ElemTypee){

LiStack*p;

p=(LiStack*)malloc(sizeof(LiStack)); p->data=e; p->next=s->next; /*插入*p結(jié)點作為第一個數(shù)據(jù)結(jié)點*/

s->next=p;}(6)出棧Pop(&s,&e)

在棧不為空的條件下，將頭結(jié)點后繼數(shù)據(jù)結(jié)點的數(shù)據(jù)域賦給e，然后將其刪除。

int

Pop(LiStack*&s,ElemType&e){ LiStack*p; if(s->next==NULL)return0;/*?？盏那闆r*/

p=s->next; /*p指向第一個數(shù)據(jù)結(jié)點*/ e=p->data; s->next=p->next;

free(p); return1;}(7)取棧頂元素GetTop(s)

在棧不為空的條件下，將頭結(jié)點后繼數(shù)據(jù)結(jié)點的數(shù)據(jù)域賦給e。int

GetTop(LiStack*s，ElemType&e){

if(s->next==NULL)return0; /*?？盏那闆r*/ e=s->next->data; return1;}(8)顯示棧中元素DispStack(s)

從第一個數(shù)據(jù)結(jié)點開始掃描單鏈表，并輸出當前訪問結(jié)點的數(shù)據(jù)域值。對應(yīng)算法如下:voidDispStack(LiStack*s){ LiStack*p=s->next;

while(p!=NULL) { printf("%c",p->data); p=p->next; }

printf("\n");}

例

假設(shè)表達式中允許包含三種括號：圓括號、方括號和大括號。編寫一個算法判斷表達式中的括號是否正確配對。1.1.4棧的應(yīng)用例子

由于棧結(jié)構(gòu)具有的后進先出的固有特性，使棧成為程序設(shè)計中常用的工具。如：行編輯程序、數(shù)制轉(zhuǎn)換、表達式的括號配對及求值。1.括弧配對和表達式求值intcorrect(charexp[],intn){ charst[MaxSize];

inttop=-1,i=0,tag=1; while(i<n&&tag) {if(exp[i]=='('||exp[i]=='['||exp[i]=='{')

{

top++;

st[top]=exp[i];}/*遇到‘(’、‘[’或‘{’，則將其入棧*/

if(exp[i]==‘)’)

if(st[top]=='(')top--;elsetag=0;

if(exp[i]==‘]’)

if(st[top]=='[')top--;elsetag=0;

if(exp[i]==‘}’)

if(st[top]=='{')top--;elsetag=0;i++;}/*遇到‘)，若棧頂是‘(’，則繼續(xù)處理，否則以不配對返回*//*遇到‘]’，若棧頂是‘[’，則繼續(xù)處理，否則以不配對返回*//*遇到‘}’，若棧頂是‘{’，則繼續(xù)處理，否則以不配對返回*/

if(top>-1) tag=0;/*若棧不空，則不配對*/

return(tag);}問題：用戶輸入一個包含“+”、“-”、“*”、“/”、正整數(shù)和圓括號的合法數(shù)學表達式，計算該表達式的運算結(jié)果。在程序語言中，運算符位于兩個操作數(shù)中間的表達式稱為中綴表達式。如：1+2*3。

表達式的三種標識方法：設(shè)

Exp=S1+OP+S2則稱

OP+S1+S2

為前綴表示法

S1+OP+S2

為中綴表示法

S1+S2+OP

為后綴表示法

例如:Exp=ab+(cd/e)f

前綴式:+ab

c/def

中綴式:ab+cd/ef

后綴式:ab

cde/f+經(jīng)過分析，表達式的三種表示法有以下特點:1）操作數(shù)之間的相對次序不變;2）運算符的相對次序不同;3）中綴式丟失了括弧信息，致使運算的次序不確定;4)前綴式的運算規(guī)則為:

連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一個最小表達式；5)后綴式的運算規(guī)則為：

運算符在式中出現(xiàn)的順序恰為表達式的運算順序；每個運算符和在它之前出現(xiàn)

且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達式;如何從后綴式求值？先找運算符，再找操作數(shù)例如：

abcde/f+abd/ec-d/e(c-d/e)f

對中綴表達式的運算一般遵循“先乘除，后加減，從左到右計算，先括號內(nèi)，后括號外”的規(guī)則。因此，中綴表達式不僅要依賴運算符優(yōu)先級，而且還要處理括號。

所謂后綴表達式，就是運算符在操作數(shù)的后面,如1+2*3的后綴表達式為123*+。在后綴表達式中已考慮了運算符的優(yōu)先級，沒有括號，只有操作數(shù)和運算符。如何從原表達式求得后綴式？

每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優(yōu)先級高的運算符領(lǐng)先于優(yōu)先級低的運算符。

分析“原表達式”和“后綴式”中的運算符:原表達式:a+bcd/ef

后綴式:abc+de/f

所以，算術(shù)表達式求值過程是：STEP1：先將算術(shù)表達式轉(zhuǎn)換成后綴表達式，STEP2：然后對該后綴表達式求值。STEP1:從原表達式求得后綴式的步驟為：1)設(shè)立暫存運算符的棧;2)依次取出原表達式中的字符;3)若當前字符是操作數(shù)，則直接發(fā)送給后綴式;4)若當前運算符的優(yōu)先數(shù)高于棧頂運算符，則進棧;5)否則，退出棧頂運算符發(fā)送給后綴式;

其中，“(”

對它之前后的運算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的表達式的結(jié)束符。6)轉(zhuǎn)2）;

表達式存放在字符型數(shù)組str中，其后綴表達式存放在字符型數(shù)組exp中，在將算術(shù)表達式轉(zhuǎn)換成后綴表達式的過程中用一個字符型數(shù)組op作為棧。

STEP1:從原表達式求得后綴式算法中用到的變量有：a+bcd/ef`\0`strexp+abcdefop.datachchchchchch-/依次從鍵盤輸入表達式中的字符ch，對于每一個ch：

(1)若ch為數(shù)字，將后續(xù)的所有數(shù)字均依次存入數(shù)組exp中，并以字符’\0’標志數(shù)值串結(jié)束。

(2)若ch為左括弧“(”，則將此括弧入棧op。

(3)若ch為右括弧“)”，則將棧op中左括弧“(”以前的字符依次刪除并存入數(shù)組exp中，然后將左括弧“(”刪除。算法描述：(4)若ch為“+”或“-”，則將當前棧op中“(”以前的所有字符(運算符)依次刪除并存入數(shù)組exp中，然后將ch入棧op中。(5)若ch為“*”或“/”，則將當前棧op中的棧頂端連續(xù)的“*”或“/”刪除并依次存入數(shù)組exp中，然后將ch入棧op中。(6)若字符串str掃描完畢，則將棧op中的所有運算符依次刪除并存入數(shù)組exp中，然后再將ch存入數(shù)組exp中，最后可得到表達式的后綴表示在數(shù)組exp中。

voidtrans(charstr[],charexp[])/*將算術(shù)表達式str轉(zhuǎn)換成后綴表達式exp*/{ struct{char

data[MaxSize];/*存放運算符*/

inttop; /*棧指針*/ }op; /*定義運算符棧*/ charch;

inti=0,t=0;/*t作為exp的下標,i作為str的下標*/

op.top=-1;

ch=str[i];i++;while(ch!='\0') /*str表達式未掃描完時循環(huán)*/{switch(ch) {case'(': /*判定為左括號*/

op.top++;op.data[op.top]=ch;break;

case')': /*判定為右括號*/ while(op.data[op.top]!='(') {exp[t]=op.data[op.top];

op.top--;t++;}

op.top--;break;

case'+':

case'-': /*判定為加或減號*/ while(op.top!=-1&&op.data[op.top]!='(') {exp[t]=op.data[op.top];

op.top--;t++;}

op.top++;op.data[op.top]=ch;break;

case'*':case'/':/*判定為'*'或'/'號*/ while(op.data[op.top]=='*'||op.data[op.top]=='/') {exp[t]=op.data[op.top];

op.top--;t++;}

op.top++;op.data[op.top]=ch;break;

case'':break; /*過濾掉空格*/

default:

while(ch>='0'&&ch<='9')/*判定為數(shù)字*/ {exp[t]=ch;t++;

ch=str[i];i++;} i--;exp[t]='#';t++;/*用#標識一個數(shù)值串結(jié)束*/}/*switch結(jié)束*/

ch=str[i];i++;}/*while結(jié)束*/while(op.top!=-1)

/*此時str掃描完畢,棧不空時循環(huán)*/{exp[t]=op.data[op.top];t++;op.top--;}

exp[t]='\0';/*給exp表達式添加結(jié)束標識*/}STEP2：對后綴表達式求值過程是：從左到右讀入后綴表達式，若讀入的是一個操作數(shù)，就將它入數(shù)值棧；若讀入的是一個運算符op，就從數(shù)值棧中連續(xù)出棧兩個元素(兩個操作數(shù))，假設(shè)為x和y，計算xopy之值，并將計算結(jié)果入數(shù)值棧；對整個后綴表達式讀入結(jié)束時，棧頂元素就是計算結(jié)果。exp56#20#-4#2#+/st.data5620-3642+6/6

對后綴表達式求值的算法中要用到一個數(shù)值棧st，該算法實現(xiàn)過程如下:

后綴表達式存放在字符型數(shù)組exp中，從頭開始依次掃描這個后綴表達式，當遇到運算數(shù)時，就把它插入到數(shù)值棧st中；當遇到運算符時，就執(zhí)行兩次退棧，運算并把結(jié)果入棧st。重復上述過程，直至后綴表達式exp掃描完畢，此時數(shù)值棧st中棧頂?shù)臄?shù)值即為表達式的值。STEP2：算法中用到的變量有：floatcompvalue(charexp[]) /*計算后綴表達式的值*/{ struct

{floatdata[MaxSize]; /*存放數(shù)值*/

inttop; /*棧指針*/ }st; /*定義數(shù)值棧*/floatd;charch;intt=0; /*t作為exp的下標*/

st.top=-1;ch=exp[t];t++;while(ch!='\0') /*exp字符串未掃描完時循環(huán)*/{switch(ch){case'+':st.data[st.top-1]=st.data[st.top-1]+st.data[st.top];

st.top--;break;

case'-':st.data[st.top-1]=st.data[st.top-1]-st.data[st.top];

st.top--;break;

case'*':st.data[st.top-1]=st.data[st.top-1]*st.data[st.top];

st.top--;break;case‘/’:if(st.data[st.top]!=0) st.data[st.top-1]=st.data[st.top-1]/st.data[st.top];else{printf("\n\t除零錯誤!\n"); exit(0); /*異常退出*/ }

st.top--;break;

default:

d=0;/*將數(shù)字字符轉(zhuǎn)換成數(shù)值存放到d中*/while(ch>='0'&&ch<='9')/*為數(shù)字字符*/ {d=10*d+ch-'0';

ch=exp[t];t++;}

st.top++;st.data[st.top]=d;}/*case結(jié)束*/

ch=exp[t];t++;}/*while結(jié)束*/returnst.data[st.top];}3.2隊列3.2.1隊列的定義

返回3.2.2隊列的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn)3.2.3隊列的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn)

隊列簡稱隊，也是一種運算受限的線性表，其限制僅允許在表的一端進行插入，而在表的另一端進行刪除。隊列結(jié)構(gòu)具有先進先出（FIFO）的特性。插入元素的一端稱做隊尾(rear)，進行刪除的一端稱做隊首(front)。向隊列中插入新元素稱為進隊或入隊，新元素進隊后就成為新的隊尾元素；從隊列中刪除元素稱為出隊或離隊，元素出隊后，其后繼元素就成為隊首元素。

3.2.1隊列的定義

a1a2an……a1a2ane……a1a2an……

取隊首元素在隊尾插入新元素刪除隊首元素3.2.2隊列的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn)

假設(shè)隊列的元素個數(shù)最大不超過整數(shù)MaxSize，所有的元素都具有同一數(shù)據(jù)類型ElemType，則順序隊列類型SqQueue定義如下：typedef

struct

{ ElemType

elem[MaxSize]；

intfront，rear；/*隊首和隊尾指針*/}SqQueue；

循環(huán)隊列首尾相連，當隊首front指針滿足front==MaxSize-1后，再前進一個位置就自動到0，可利用除法取余的運算(％)來實現(xiàn)：隊首指針進1：front=(front+1)％MaxSize

隊尾指針進1：rear=(rear+1)％MaxSize

循環(huán)隊列的除頭指針和隊尾指針初始化時都置0：front=rear=0。在入隊元素和出隊元素時，指針都按逆時針方向進1。fra012345678dbefcihgrrrrrrrrfffjkl初始化空隊列時：front=rear=0;空隊列時：front==rear隊列滿：(rear+1)%M==front

隊列的初始狀態(tài)，有front==rear成立，該條件可以作為隊列空的條件。當rear==MaxSize-1時，隊列為空，但仍滿足該條件。這時入隊時出現(xiàn)“假上溢出”，這種溢出并不是真正的溢出，在elem數(shù)組中存在可以存放元素的空位置。為了能夠充分地使用數(shù)組中的存儲空間，把數(shù)組的前端和后端連接起來，形成一個環(huán)形的順序表，即把存儲隊列元素的表從邏輯上看成一個環(huán)，稱為循環(huán)隊列。

在入隊時少用一個數(shù)據(jù)元素空間，以隊尾指針加1等于隊首指針判斷隊滿，即隊滿條件為：

(q->rear+1)%MaxSize==q->front隊空條件仍為：

q->rear==q->front

在循環(huán)隊列中，實現(xiàn)隊列的基本運算算法：(1)初始化隊列InitQueue(&q)

構(gòu)造一個空隊列q。將front和rear指針均設(shè)置成初始狀態(tài)即0值。對應(yīng)算法如下:voidInitQueue(SqQueue*&q){ q=(SqQueue*)malloc(sizeof(SqQueue)); q->front=q->rear=0;}(2)銷毀隊列ClearQueue(&q)

釋放隊列q占用的存儲空間。voidClearQueue(SqQueue*&q){

free(q);}(3)判斷隊列是否為空QueueEmpty(q)

若隊列q滿足q->front==q->rear條件，則返回1；否則返回0。對應(yīng)算法如下：int

QueueEmpty(SqQueue*q){

return(q->front==q->rear);}(4)入隊列enQueue(q,e)

在隊列不滿的條件下，先將隊尾指針rear循環(huán)增1，然后將元素添加到該位置。int

enQueue(SqQueue*&q，ElemTypee){if((q->rear+1)%MaxSize==q->front)/*隊滿*/ return0; q->rear=(q->rear+1)%MaxSize; q->elem[q->rear]=e; return1;}(5)出隊列deQueue(q,e)

在隊列q不為空的條件下,將隊首指針front循環(huán)增1，并將該位置的元素值賦給e。int

deQueue(SqQueue*&q,ElemType&e){if(q->front==q->rear)/*隊空*/ return0; q->front=(q->front+1)%MaxSize; e=q->elem[q->front]; return1;}

鏈隊中數(shù)據(jù)結(jié)點類型QNode定義如下:

struct

qnode{

ElemTypedata;

struct

qnode*next;}QNode;3.2.3隊列的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn)鏈式隊列的結(jié)構(gòu)體類型LiQueue定義如下:typedef

struct{

QNode*front;

QNode*rear;}LiQueue;a1∧an…Q.frontQ.rear∧空隊列∧a2∧元素a1，a2，…，an依次入隊出隊一次frontrearq(b)入隊3個元素ab

^cfrontrear(c)出隊1個元素b∧cq∧∧frontrearq(a)鏈隊初態(tài)在鏈隊存儲中，隊列的基本運算算法如下:(1)初始化隊列InitQueue(q)

構(gòu)造一個空隊列，即創(chuàng)建一個頭結(jié)點。

voidInitQueue(LiQueue*&q){

q=(LiQueue*)malloc(sizeof(LiQueue));q->front=q->rear=(QNode*)malloc(sizeof(QNode));

q->rear->next=NULL;}(2)銷毀隊列ClearQueue(q)

釋放隊列占用的存儲空間,包括鏈隊結(jié)點和所有數(shù)據(jù)結(jié)點的存儲空間。voidClearQueue(LiQueue*&q){ QNode*p=q->front，*r; if(p!=NULL) /*釋放數(shù)據(jù)結(jié)點占用空間*/ { r=p->next; while(r!=NULL) {free(p); p=r;r=p->next;}

free(p); }

free(q); /*釋放鏈隊結(jié)點占用空間*/}(3)判斷隊列是否為空QueueEmpty(q)

若鏈隊頭結(jié)點的next域值為NULL，表示隊列為空，返回1；否則返回0。

int

QueueEmpty(LiQueue*q){

if(q->front->next==NULL) return1; else return0;}(4)入隊列enQueue(q,e)

創(chuàng)建data域為e的數(shù)據(jù)結(jié)點*s。若原隊列為空，則將鏈隊結(jié)點的兩個域均指向*s結(jié)點，否則，將*s鏈到單鏈表的末尾，并讓鏈隊結(jié)點的rear域指向它。對應(yīng)算法：voidenQueue(LiQueue*&q,ElemTypee){ QNode*s;

s=(QNode*)malloc(sizeof(QNode)); s->data=e; s->next=NULL;

q->rear->next=s;

}(5)出隊列deQueue(q,e)

若原隊列不為空，則將第一個數(shù)據(jù)結(jié)點的data域值賦給e，并刪除之。若出隊之前隊列中只有一個結(jié)點，則需將鏈隊結(jié)點的兩個域均置為NULL，表示隊列已為空。int

deQueue(LiQueue*&q,ElemType&e){ QNode*t;

if(q->rear==q->front)return0;/*隊列為空*/ e=q->front->data;t=q->front;

q->front==q->front->next;

free(t);

return1;}求迷宮問題就是求出從入口到出口的路徑。3.3.1用棧求解迷宮問題3.3.2用隊列求解迷宮問題

3.3

迷宮問題——棧和隊列的應(yīng)用求解迷宮問題就是求出從迷宮入口到出口的路徑。１．應(yīng)用棧求解迷宮問題２．應(yīng)用隊列求解迷宮問題

在求解時，從入口出發(fā)，沿某一方向向前試探，若能走通，則繼續(xù)往前走；否則沿原路退回到上一步，換一個方向再繼續(xù)試探，直至所有方向上的可能通路都試探完為止。為了保證從任何位置都能沿原路退回(稱為回溯)，需要用一個后進先出的棧來保存從入口到當前位置的路徑。對于圖中的每個方塊，用白色表示通道，用黑色表示墻。1．應(yīng)用棧求解迷宮問題01234567890123456789(i-1,j)方位0(i,j+1)方位2(i+1,j)方位1(i,j-1)方位3所求路徑必須是簡單路徑，即在求得的路徑上不能重復出現(xiàn)同一通道塊。(i，j)111122222321331340

240

141151162263253012345678901234567892-125-1迷宮路徑算法的基本思想如下：若當前位置“不可通”，則后退，換方向繼續(xù)探索；若四周“均無通路”，則將當前位置從路徑中刪除出去，退回到上一步。若當前位置“可通”，則納入路徑，繼續(xù)前進；設(shè)定當前位置的初值為入口位置；

do｛若當前位置可通，則｛將當前位置插入棧頂；若該位置是出口位置，則算法結(jié)束；否則切換當前位置的東鄰方塊為新的當前位置；｝否則{

｝｝while(棧不空）；求迷宮中的路徑算法步驟:從當前棧頂元素開始試探；若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當前位置為：沿順時針方向旋轉(zhuǎn)，能找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測試新的棧頂位置，

直至找到一個可通的相鄰塊或出棧至?？?；｝若棧空，則表明迷宮沒有通路。

設(shè)置一個數(shù)組mg，其中每個元素表示一個迷宮中方塊的狀態(tài)，為0時表示對應(yīng)方塊是通道，為1時表示對應(yīng)方塊為墻。圖中對應(yīng)的迷宮數(shù)組mg如下:

intmg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}};

為了便于回溯，對于可走的方塊都要進棧，并試探它的下一可走的方位，將這個可走的方位保存到棧中，為此，將棧定義為：

struct

{inti; /*當前方塊的行號*/

intj; /*當前方塊的列號*/

int

di; /*di是下一可走方位的方位號*/}Stack[MaxSize]; /*定義棧*/

inttop=-1; /*初始化棧指針*/voidmgpath() /*路徑為：(1，1)(M-2，N-2)*/{int

i,j,di,find,k;top++;/*初始方塊進棧*/

Stack[top].i=1;Stack[top].j=1;

Stack[top].di=-1;mg[1][1]=-1;/*（1，1）為路徑中的一塊*/while(top>-1) /*棧不空時循環(huán)*/{i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;

if(i==M-2&&j==N-2) /*找到了出口,輸出路徑*/ {printf("迷宮路徑如下:\n"); for(k=0;k<=top;k++) {printf("\t(%d,%d)",Stack[k].i,Stack[k].j); if((k+1)%5==0)printf("\n");}

printf("\n"); return; } find=0;

while(di<4&&find==0)/*找下一個可走方塊*/ {di++;

switch(di) {

case0:i=Stack[top].i-1;j=Stack[top].j;break;

case1:i=Stack[top].i;j=Stack[top].j+1;break;

case2:i=Stack[top].i+1;j=Stack[top].j;break;

case3:i=Stack[top].i,j=Stack[top].j-1;break; } if(mg[i][j]==0)find=1; } if(find==1)/*找到了下一個可走方塊*/ {Stack[top].di=di;/*修改原棧頂元素的di值*/ top++;/*下一個可走方塊進棧*/

Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;

mg[i][j]=-1; /*避免重復走到該方塊*/ } else /*沒有路徑可走，則退棧*/ {mg[Stack[top].i][Stack[top].j]=0;/*讓該位置變?yōu)槠渌窂娇勺叻綁K*/ top--; } }

printf("沒有可走路徑!\n");}完整算法使用一個隊列Qu記錄走過的方塊：

struct

{ int

i,j;/*方塊的位置*/

intpre;/*本路徑中上一方塊在Qu中的下標*/}Qu[MaxSize];

intfront=-1,rear=-1; /*隊首指針和隊尾指針*/

使用的隊列Qu不是循環(huán)隊列，因此在出隊時，不會將出隊元素真正從隊列中刪除，因為要利用它輸出路徑。2．應(yīng)用隊列求解迷宮問題01234567