1、第三章 棧和隊列,【課前思考】,簡單地說，線性結構是一個數據元素的序列。,必然是依從上往下的次序，即n,2,1。它們遵循的是后進先出的規(guī)律，這正是本章要討論的棧的結構特點。,是排隊。在計算機程序中，模擬排隊的數據結構是隊列。,【學習目標】,1. 掌握棧和隊列這兩種抽象數據類型的特點，并能在相應的應用問題中正確選用它們。 2. 熟練掌握棧類型的兩種實現方法。 3. 熟練掌握循環(huán)隊列和鏈隊列的基本操作實現算法。 4. 理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。,棧和隊列是在程序設計中被廣泛使用的兩種線性數據結構，因此本章的學習重點在于掌握這兩種結構的特點，以便能在應用問題中正確使用。,【知識點】,順

2、序棧、鏈棧、循環(huán)隊列、鏈隊列,【重點和難點】,【學習指南】,在這一章中，主要是學習如何在求解應用問題中適當地應用棧和隊列，棧和隊列在兩種存儲結構中的實現都不難，但應該對它們了如指掌，特別要注意它們的基本操作實現時的一些特殊情況，如棧滿和?？?、隊滿和隊空的條件以及它們的描述方法。本章要求必須完成的算法設計題為：3.15，3.17，3.19，3.22， 3.27 ,3.28，3.30，3.31，3.32。其中前4個主要是練習棧的應用，后4個主要是有關隊列的實現方法的練習。,通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。,線性表 棧 隊列 insert(l, i, x) inser

