1、第3章 棧和隊列棧的定義及其運算棧的順序存儲結構 棧的鏈式存儲結構 棧的應用舉例 隊列的定義及運算 隊列的順序存儲結構隊列的鏈式存儲結構棧和隊列的應用實例13.1 棧(Stack)棧: 只允許在表的一端進行插入和刪除的線性表允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)進棧插入: 將一個數據元素存放在棧頂出棧刪除：將棧頂元素取出并刪除特點:后進先出(LIFO )2出棧anan-1a2a1棧底 bottom棧頂 top進棧棧(Stack)3棧的根本操作 InitStack(S) 初始化操作,建立一個空棧S StackEmpty(S) 判空棧操作,假設S為空棧,返回一個真值

2、Push(S，x) 進棧操作,在棧S頂插入一個元素XPop(S,*y) 出棧操作,假設棧S不空, 刪除棧頂元素并保存在*y中。GetTop(S, *y) 取棧頂元素操作,假設棧S不空那么取棧頂元素保存在*y中4 棧的順序存儲結構(順序棧)棧的存儲結構描述typedef struct ElemType elemMAXSIZE; int top; /*棧頂指針*/ SqStack; 利用一批地址連續的存儲單元依次存放自棧底到棧頂的數據元素，同時設一個棧頂指針top 指向棧頂元素在順序棧中的位置5進棧例如 4 3 2 1top0空棧a 進棧b 進棧 4 3 2top 1 0a 4 3 top 2 1

3、b 0ae 進棧 4e 3 d 2c 1b 0af 進棧上溢 4e 3 d 2c 1b 0atoptop6出棧例如b出棧c出棧 4 3 2 top1b 0a 4 3 top 2c 1b 0ae 出棧 top4e 3 d 2c 1b 0a 4top 3 d 2c 1b 0ad 出棧a出棧，棧空 4 3 2 1 top0a7棧空 top=O 時棧滿 top=MAXSIZE時進棧 先進一個元素，指針top加1出棧 先指針top減1，出一個元素，棧頂指針top 始終指向棧頂元素的下一個位置上溢 棧滿時如還有元素要進棧,它可能使有用信息喪失，因此要盡量防止下溢 棧空時還要出棧,下溢常常用來作為控制轉移的

4、條件或算法結束的標志有關說明8棧的主要算法 /* (1)初始化建立一個空棧S */void InitStack_Sq( SqStack *S) S-top=0; /* InitStack_Sq*/ /* 2判棧S是否為空 , 空那么返回1 */int Empty_Sq( SqStack *S) return ( S-top=0) ; /*Empty_Sq */9 /* (3)進棧操作，假設棧S未滿，將元素x進棧 */int Push_Sq(SqStack *S, ElemType x) if( S-top=MAXSIZE ) return 0; /* 棧滿 */ S-elemS-top=x;

5、S-top+; return 1; /*Push_Sq */ /*(4)出棧操作,假設棧S非空,刪除棧頂元素并保存在*y中*/ int Pop_Sq(SqStack *S , ElemType *y) if(S-top=0) return 0; /* 棧空 */ -S-top; *y=S-elemS-top; return 1; /*Pop_Sq */10思考：設計GetTop算法int GetTop _Sq(SqStack *S , ElemType *y) if(S-top=0) return 0; /* 棧空 */ *y=S-elemS-top; return 1; /* GetTop

6、_ Sq */113.1.3 棧的鏈式存儲結構(鏈棧)鏈棧采用帶表頭結點的單鏈表結構，將尾結點定為棧底，首元結點定為棧頂鏈棧由它的棧頂指針top唯一確定插入與刪除僅在棧頂處執行鏈棧無棧滿問題，空間可擴充適合于多棧操作棧頂棧底top BC Adata next 12說明 使用帶表頭結點的單鏈表，是因為這樣在入棧和出棧操作時改變的都是指針top所指頭結點的指針域的值，而不是指針top 的值鏈棧的存儲結構描述typedef struct node ElemType data; Struct node *next; SNode; 13鏈棧的主要算法/*建立一個空鏈棧 */ SNode *InitSta

7、ck_L(void) top=new SNode; top-next=NULL; return top; /* InitStack_L*/ top14 /* 元素x進鏈棧 */ void Push_L(SNode *top , ElemType x) p=new SNode; p-data=x; p-next=top-next; top-next=p; /* Push_L*/x ptop 15 /* 假設鏈棧非空，棧頂元素出棧并保存在*y中*/int Pop_L(SNode *top , ElemType *y) if(top-next=NULL) return 0; /*鏈棧已空*/ p=t

8、op-next; *y=p-data; top-next=p-next; delete p; return 1;/* Pop_L*/ptop16多個鏈棧的操作 在程序中需要同時使用兩個以上的棧時，可用多個鏈棧，操作極為方便。我們可將多個鏈棧的棧頂指針放在一個一維數組之中，即可設： SNode *topn； 讓top0，top1，topn-1 指向n個不同的鏈棧。操作時只需確定棧號i ，然后以topi 棧頂指針進行棧操作。此時每個鏈棧不需帶表頭結點。17top0 topi topn-1棧頂多個鏈棧18算法如下： /* 元素x進第 i號鏈棧*/void Pushn(SNode *top ,int

9、i, ElemType x) pnew SNode； p-data=x; p-next=topi； topiP; 19/* 假設第i號鏈棧非空，棧頂元素出棧并保存在*y中*/int Popn(SNode *top,int i, ElemType *y) if(topi=NULL) return 0; /* 棧空 */ p=topi; topi=p-next; *y=p-data; free(p); return 1; 在上面的兩個算法中，當指定棧號 i(0in-1)時，那么只對第 i 個鏈棧操作，不會影響其它鏈棧。20棧的應用舉例 棧的應用非常廣泛，在計算機程序設計很重要。比方，在編譯和運行計

10、算機語言程序的過程中，就需要利用棧進行語法檢查、計算表達式的值、函數的調用和實現遞歸等。下面討論棧在這些方面的幾個應用例子21檢驗表達式中的左右圓括號是否匹配 假設表達式存儲在字符數組str 中，設置一個元素為字符類型的棧S ，用它來存儲表達式中從左到右順序掃描到的左括號,棧的最大深度不會超過表達式中左括號的個數。算法實現順序掃描字符數組str 中的每一個字符凡遇到( ，那么令其進棧；假設遇到的是),那么棧頂元素應出棧,此時假設棧S 發生下溢,那么說明缺少與之匹配的(括號；當表達式處理完畢時, 棧S 應空，否那么說明缺少)。22/*算法3.1 檢驗str中的表達式的左右圓括號是否匹配*/int