3、t(s, n+1, x) insert(q, n+1, x) 1in+1 delete(l, i) delete(s, n) delete(q, 1) 1in,棧和隊列是兩種常用的數據類型,3.1 棧,3.2 棧的應用舉例,3.4 隊列,目 錄,3.3 棧與遞歸的實現,3.1 棧,一、棧的定義,棧(stack)作為一種限定性線性表，是將線性表的插入和刪除運算限制為僅在表的一端進行。 通常將表中允許進行插入、刪除操作的一端稱為棧頂(top)，因此棧頂的當前位置是動態(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。同時表的另一端為固定的一端，被稱為棧底(bottom)。當棧中沒有元素時稱為空棧。棧的

4、插入操作被形象地稱為進棧或入棧，刪除操作稱為出?；蛲藯?。 插入：最先放入棧中元素在棧底，最后放入的元素在棧頂； 刪除：最后放入的元素最先刪除，最先放入的元素最后刪除。 棧是一種后進先出(last in first out)的線性表，簡稱為lifo表。,圖3.1 棧,例：設一個棧的輸入序列為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均在棧中,按照入棧順序,在棧中順序應為d,c,b,a,出棧的順序只能是d

5、,c,b,a。所以本題答案為d。,二、棧的主要操作,1.初始化棧：initstack( /在棧構造前和銷毀后base值為null selemtype *top; /棧頂指針 int stacksize; sqstack; /當前已分配存儲空間 或簡單定義如下： #define m 100 int sm; int top;,圖3.2 順序棧中的進棧和出棧,top指向棧頂元素 初態(tài)：top=-1; 空棧，棧中無元素， 進棧：top=top+1; stop=x; 退棧：取stop; top=top-1; 棧滿：top=m-1;棧溢出（上溢），不能再進棧（錯誤狀態(tài)） top=-1時不能退棧，下溢（正常

6、狀態(tài)，常作控制條件）,（1）構造空順序棧算法:初始化棧 status initstack ( sqstack / initstack,2.順序?；静僮鞯膶崿F如下:,程序描述： /this program is to initialize a stack # include # include # include # define stack_init_size 100 # define stackincrement 10 # define ok 1 # define error 0 typedef int selemtype; typedef struct /define structure

7、 sqstack() selemtype *base; selemtype *top; int stacksize; sqstack;,int initstack(sqstack ,（2） 取順序棧的棧頂元素 status gettop ( sqstack s, selemtype / gettop,（3）將元素壓入順序棧算法（進棧） status push ( sqstack / push,（4）將元素彈出順序棧算法（退棧） status pop ( sqstack / pop,（5） 判?？辗?int empty ( sqstack s) / 如果棧 s 空，返回 1 ；如果棧 s 不空，

8、返回 0 。 if ( s.top = = s.base ) return 1; / 如果棧 s 為空，則返回 1 else return 0; / 如果棧 s 為空，則返回 0 / empty end,3棧的共享 有時，一個程序設計中，需要使用多個同一類型的棧,這時候，可能會產生一個棧空間過小，容量發(fā)生溢出，而另一個?？臻g過大，造成大量存儲單元浪費的現象。 為了充分利用各個棧的存儲空間，這時可以采用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實現存儲空間優(yōu)勢互補。,?？眨簍op1=0,top2=m-1; 棧滿：top1+1=top2,兩個棧共享存儲單元可用如下c語句描述：

9、 #define maxsize 100 #define dustacksize maxsize typedef struct dusqstack selemtype datamaxsize; int top1; /top1 is the pointer of dusqstack s1 int top2; /top2 is the pointer of dusqstack s2 int flag;dusqstack; / 或： #define maxsize 100 struct duseqstack elemtype datamaxsize; int top2 ; /兩個棧的棧頂指針 int

10、 flag; ,（1）兩個棧共享存儲單元的進棧算法 status dusqstackpush ( dusqstack / 如果 flag 不為 1,2，則返回 error else / 如果 flag 為 1 或 2，則入棧 switch ( s.flag ) case 1 : / 標志位 flag 為 1,s.datas.top1 = x; / 元素 x 入棧 s1 s.top1+; / 修改棧 s1 的棧頂指針 break; case 2 : / 標志位 flag 為 2 s.datas.top2 = x; / 元素 x 入棧 s2 s.top2- -; / 修改棧 s2 的棧頂指針 br

11、eak; / switch 結束 return ok; / else 結束 / else 結束 / dusqstackpush,（2）兩個棧共享存儲單元的退棧算法 status dusqstackpop ( dusqstack / 元素 x 出棧 / if 結束,else return error; / 如果棧 s1 為空，則返回 error break; case 2 : / 標志位 flag 為 1 if ( s.top2maxsize-1 ) /若棧 s2 不空，對 s2 進行操作 s.top2+; / 修改棧 s2 的棧頂指針 x = s.datas.top2; / 元素 x 出棧 /

12、 if 結束 else return error; / 如果棧 s2 為空，則返回 error break; / switch結束 return ok; / else結束 / dusqstackpop,4.鏈棧 （1）鏈棧結構及數據類型 棧的鏈式存貯結構,也稱為鏈棧，它是一種限制運算的鏈表，即規(guī)定鏈表中的插入和刪除運算只能在鏈表開頭進行。鏈棧結構見圖3-4。,typedef struct snode /define structure linkstack selemtype data; struct snode *next; snode,*linkstack,（2）鏈棧的五種棧運算,（a）棧初

13、始化 void inistack(linkstack top) top = ( linkstack ) malloc ( sizeof ( snode ) ); top-next=null; （b）進棧運算 status push_l ( linkstack / push_l,（c）退棧運算 status pop_l ( linkstack / pop_l,（d）取棧頂元素 status gettop_l ( linkstack top, selemtype / else 結束 / gettop_l,（5）判棧空 int empty(linkstack *top) if(top-next=nu

14、ll) return(1); else return(0); ,課 前 復 習,設n 個元素的進棧序列是p1，p2，p3， pn，其輸出序列是1,2，3，n，若p1=3，則p2的值 ()。 a、可能是2b、一定是2 c、不可能是1d、一定是1,一、 數制轉換 假設要將十進制數n轉換為d進制數，一個簡單的轉換算法是重復下述兩步， 直到n等于零： x = n mod d (其中mod為求余運算) n = n div d (其中div為整除運算) 計算過程從低位到高位，打印輸出從高位到低位,3.2 棧的應用舉例 棧在日常生活中和計算機程序設計中有著許多應用，下面僅介紹棧在計算機中的應用。,void

15、conversion(int n) /*對于任意的一個非負十進制數n， 打印出與其等值的8進制數*/ stack s; int x; /* s為順序?；蜴湕?*/ initstack( 算法3.1,二、括號匹配問題 假設表達式中允許包含三種括號:圓括號、方括號和大括號。編寫一個算法判斷表達式中的括號是否正確配對。 解:設置一個括號棧,掃描表達式：遇到左括號(包括(、和)時進棧,遇到右括號時,若棧是相匹配的左括號,則出棧,否則,返回0。 若表達式掃描結束,棧為空,返回1表示括號正確匹配,否則返回0。,int correct(char exp,int n) char stmaxsize; int

16、top=-1,i=0,tag=1; while (in ,if (expi=) /*遇到,若棧頂是, 則繼續(xù)處 理,否則以不配對返回*/ if (sttop=) top-; else tag=0; if (expi=) /*遇到,若棧頂是 ,則繼續(xù)處 理,否則以不配對返回*/ if (sttop=) top-; else tag=0; i+; /*表達式掃描完畢*/ if (top-1) tag=0; /*若棧不空,則不配對*/ return(tag); ,三、行編輯程序 功能：接收用戶從終端輸入的數據或程序，并存入用戶的數據區(qū)。 算法思想：設輸入緩沖區(qū)為一個棧結構，每當從終端接收一個字符后先

17、作如下判別：若它既不是退格符（#）也不是退行符（）,則將該字符入棧；若是退格符（#），則從棧頂刪去一個字符；若是退行符（），則將棧清空。 算法描述如下：,void lineedit() initstack(s); ch=getchar(); while(ch!=eof) /eof為全文結束符 while(ch!=eof,五、 表達式求值,表達式求值是高級語言編譯中的一個基本問題， 是棧的典型應用實例。 任何一個表達式都是由操作數(operand)、 運算符(operator)和界限符(delimiter)組成的。操作數既可以是常數， 也可以是被說明為變量或常量的標識符；運算符可以分為算術運算符

18、、 關系運算符和邏輯運算符三類；基本界限符有左右括號和表達式結束符等。,1.無括號算術表達式求值,表達式計算 程序設計語言中都有計算表達式的問題， 這是語言編譯中的典型問題。 (1) 表達式形式： 由運算對象、 運算符及必要的表達式括號組成； (2) 表達式運算： 運算時要有一個正確的運算形式順序。 由于某些運算符可能具有比別的運算符更高的優(yōu)先級，因此表達式不可能嚴格的從左到右， 見圖3.5。,圖3.5 表達式運算及運算符優(yōu)先級,圖3.6 無括號算術表達式的處理過程,2. 算術表達式處理規(guī)則 (1) 規(guī)定優(yōu)先級表。 (2) 設置兩個棧： ovs(運算數棧)和optr(運算符棧)。 (3) 自左

19、向右掃描，遇操作數進ovs，遇操作符則與optr棧頂優(yōu)先數比較：當前操作符optr棧頂, 當前操作符進optr棧；當前操作符optr棧頂，ovs棧頂、次頂和optr棧頂，退棧形成運算t(i)，t(i)進ovs棧。 例： 實現a/bc+d*e的運算過程時棧區(qū)變化情況如圖3.7所示。,圖3.7 a/bc+d*e運算過程的棧區(qū)變化情況示意圖,+,*,3. 帶括號算術表達式 假設操作數是整型常數，運算符只含加、減、乘、除等四種運算符， 界限符有左右括號和表達式起始、結束符“”，如： （7+15）*（23-28/4）。 引入表達式起始、 結束符是為了方便。 要對一個簡單的算術表達式求值， 首先要了解算術

20、四則運算的規(guī)則， 即： (1) 從左算到右；(2) 先乘除， 后加減；(3) 先括號內， 后括號外。,運算符和界限符可統(tǒng)稱為算符，它們構成的集合命名為optr。根據上述三條運算規(guī)則，在運算過程中，任意兩個前后相繼出現的算符1和2之間的優(yōu)先關系必為下面三種關系之一： 12， 1的優(yōu)先權高于2。,表 3-1 算符之間的優(yōu)先關系,實現算符優(yōu)先算法時需要使用兩個工作棧： 一個稱作optr， 用以存放運算符；另一個稱作opnd，用以存放操作數或運算的中間結果。 算法的基本過程如下： 首先初始化操作數棧opnd和運算符棧optr， 并將表達式起始符“”壓入運算符棧； 依次讀入表達式中的每個字符，若是操作數

21、則直接進入操作數棧opnd， 若是運算符，則與運算符棧optr的棧頂運算符進行優(yōu)先權比較，并做如下處理： ,(1) 若棧頂運算符的優(yōu)先級低于剛讀入的運算符， 則讓剛讀入的運算符進optr棧； (2) 若棧頂運算符的優(yōu)先級高于剛讀入的運算符，則將棧頂運算符退棧，送入，同時將操作數棧opnd退棧兩次，得到兩個操作數a、b，對a、 b進行運算后， 將運算結果作為中間結果推入opnd棧； (3) 若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)先級相同，說明左右括號相遇，只需將棧頂運算符（左括號）退棧即可。,算法具體描述如下：,int expevaluation() /*讀入一個簡單算術表達式并計算其值。 o

22、perator和operand分別為運算符棧和運算數棧， ops為運算符集合*/ initstack( while(c!=|gettop(optr)! =) /* gettop()通過函數值返回棧頂元素*/, if(!in(c,op) push(,pop( ,例求表達式1+2*3-4/2的值，棧的變化如下。,步驟 操作數棧 運算符棧 說明,開始,兩棧均為空,1,1,1進入操作數棧,+進入運算符棧,2進入操作數棧,*進入運算符棧,3進入操作數棧,退棧,2*3進入操作數棧,退棧,1+6進入操作數棧,2,3,4,5,6,7,8,9,1,+,1,2,+,1,2,+,1,1,1,7,+,*,2,3,6,

23、+,*,+,步驟 操作數棧 運算符棧 說明,10,7,-進入運算符棧,4進入操作數棧,/進入運算符棧,2進入操作數棧,退棧,4/2進入操作數棧,退棧,7-2進入操作數棧,11,12,13,14,15,16,17,7 4,-,7 4,- /,7 4 2,- /,7,7 2,-,-,-,5,當然，算術表達式除了簡單求值外，還會涉及到算術表達式的兩種表示方法，即中綴表示法和后綴表示法。中綴表達式求值較麻煩（須考慮運算符的優(yōu)先級，甚至還要考慮圓括號），而后綴表達式求值較方便（無須考慮運算符的優(yōu)先級及圓括號）。下面將介紹算術表達式的中綴表示和后綴表示及它們的求值規(guī)律，,例如，對于下列各中綴表達式：（1）

24、 3/5+8 （2） 18-9*(4+3) （3） (25+x)*(a*(a+b)+b) 對應的后綴表達式為： (1)3 5 / 8 + (2)18 9 4 3 + * - (3)25 x + a a b + * b + *,4.中綴表達式變成等價的后綴表達式 將中綴表達式變成等價的后綴表達式，表達式中操作數次序不變，運算符次序發(fā)生變化，同時去掉了圓括號。轉換規(guī)則是：設立一個棧，存放運算符，首先棧為空，編譯程序從左到右掃描中綴表達式，若遇到操作數，直接輸出，并輸出一個空格作為兩個操作數的分隔符；若遇到運算符，則必須與棧頂比較，運算符級別比棧頂級別高則進棧，否則退出棧頂元素并輸出，然后輸出一個空

25、格作分隔符；若遇到左括號，進棧；若遇到右括號，則一直退棧輸出，直到退到左括號止。當棧變成空時，輸出的結果即為后綴表達式。 將中綴表達式(1+2)*(8-2)/(7-4)變成等價的后綴表達式。 現在用棧來實現該運算，棧的變化及輸出結果如下,步驟 棧中元素 輸出結果 說明,5.后綴表達式的求值 將中綴表達式轉換成等價的后綴表達式后，求值時，不需要再考慮運算符的優(yōu)先級，只需從左到右掃描一遍后綴表達式即可。具體求值步驟為：設置一個棧，開始時，棧為空，然后從左到右掃描后綴表達式，若遇操作數，則進棧；若遇運算符，則從棧中退出兩個元素，先退出的放到運算符的右邊，后退出的放到運算符左邊，運算后的結果再進棧，直

26、到后綴表達式掃描完畢。此時，棧中僅有一個元素，即為運算的結果。例，求后綴表達式：1 2 + 8 2 - 7 4 - / *的值， 棧的變化情如下：,從上可知，最后求得的后綴表達式之值為6，與用中綴表達式求得的結果一致，但后綴式求值要簡單得多。,五、 求解迷宮問題 求迷宮問題就是求出從入口到出口的路徑。在求解時,通常用的是“窮舉求解”的方法,即從入口出發(fā),順某一方向向前試探,若能走通,則繼續(xù)往前走；否則沿原路退回,換一個方向再繼續(xù)試探,直至所有可能的通路都試探完為止。為了保證在任何位置上都能沿原路退回(稱為回溯),需要用一個后進先出的棧來保存從入口到當前位置的路徑。 首先用如圖3.3所示的方塊圖

27、表示迷宮。對于圖中的每個方塊,用空白表示通道,用陰影表示墻。所求路徑必須是簡單路徑,即在求得的路徑上不能重復出現同一通道塊。,為了表示迷宮,設置一個數組mg,其中每個元素表示一個方塊的狀態(tài),為0時表示對應方塊是通道,為1時表示對應方塊為墻,如圖3.3所示的迷宮,對應的迷宮數組mg如下: int mgm+1n+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,

28、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;,while (棧不空) 若當前位置可通， 則將當前位置插入棧頂； / 納入路徑 若該位置是出口位置，則算法結束； / 此時棧中存放的是一條從入口位置到出口位置的路徑否則切換當前位置的北鄰方塊為新的當前位置； 否則若棧不空且棧頂位置尚有其他方向未被探索， 則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通， 則 刪去棧頂位置；/ 從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置， 直至

29、找到一個可通的相鄰塊或出棧至?？眨?,算法描述：,void mgpath()/*路徑為:(1,1)-(m-2,n-2)*/ int i,j,di,find,k; top+; /*初始方塊進棧*/ stacktop.i=1;stacktop.j=1;stacktop.di=-1;mg11=-1; while (top-1) /*棧不空時循環(huán)*/ i=stacktop.i;j=stacktop.j;di=stacktop.di; if (i=m-2 ,find=0; while (di4 ,if (find=1) /*找到了下一個可走方塊*/ stacktop.di=di; /*修改原棧頂元素的d

30、i值*/ top+; /*下一個可走方塊進棧*/ stacktop.i=i;stacktop.j=j;stacktop.di=-1; mgij=-1;/*避免重復走到該方塊*/ else /*沒有路徑可走,則退棧*/ mgstacktop.istacktop.j=0; /*讓該位置變?yōu)槠渌窂娇勺叻綁K*/ top-; printf(沒有可走路徑!n); ,3.3 棧與遞歸的實現,1、什么是遞歸 在定義一個過程或函數時出現調用本過程或本函數的成分,稱之為遞歸。若調用自身,稱之為直接遞歸。若過程或函數p調用過程或函數q,而q又調用p,稱之為間接遞歸。 如果一個遞歸過程或遞歸函數中遞歸調用語句是最后

31、一條執(zhí)行語句,則稱這種遞歸調用為尾遞歸。,例 以下是求n!(n為正整數)的遞歸函數。 int fun(int n) int x; if (n=1) /*語句1*/ x=1;/*語句2*/ else /*語句3*/ x=fun(n-1)*n;/*語句4*/ return(x);/*語句5*/ 在該函數fun(n)求解過程中,直接調用fun(n-1)(語句4)自身,所以它是一個直接遞歸函數。又由于遞歸調用是最后一條語句,所以它又屬于尾遞歸。,2 、何時使用遞歸 在以下三種情況下,常常要用到遞歸的方法。 1) 定義是遞歸的 有許多數學公式、數列等的定義是遞歸的。例如,求n!和fibonacci數列等

32、。這些問題的求解過程可以將其遞歸定義直接轉化為對應的遞歸算法。,2) 數據結構是遞歸的 有些數據結構是遞歸的。例如,第2章中介紹過的單鏈表就是一種遞歸數據結構,其結點類型定義如下： typedef struct lnode elemtype data; struct lnode *next; linklist; 該定義中,結構體lnode的定義中用到了它自身,即指針域next是一種指向自身類型的指針,所以它是一種遞歸數據結構。,對于遞歸數據結構,采用遞歸的方法編寫算法既方便又有效。例如,求一個不帶頭結點的單鏈表head的所有data域(假設為int型)之和的遞歸算法如下： int sum(li

33、nklist *head) if (head=null) return 0; else return(head-data+sum(head-next); ,3)問題的求解方法是遞歸的 有些問題的解法是遞歸的,典型的有hanoi問題求解,該問題描述是：設有3個分別命名為x,y和z的塔座,在塔座x上有n個直徑各不相同,從小到大依次編號為1,2,n的盤片,現要求將x塔座上的n個盤片移到塔座z上并仍按同樣順序疊放,盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤片；盤片可以插在x,y和z中任一塔座；任何時候都不能將一個較大的盤片放在較小的盤片上。設計遞歸求解算法,并將其轉換為非遞歸算法。 設hanoi(

34、n,x,y,z)表示將n個盤片從x通過y移動到z上,遞歸分解的過程是：,hanoi(n,a,b,c),hanoi(n-1,a,c,b)； move(n,a,c):將第n個圓盤從a移到c； hanoi(n-1,b,a,c),圖 hanoi塔的遞歸函數運行示意圖,3、 遞歸模型 遞歸模型是遞歸算法的抽象,它反映一個遞歸問題的遞歸結構,例如,前面的遞歸算法對應的遞歸模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 其中,第一個式子給出了遞歸的終止條件,第二個式子給出了fun(n)的值與fun(n-1)的值之間的關系,我們把第一個式子稱為遞歸出口,把第二個式子稱為

35、遞歸體。,實際上,遞歸思路是把一個不能或不好直接求解的“大問題”轉化成一個或幾個“小問題”來解決,再把這些“小問題”進一步分解成更小的“小問題”來解決,如此分解,直至每個“小問題”都可以直接解決(此時分解到遞歸出口)。但遞歸分解不是隨意的分解,遞歸分解要保證“大問題”與“小問題”相似,即求解過程與環(huán)境都相似。,求解fun(5)的過程如下：5!,4 遞歸問題的優(yōu)點 通過上面的例子可看出，遞歸既是強有力的數學方法， 也是程序設計中一個很有用的工具。其特點是對遞歸問題描述簡捷，結構清晰，程序的正確性容易證明。 5、消除遞歸的原因 其一：有利于提高算法時空性能，因為遞歸執(zhí)行時需要系統(tǒng)提供隱式棧實現遞歸

36、，效率低且費時。 其二： 無應用遞歸語句的語言設施環(huán)境條件，有些計算機語言不支持遞歸功能，如fortran語言中無遞歸機制 。 其三：遞歸算法是一次執(zhí)行完，這在處理有些問題時不合適， 也存在一個把遞歸算法轉化為非遞歸算法的需求。 ,3.4 隊列,隊列簡稱隊,它也是一種運算受限的線性表,其限制僅允許在表的一端進行插入,而在表的另一端進行刪除。 我們把進行插入的一端稱做隊尾(rear),進行刪除的一端稱做隊首(front)。 向隊列中插入新元素稱為進隊或入隊,新元素進隊后就成為新的隊尾元素；從隊列中刪除元素稱為出隊或離隊,元素出隊后,其后繼元素就成為隊首元素。,二、隊列的基本運算 1. 初始化操作

37、：initqueue( /*數據域*/ struct qnode *next; /*指針域*/ qnode,*queueptr; typedef struct queueptr front; queueptr rear; linkqueue;,鏈隊列的基本操作 （1） 初始化操作。 int initqueue(linkqueue ,（2） 入隊操作。 status enqueue(linkqueue ,（3） 出隊操作。 int dequeue(linkqueue ,2. 循環(huán)隊列:隊列的順序表示和實現,圖3.15 隊列的基本操作,用一組連續(xù)的存儲單元依次存放隊列的元素，并設兩個指針front

38、、rear分別指示隊頭和隊尾元素的位置。 front：指向實際的隊頭；rear：指向實際隊尾的下一位置。 初態(tài)： frontrear0；隊空： frontrear;隊滿： rearm; 入隊： qrear=x; rear rear+1; 出隊：x=qfront;front=front+1;,圖3.16 循環(huán)隊列,假溢出的解決方法： （1）將隊中元素向隊頭移動；（2）采用循環(huán)隊列：q0接在qm-1之后 初態(tài)： frontrear0或m-1；隊空： frontrear; 入隊： qrear=x； rear( rear+1)%m; 出隊： x=qfront; front=(front+1)%m; 隊

39、滿： 留一個空間不用(rear+1)%m=front; 或另設一個標志以區(qū)分隊空和隊滿。,循環(huán)隊列的類型定義： define maxsize 100 /*隊列的最大長度*/ typedef struct qelemtype elementmaxsize; /* 隊列的元素空間*/ int front; /*頭指針指示器*/ int rear ; /*尾指針指示器*/ seqqueue;,循環(huán)隊列的基本操作： （1） 初始化操作。 void initqueue（seqqueue ,（2） 入隊操作。 int enterqueue(seqqueue *q, queueelementtype x) /*將元素x入隊*/ if(q-rear+1)%maxsize=q-front) /*隊列已經滿了*/ return error; q-elementq-rear=x; q-rear=(q-rear+1)%maxsize; /* 重新設置隊尾指針 */ return ok; /*操作成功*/ ,（3） 出隊操作。 int dequeue(seqqueue /*操作成功*/ ,鍵盤輸入循環(huán)緩沖區(qū)問題,有兩個進程同時存在于一個程序中。 其中第一個進程在屏幕上連續(xù)顯示字符“a”，與此同時，程序不斷檢測鍵盤是否有輸入，如果有的話，就讀入用戶鍵入