11、 Pair(char *str )InitStack(S)；/*置S棧為空 */ for ( ; *str; str+ ) switch (*str) case ( : Push(S,*str);break; case ) : if(StackEmpty(S) return 0;/* 缺少相配的左括號 */ else Pop(S,y); break; if(StackEmpty(S) return 1; return 0; /* 缺少相配的右括號 */*Pair*/思考 1如采用對左右括號分別計數的方法，如何實現匹配算法，并與算法3.1比較;2當表達式中出現多種括號對,如( 和) 、和、和時，

12、如何用算法3.1的思路來實現?23#include #include #define MAXSIZE 20 typedef char ElemType ; typedef struct ElemType elemMAXSIZE; int top; SqStack; SqStack stack; void InitStack_Sq( SqStack *S) S-top=0; int Empty_Sq( SqStack S) return ( S.top=0) ; 24int Push_Sq(SqStack *S, ElemType x) if( S-top=MAXSIZE ) return 0;

13、 S-elemS-top=x; S-top+; return 1; int Pop_Sq(SqStack *S ) if(S-top=0) return 0; -S-top; return 1; 25int Pair(char *str ) InitStack(&stack)； for ( ; *str; str+ ) switch (*str) case ( : Push(&stack,*str);break; case ) : if(StackEmpty(stack) return 0; else Pop(&stack); break; if(StackEmpty(stack) retur

14、n 1; return 0; 26main() char exp1 =(a+b)*(c-d)/n-x/y); char exp2 =(a+b)*(c-d)/n-x/y); int tag; /clrscr(); tag=Pair(exp1); if(tag=1) printf(%s is Pair!n,exp1); else printf(%s is not Pair!n,exp1); tag=Pair(exp2); if(tag=1) printf(%s is Pair!n,exp2); else printf(%s is not Pair!n,exp2); getch();27 表達式求值

15、是程序設計語言編譯中的一個根本問題。要把一個表達式翻譯成正確求值的一個機器指令序列，或者直接對表達式求值，首先要能夠正確解釋表達式。 任何一個表達式都是由操作數(operand)、和算符(operator)組成的。操作數可以是常量或變量；算符包括運算符+,-,*,/和界限符(,),#)，它們構成的集合命名為OP。在算符集合中的特殊符號#，作為表達式的起始符和結束符，構成整個表達式的一對括號。 算術表達式的求值28表達式的算符是有優先級的，其規那么是： 先乘除，后加減； 同一個優先級，先左后右； 先括號內，后括號外。 根據上述三條運算規那么，在運算的每一步中，任意兩個相繼出現的算符1和2之間的優

16、先關系至多是下面三種關系之一： 12，1的優先級低于2； 12，1的優先級等于2， 12，1的優先級高于2。29表3-1-1 算符間的優先關系 + - * / ( ) # + - * / ( # = 2 1 30設兩個工作棧OPTR棧：用以存放運算符OPND棧：用以存放操作數或運算結果首先置操作數棧為空，表達式起始符#為運算符棧的棧底元素；依次讀入表達式中每一個字符，假設是操作數那么進OPND棧，假設是運算符(設為2)，那么和OPTR的棧頂算符(設為1)按表3-1-1比較優先權,再進行下面相應的操作: 假設12，2進棧 假設12，1出棧 假設12，1出棧參加運算直至整個表達式求值完畢( OPT

17、R棧的棧頂元素和當前讀入的字符均為#)算法的根本思想31算法3.2 描述了求解算術表達式過程算法中還調用了三個函數:函數Inc,OP:判定字符c是否屬于運算符集OP；函數Precede1，2:判定運算符棧的棧頂算符1與讀入的算符2之間優先關系；函數Operatea，b:進行二元運算a b例3-1 利用算法Eval_Exp對算術表達式2*(7-4)+3求值，操作過程如表3-1-2所示32OperandType Eval_Exp( void) InitStack(OPTR);Push(OPTR,#); InitStack(OPND)；c=getchar()； while (c!=#| GetTop

18、(OPTR)!=#) if(!In(c,OP) /* c是一個運算數 */ Push(OPND,c); cgetchar()； else /* c是一個算符*/ r=Precede(GetTop(OPTR),c);/*比較兩個算符的優先權 */ switch( r) case ： Pop(OPTR,op)； Pop(OPND,b)；Pop(OPND,a)； value=Operate(a,op,b)； Push(OPND,value); break； /* 退棧并將運算結果入棧 */ /* switch */ /*else*/ /*while */ return(GetToP(OPND)；33

19、步驟 OPTR棧 OPND棧 輸入字符 主要操作 1 # 2*(7-4)+3# PUSH(OPND,2) 2 # 2 *(7-4)+3# PUSH(OPTR,*) 3 # * 2 (7-4)+3# PUSH(OPTR,() 4 # *( 2 7-4)+3# PUSH(OPND,7) 5 # *( 2 7 -4)+3# PUSH(OPTR,-) 6 # *( - 2 7 4)+3# PUSH(OPND,4) 7 # *( - 2 7 4 )+3# Operate(7,-,4) 8 # *( 2 3 )+3# POP(OPTR) 9 # * 2 3 +3# PUSH(OPTR,+)10 # 6 +

20、3# Operate(2,*,3) 11 # + 6 3# PUSH(OPND,3)12 # + 6 3 # OPERATR(6,+,3)13 # 9# RETURN(GETTOP(OPND)34設棧st和隊列q的初始狀態為空，元素e1、e2、e3、e4、e5、e6依次通過棧st，一個元素出棧后即進入隊列q。假設出隊順序為e2、e4、e3、e6、e5、e1，那么棧st的容量至少應該為多少？35一個直接或間接地調用自身的函數稱為遞歸函數遞歸是程序設計中一個非常重要的方法優點是邏輯性強，結構清晰，且算法的正確性易于證明遞歸設計先要確定求解問題的遞歸模型，了解遞歸的執行過程，在此根底上進行遞歸程序設

21、計，同時還要掌握從遞歸算法到非遞歸算法的轉換過程棧與遞歸36 遞歸模型反映一個遞歸問題的遞歸結構，例如， n！的遞歸模型為: f1=1 假設 n=1 /*遞歸出口*/ fn=n*fn-1 假設 n1 /*遞歸體*/ 一般地，一個遞歸模型是由遞歸出口和遞歸體兩局部組成，前者確定遞歸到何時為止，后者確定遞歸的方式。求 n！的遞歸函數如下：37main() fact(4); 第1層fact n=4 p=4*fact(3); 第2層fact n=3 p=3*fact(2); 第1層fact n=1 p=1; 返回1 返回2 返回6 返回24 遞歸調用示意 第3層fact n=2 p=2*fact(1)

22、; long fact (int n) if(n=1) p=1; else p=n*fact(n-1); return p; /*fact*/38計算機在執行遞歸算法時，是通過棧來實現的。在一層層遞歸調用時，系統自動將其返回地址和處在每一調用層的變量數據一一記下進棧。返回時，它們一一出棧并且被采用。從執行語句fact(4);所展示的遞歸調用的情況，可以看到fact函數共被調用4次，即fact(4)、fact(3)、fact(2)、fact(1)。其中fact(4) 是在main函數中調用的，其余3次是在fact 函數中調用的。在某一層遞歸調用時，并末立即得到結果，而是進一步向深度遞歸調用，直到

23、最內層函數執行n=1 時，fact(n) 才有結果。然后在一一返回時，不斷得到中間結果，直到回到主程序就可得到 n !的最終結果。39 實際上，遞歸是把一個不能或不好直接求解的“大問題轉化成一個或幾個“小問題來解決，再把這些“小問題進一步分解成更小的“小問題來解決，如此分解，直至每個“小問題都可以直接解決此時分解到遞歸出口。當然，被分解的“小問題和“大問題必須具有相同的特征屬性。下面介紹的Hanoi 塔問題將有助于對遞歸更進一步的理解40 x y z例3-2 n階Hanoi 塔問題 假設有3個分別命名為x、y 和z 的塔座，在塔座x上插有n 個直徑大小各不相同、從小到大編號為l，2，n 的圓盤

24、，如圖3-1-5所示。現要求將x 座上的n 個圓盤移至z座上并仍按同樣順序疊排，圓盤移動時必須遵循以下規那么：(1)每次只能移動一個圓盤；(2)圓盤可以插在 x、y 和 z 中的任一塔座上；(3)任何時刻都不能將一個較大的圓盤壓在較小圓盤之上。41如何實現移動圓盤的操作呢?當n=1 時，問題比較簡單，將編號為1 的圓盤從塔座x直接移至塔座 z 上；當n1 時，利用塔座z 作輔助塔座，設法將壓在編號為n 的圓盤之上的n-1 個圓盤從塔座x (依照上述法那么)移至塔座y 上，那么可將編號為n 的圓盤從塔座x 移至塔座z上;再將塔座y 上的n-1 個圓盤(依照上述法那么)移至塔座z上將n-1 個圓盤

25、從一個塔座移至另一個塔座的問題是一個和原問題具有相同特征屬性的問題，只是問題的規模變小，因此可以用同樣的方法求解。算法3.3所示求解n 階Hanoi塔問題的遞歸函數42 /*算法3.3 將塔座x上按直徑由小到大且自上而下編號為l至n的n個圓盤按規那么移到塔座z上，y可以用作輔助塔座函數move(x,n,z)實現把編號為n的圓盤從x座移到z座的操作*/void Hanoi(int n，char x，char y，char z) if(n=1) move(x,1,z)；/* 編號為l的圓盤從x移到z */ else /*將x上編號為1到n-1的圓盤移到y上，z作輔助塔座*/ Hanoi(n-l,x

26、,z,y)； /*將編號為n的圓盤從x移到z 上 */ move(x,n,z)； /*將y上編號為l至n-l的圓盤移到z上，x作輔助塔座*/ Hanoi(n-l,y,x,z)； /* Hanoi */43 下面用語句：Hanoi(3,a,b,c)；來展示遞歸執行的過程Hanoi(3,a,b,c)；Hanoi(2,a,c,b)；move(a,3,c)； /*3號盤從a移到c*/Hanoi(2,b,a,c)；Hanoi(1,a,b,c)；/*1號盤從a移到c*/move(a,2,b)；/*2號盤從a移到b*/Hanoi(1,c,a,b)；/*1號盤從c移到b*/Hanoi(1,b,c,a)；/*1

27、號盤從b移到a*/move(b,2,c)； /*2號盤從b移到c*/Hanoi(1,a,b,c)；/*1號盤從a移到c*/441 32 a b c 初始狀態移動后的狀態 32 a b c 1移動后的狀態 32 a b c 1移動后的狀態 3 a b c 12移動后的狀態 3 a b c 12移動后的狀態 3 a b c 12移動后的狀態 3 a b c 12移動后的狀態 3 a b c 12 3階Hanoi塔 遞歸過程圖示45 雖然遞歸算法簡明精練，但運行效率較低，時空開銷較大，并且某些高級語言(如FORTRAN語言)沒有提供遞歸調用的語句及功能。因此，在實際應用中往往會使用非遞歸方法。為了提

28、高程序設計的能力，有必要進行由遞歸方法到非遞歸方法的根本訓練。通過前面對遞歸算法執行的分析，我們已經知道，系統內部是借助于棧來實現遞歸的。因此，在設計相應的非遞歸算法時也需要人為地設置一個棧來實現。具體如何實現將在后面的有關章節中詳細介紹。46 32 隊列(Queue)隊列：只允許在表的一端進行插入，在另一端進行刪除的，操作受限制的線性表允許插入的一端稱之為隊尾(rear)允許刪除的一端稱之為隊頭(front)入隊插入: 將一個數據元素存放在隊尾出隊刪除：將隊頭元素取出并刪除特點:先進先出(LIFO )47a1 a2 a3 a n隊頭隊尾出隊入隊隊列示意 在日常生活中，隊列的例子到處皆是，如等

29、待購物的顧客總是按先來后到的次序排成隊，先得到效勞的顧客是站在隊頭的先來者，而后到的人總是排在隊的末尾。 在程序設計中，一個典型的例子就是操作系統中的作業排隊。48隊列的根本操作InitQueue(Q) 初始化一個空隊列QEnQueue(Q，x) 在隊列Q的尾部插入一個新的元素XDelQueue(Q，*y) 刪除隊列Q的隊頭的元素，并存人*y中QueueEmpty(Q) 判隊列Q是否為空,假設為空返回一個真值，否那么返回一個假值GetFront(Q，*y) 取得隊列Q的隊頭元素49隊列的順序存儲結構順序存儲結構定義typedef struct ElemType elemMAXSIZE; int

30、 front,rear; /*隊頭、隊尾指針*/ SqQueue;50空隊列q1 入隊543 210rear front543 210q1rear front543 21q20q1rear frontq2 入隊初始置空隊列:頭、尾指針均置為0，即 front=rear=0入隊操作:先在尾指針rear位置插入一個 元素，然后尾指針增1注意:尾指針始終指向隊尾元素的下一個位置入隊示意51543 21q20q1rear frontq1 出隊543 21q20q1rear frontq2 出隊,隊空543 21q20q1rear front出隊操作:先在頭指針front 位置取出一個 元素，然后頭指針

31、增1注意:頭指針始終指向隊頭元素的當前位置隊空條件:頭指針rear =尾指針 front出隊示意52q3入隊543 2q31q20q1rear frontq6入隊,隊滿？5q64q53 q42q31q20q1rear front假溢出 隊列的實際可用空間并沒有占滿，但隊尾卻無法插入元素隊滿如何判斷53循環隊列(Circular Queue)解決假溢出的方法是把順序隊列所使用的存儲空間構造成一個邏輯上的環狀空間，即把elem0 接在elemMAXSIZE-1 之后。發生假溢出時，將新元素插入到第一個位置上，這樣雖然物理上隊尾在隊頭之前，但邏輯上隊頭仍然在前，入隊和出隊仍按“先進先出的原那么進行5

32、34120Sq.frontSq.rearq3q4循環隊列sq54534120Sq.frontSq.rearq3q4 此時假設q5要入隊, 隊尾指針Sq.rear再進一個位置就應自動到0,這可以利用對MAXSIZE取模%運算來實現,即： Sq.rear = (Sq.rear+1)% MAXSIZE534120Sq.frontSq.rearq3q4q5 同理,出隊時對隊頭指針Sq.front的修改也是： Sq.front = (Sq.front+1% MAXSIZE入隊和出隊時隊頭尾指針的修改55隊空條件討論假設q3、q4和q5相繼出隊列534120Sq.frontSq.rearq3q4q5534

33、120Sq.frontSq.rearq3q4q5此時隊列已空，得到隊空條件為: Sq.front = Sq.rear56假設q6、q7和q8相繼入隊列此時隊列已滿，得到隊滿條件為: Sq.rear = Sq.front 與隊空條件相同，任何區分？534120Sq.frontSq.rearq3q4q5Sq.rearSq.front534120q3q4q5q7q8q6隊滿條件討論57課堂思考：如何判斷順序循環隊列是空還是滿？ 結論：當循環隊列滿時有front=rear ，而當循環隊列空時也有front=rear。rear0 1 2 34 5 6 7BACfrontrear0 1 2 34 5 6

34、7BACfrontrear0 1 2 34 5 6 7front隊列中有五個元素A、B、C、D、EDEDEXYZ又有三個元素X、Y、Z入隊后隊列滿所有元素出隊后隊列空58另設一個標志位以區別隊列是空還是滿；約定 隊空條件: Sq.front = Sq.rear 隊滿條件:隊尾指針加1等于隊頭指針,即 (Sq.rear+1 ) %MAXSIZE= Sq.front即一個大小為MAXSIZE的循環隊列最多有MAXSIZE-1個元素Sq.rearSq.front534120q3q4q5q7q6處理的方法59循環隊列的主要算法實現 /*將循環隊列Sq初始化置為空循環隊列 */ void InitQue

35、ue(SqQueue *Sq) Sq-front=Sq-rear=0; /* InitQueue*/ 60/* 在循環隊列Sq的尾部入隊一個新元素x */ int EnQueue(SqQueue *Sq，ElemType x) if(Sq-rear+1) % MAXSIZE = Sq-front) return 0; /*隊列已滿*/ Sq-elemSq-rear=x; Sq-rear=(Sq-rear+1) % MAXSIZE; return 1; /* EnQueue*/61/*循環隊列Sq出隊一個元素，并存人*y中*/int DelQueue(SqQueue *Sq，ElemType *

36、y) if(Sq-front=Sq-rear) return 0; /*隊列已空*/ *y=Sq-elemSq-front; Sq-front=(Sq-front+1) % MAXSIZE ; return 1; /* DelQueue*/62 隊列的鏈式存儲結構鏈式隊列用帶表頭結點單鏈表表示，簡稱鏈隊列一個鏈隊列用兩個指針分別指示隊頭和隊尾，隊頭指針front在鏈表鏈頭，隊尾指針rear在鏈表鏈尾鏈隊列在入隊時無隊滿問題，但有隊空問題 隊空條件為:front = rear隊頭隊尾 rear frontdata next 63鏈隊列存儲結構的定義typedef struct node /*結點

37、結構*/ ElemType data; struct node *next; QNode;typedef struct QNode *front; /*隊頭指針*/ QNone *rear; /*隊尾指針*/ LQueue;64鏈隊列主要算法實現/* 初始化鏈隊列Lq，生成鏈隊列的表頭結點，并令頭指針和尾指針指向該結點*/void InitQueue_L(LQueue *Lq) p=( QNone *)malloc(sizeof(QNone); p-next=NULL； Lq-front=Lq-rear=p; /* InitQueue_L*/pLq-frontLq-rear65入隊圖示Lq-f

38、rontLq-rearab入隊前pxLq-frontLq-rearab入隊后66/* 在鏈隊列Lq的尾部插入一個新的元素x */ void EnQueue_L(LQueue *Lq，ElemType x) p=(QNone *)malloc(sizeof(QNone); p-data=x; p-next=NULL ; Lq-rear-next=p；Lq-rear=p; /* EnQueue_L*/算法67cLq-frontLq-rearab出隊前pcLq-frontLq-rearab出隊后出隊圖示68算法 /*刪除隊列Lq的隊頭元素，并存入*y中*/ int DelQueue-L(LQueue

39、 *Lq，ElemType *y) if(Lq-front=Lq-rear) return 0; /*隊列已空*/ p=Lq-front-next; /*p指向隊頭結點*/ *y=p-data; Lq-front-next=p-next; if (Lq-rear=p ) Lq-rearLq-front；/*尾指針指向頭結點*/ free(p); return 1; /* DelQueue-L*/注意 防止隊尾指針喪失6933 棧和隊列的應用實例停車場管理 設有一個可以停放n輛汽車的狹長停車場,它只有一個大門可以供車輛進出。車輛按到達停車場時間的先后次序從停車場最里面向門口處停放(最先到達的第一

40、輛車停在停車場的最里面)。如果停車場已放滿n輛車，那么后來的車輛只能在停車場大門外的便道上等待，一旦停車場內有車開走,那么排在便道上的第一輛車就可進入停車場。停車場內如有某輛車要開走,在它之后進入停車場的車輛都必須先退出停車場為它讓路,待其開出停車揚后,這些車輛再依原來的次序進入。每輛車在離開停車場時,根據它在停車場內停留時間的長短交費。如果停在便道上的車輛未進停車場就要離去，允許其離去時不收停車費,并且仍然保持在便道上等待的車輛的次序。 現在編制一個程序來模擬停車場的管理。70 首先確定模擬程序中需要的數據結構及其操作。 由于停車場只有一個大門,因此可用一個棧來模擬;根據便道停車的特點，先排

41、隊的車輛先離開便道進入停車場,可以用一個隊列來模擬；又因為排在停車場中間的車輛可以提前離開，因此還需要有一個地方(車輛躲避所)保存為了讓路離開停車場的車輛,很顯然這也應該用一個棧來模擬。所以在程序中設置了兩個順序棧s1和s2分別表示停車場和躲避所;設置了一個鏈隊列q表示便道。它們的數據類型定義在下面的源程序中，為了操作方便，鏈隊列表頭結點中的num域中存放便道上的車輛數量。71 程序執行時，當輸入數據表示有車輛到達時，判斷棧s1是否滿，假設未滿就將新數據進棧s1；假設棧已滿,就將數據入隊列q，表示車輛在便道上等待進入停車場。該操作過程由函數Arrive完成。 當輸入數據表示有車輛要離去時,就在

42、棧s1中尋找此車牌號的車輛,如尋找到就讓其離開停車場,并根據停車時間計費，同時將隊列q的隊頭元素進棧s1；如沒有找到,就到隊列q中去尋找此車牌號的車輛。如在隊列q中找到就允許其離開隊列,并不收費；如找不到就顯示出錯信息。 當離開停車場的車輛位于棧s1的中間時,必須先將此位置到棧頂之間的所有數據倒到棧s2中去,然后安排車輛出棧s1,最后將棧s2中的數據倒回到棧s1中來。該操作過程由函數Delive完成。顯然，以上兩個主要操作需要利用棧和隊列的兩個根本操作入棧隊列和出棧隊列來實現。 源程序中的函數Display那么可以隨時顯示停車場的狀況。72 下面是模擬停車場管理的源程序。其模擬過程中棧和隊列的

43、變化過程可以見本書附帶的光盤。#include stdio.h#define N 2 /*停車場容量*/#define M 5 /*停車單價*/#define True 1#define False 0typedef struct int num; /*車牌號*/ int arrtime; /*到達/離開時間*/ ElemType; /*順序棧的數據元素類型*/typedef struct ElemType elemN; int top; SqStack; /*順序棧類型*/73typedef struct node int num; /*車牌號/便道上的車輛數量*/ struct node

44、*next; QNode; /*鏈隊列的數據元素類型*/typedef struct QNode *front, *rear; LQueue; /*鏈隊列類型*/74/*函數聲明*/void InitStack_Sq (SqStack *s); /*初始化棧*/int Push_Sq(SqStack *s,ElemType x); /*入棧*/ElemType Pop_Sq(SqStack *s); /*出棧*/void InitQueue_L(LQueue *q); /*初始化隊列*/void EnQueue_L (L LQueue *q,int num1); /*入隊列*/int DelQ

45、ueue_L(LQueue *q); /*出隊列*/*以上函數定義在本書附帶的光盤中*/75/*車輛x進入停車場*/void Arrive (SqStack *s1, LQueue *q,ElemType x) int f; f=Push_Sq(s1,x); if (f=False) /*停車場棧s1已滿入便道q */ EnQueue_L(q,x.num); printf(第%d號車停在便道第%d車位上n, x.num,q-front-num); else printf(第%d號車停在停車場第%d車位上n, x.num,s1-top); /* Arrive */76void Delive (S

46、qStack *s1,SqStack *s2, LQueue *q,ElemType x) /*車輛x離開停車場*/ int n,f=False; ElemType y; QNode *p; while (s1-top0) & (f!=True) /*在棧s1中尋找車輛x */ y=Pop_Sq(s1); if (y.num!=x.num) n=Push_Sq(s2,y); else f=True; if (y.num=x.num) /*尋找到車輛x*/ printf(第%d號車應收費%d元n, )*M); while (s2-top0) /*將棧s2中的車輛倒回到棧s1中*/ y=Pop_Sq(s2); f=Push_