算法與數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列

1、BUPT第三章第三章 棧與隊(duì)列棧與隊(duì)列BUPT第三章第三章 （第一部分）棧（第一部分）棧BUPT SCSTBUPT提提 綱綱棧的定義1順序棧2鏈棧3棧的應(yīng)用4BUPT SCSTBUPT3.1 棧的定義棧的定義棧的定義棧的定義棧棧 是一種特殊的線性表，限定插入和刪除操作只能在表尾進(jìn)行。具有后進(jìn)先出后進(jìn)先出(LIFOLast In First Out )的特點(diǎn)。a0a1an-1棧頂（表尾）棧底bottomtop入棧入棧push出棧出棧popBUPT SCSTBUPT定義在棧結(jié)構(gòu)上的基本運(yùn)算v (1) 生成空棧操作v (2) 判?？蘸瘮?shù)v (3) 數(shù)據(jù)元素入棧操作 v (4) 數(shù)據(jù)元素出棧函數(shù)v (

2、5) 取棧頂元素函數(shù)v (6) 置?？詹僮鱲 (7) 求當(dāng)前棧元素個(gè)數(shù)函數(shù) BUPT SCSTBUPT3.2. 順序棧順序棧棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu)一個(gè)棧獨(dú)占一組地址連續(xù)的存儲(chǔ)單元一個(gè)棧獨(dú)占一組地址連續(xù)的存儲(chǔ)單元類(lèi)型定義類(lèi)型定義 數(shù)組(棧空間)+棧頂指示?？諚l件?？諚l件 S.top=-1 (此時(shí)退棧則下溢) 棧滿(mǎn)條件棧滿(mǎn)條件 S.top=max-1 (此時(shí)進(jìn)棧則上溢) Si ai . . .1 a10 a0max-1topBUPT SCSTBUPT進(jìn)棧示例進(jìn)棧示例 BUPT SCSTBUPT退棧示例退棧示例BUPT SCSTBUPT有5 個(gè)元素，其入棧次序?yàn)椋篈，B，C，D，E，在各種

3、可能的出棧次序中，以元素C，D最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次序有哪幾個(gè) ？CDEBA，CDBEA，CDBAE BUPT SCSTBUPT思考：思考：n個(gè)元素依次入棧，可得到多少個(gè)合法的出棧序列個(gè)元素依次入棧，可得到多少個(gè)合法的出棧序列 (2n)!/(n+1)!*n! 不同的出棧序列出棧序列實(shí)際上對(duì)應(yīng)著不同的入棧入棧出棧操作，以1記為入棧入棧，0為出棧出棧。則問(wèn)題實(shí)際上是求n個(gè)個(gè)1和n個(gè)個(gè)0構(gòu)成的全排列，其中任意一個(gè)位置，它及它此前的數(shù)中，1個(gè)個(gè)數(shù)要大于等于0的個(gè)數(shù)。n個(gè)個(gè)1和n個(gè)個(gè)0構(gòu)成的全排列數(shù)為：(2n)!/n!*n! 在在n個(gè)個(gè)0和和n個(gè)個(gè)1構(gòu)成的構(gòu)成的2n個(gè)數(shù)的序列中，假設(shè)第

4、一次出現(xiàn)個(gè)數(shù)的序列中，假設(shè)第一次出現(xiàn)0的個(gè)數(shù)大于的個(gè)數(shù)大于1個(gè)個(gè)數(shù)（即個(gè)個(gè)數(shù)（即0的個(gè)數(shù)比的個(gè)數(shù)比1的個(gè)數(shù)大一）的位置為的個(gè)數(shù)大一）的位置為k，則，則k為奇數(shù)，為奇數(shù)，k之前之前有相等數(shù)目的有相等數(shù)目的0和和1，各為，各為(k-1)/2. 若把這若把這k個(gè)數(shù)，個(gè)數(shù)，0換成換成1，1換成換成0 ，則原序列唯一對(duì)應(yīng)上一個(gè)則原序列唯一對(duì)應(yīng)上一個(gè)n1個(gè)個(gè)1和和n1個(gè)個(gè)0的序列。反之，任意一的序列。反之，任意一個(gè)由個(gè)由n1個(gè)個(gè)1和和n1個(gè)個(gè)0構(gòu)成的序列也唯一的對(duì)應(yīng)一個(gè)這樣不合要求構(gòu)成的序列也唯一的對(duì)應(yīng)一個(gè)這樣不合要求的序列。由于一一對(duì)應(yīng)，故這樣不合要求的序列數(shù)實(shí)際上等于有的序列。由于一一對(duì)應(yīng)，故這樣不合

5、要求的序列數(shù)實(shí)際上等于有n1個(gè)個(gè)1和和n1個(gè)個(gè)0構(gòu)成的排列數(shù)，即構(gòu)成的排列數(shù)，即(2n)!/(n+1)(n-1)。因此合法的個(gè)數(shù)為：因此合法的個(gè)數(shù)為：(2n)!/n!*n! - (2n)!/(n+1)!*(n-1)! = (2n)!/(n+1)!*n! BUPT SCSTBUPT 例兩個(gè)棧共享一組地址連續(xù)的存儲(chǔ)單元 類(lèi)型定義類(lèi)型定義 數(shù)組(?？臻g) + 兩個(gè)棧頂指示 0 1 m-1top0top1棧滿(mǎn)條件：棧滿(mǎn)條件： s.top0+1=s.top1 ?？諚l件：棧空條件： s.top0=-1（棧（棧0） s.top1=m （棧（棧1） SBUPT SCSTBUPT BUPT SCSTBUPT插入

6、新元素時(shí)的棧滿(mǎn)處理插入新元素時(shí)的棧滿(mǎn)處理 StackFull ( )BUPT SCSTBUPTtemplate void Push ( const int i, const Type & item ) if ( t i = bi+1 ) StackFull (i); else V+ti = item; /第i 個(gè)棧進(jìn)棧template Type *Pop ( const i) if ( ti = bi ) StackEmpty(i); return 0; else return & Vti-; /第i 個(gè)棧出棧BUPT SCSTBUPT3.3. 鏈棧鏈棧topa0a n-2an-1鏈?zhǔn)綏o(wú)棧滿(mǎn)

7、問(wèn)題，空間可擴(kuò)充鏈?zhǔn)綏o(wú)棧滿(mǎn)問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作適合于多棧操作BUPT SCSTBUPT3.4.棧的應(yīng)用棧的應(yīng)用v 棧與遞歸過(guò)程棧與遞歸過(guò)程遞歸的含義遞歸的含義 函數(shù)、過(guò)程或者數(shù)據(jù)結(jié)構(gòu)的內(nèi)部又直接或者間接地由自身定義。適合于應(yīng)用遞歸的場(chǎng)合適合于應(yīng)用遞歸的場(chǎng)合 規(guī)模較大的問(wèn)題可以化解為規(guī)模較小的問(wèn)題，且二者處理(或定義)的方式一致； 當(dāng)問(wèn)題規(guī)模降低到一定程度時(shí)是可以直接求解的(終止條件) 例1. 階乘 n!= 1 n=0 n(n-1)! n0BUPT SCSTBUPT例2. n階Hanoi塔問(wèn)題 12.

8、 .nX Y Z12. .nX Y Z12.n-1X Y Zn12.n-1X Y Zn12.n-1nX Y ZBUPT SCSTBUPT寫(xiě)遞歸算法應(yīng)注意的問(wèn)題寫(xiě)遞歸算法應(yīng)注意的問(wèn)題 遞歸算法本身不可以作為獨(dú)立的程序運(yùn)行，需在其它的程序中設(shè)置調(diào)用初值，進(jìn)行調(diào)用； 遞歸算法應(yīng)有出口(終止條件) 例1. 求n！ int Factorial(int n) if (n=0) return(1); return(n*Factorial(n-1);BUPT SCSTBUPT v 例例2. Hanoi塔問(wèn)題塔問(wèn)題 PROCEDURE hanoi( )v 遞歸算法的特點(diǎn)遞歸算法的特點(diǎn) 遞歸算法簡(jiǎn)單明了，直觀易懂

9、 時(shí)間效率低，空間開(kāi)銷(xiāo)大，算法不易優(yōu)化void Hanoi (int n, int x, int y, int z) if (n=1) Move（x，1，z） 出口條件 else Hanoi (n-1, x, z, y); Move (x，n，z); Hanoi (n-1, y, x, z);x y zx y z源源 輔助輔助 目標(biāo)目標(biāo)BUPT SCSTBUPTvoid hanoi(3,a,b,c) if (3=1) move(a,1,c); else hanoi(2,a,c,b); move(a,3,c); hanoi(2,b,a,c); void hanoi(2,a,c,b) if (2=

10、1) move(a,1,b); else hanoi(1,a,b,c); move(a,2,b); hanoi(1,c,a,b); void hanoi(1,a,b,c) if 1=1 move(a,1,c); else void hanoi(1,c,a,b) if (1=1) move(c,1,b); else void hanoi(2,b,a,c) if (2=1) move(b,1,c); else hanoi(1,b,c,a); move(b,2,c); hanoi(1,a,b,c); void hanoi(1,b,c,a) if (1=1) move(b,1,a); else voi

11、d hanoi(1,a,b,c) if (1=1) move(a,1,c); else a b cBUPT SCSTBUPT遞歸算法的實(shí)現(xiàn)原理123s123- 利用棧，棧中每個(gè)元素稱(chēng)為工作記錄，分成三個(gè)部分： 返回地址 實(shí)在參數(shù)表(變參和值參) 局部變量- 發(fā)生調(diào)用時(shí)，保護(hù)現(xiàn)場(chǎng)，即當(dāng)前的工作記錄入棧，然后 轉(zhuǎn)入被調(diào)用的過(guò)程- 一個(gè)調(diào)用結(jié)束時(shí)，恢復(fù)現(xiàn)場(chǎng)，即若棧不空，則退棧，從 退出的返回地址處繼續(xù)執(zhí)行下去BUPT SCSTBUPT遞歸時(shí)系統(tǒng)工作原理示例int Factorial(int n) L1: if (n=0) L2: return(1); L3: return(n*Factorial(n

12、-1); void main() L0: N=Factorial(3); 返回地址返回地址 n Factorial NL0 3 / / L3 3 /L3 2 /L3 1 / 1126BUPT SCSTBUPT遞歸算法的用途 求解遞歸定義的數(shù)學(xué)函數(shù) 在以遞歸方式定義的數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算/操作 可用遞歸方式描述的解決過(guò)程遞歸轉(zhuǎn)換為非遞歸的方法遞歸轉(zhuǎn)換為非遞歸的方法1）采用迭代算法）采用迭代算法 遞歸從頂?shù)降?迭代從底到頂 例：求n！ int fact(int n) m=1; for (i=1;idata); linklist_output(p-next); 使用跳轉(zhuǎn)語(yǔ)句：void linklist_

13、output1(pointer p) 1: if (p!=null) write(p-data); p=p-next; goto 1; 使用循環(huán)語(yǔ)句：void linklist_output2(pointer p) while (p!=nil) write(p-data); p:=p-next; pan-1a 1a0BUPT SCSTBUPT3) 利用棧模擬遞歸通用方法如果是遞歸函數(shù)，需改寫(xiě)為遞歸過(guò)程如果是遞歸函數(shù)，需改寫(xiě)為遞歸過(guò)程 例：求n! void fact(int n; int &f) 0: if (n=0) f=1; else 1: fact(n-1,f); 2: f:=n*f; i

14、nit_stack(s);if (top!=0) stop.f=f; 還原本層變參值 top=top-1; n=stop+1.n; f=stop+1.f; goto stop+1.rd top=top+1; stop.rd=2;stop.n=n; stop.f=f; n=n-1; goto 0; BUPT SCSTBUPT自設(shè)棧模擬系統(tǒng)工作棧自設(shè)棧模擬系統(tǒng)工作棧 改寫(xiě)算法改寫(xiě)算法在程序開(kāi)頭增加棧的初始化語(yǔ)句改寫(xiě)遞歸調(diào)用語(yǔ)句 入棧處理； 確定調(diào)用的參數(shù)值； 轉(zhuǎn)至調(diào)用的開(kāi)始語(yǔ)句改寫(xiě)所有遞歸出口 退棧還原參數(shù)； 轉(zhuǎn)至返回地址處srd n ftopBUPT SCSTBUPTvoid fact(int

15、n, int & f) init_stack(s);0: if (n=0) f=1; 1: top=top+1; stop.rd=2; stop.n=n; stop.f=f; n=n-1; goto 0; 2: f=n*f if (top!=0) stop.f=f; top=top-1; n=stop+1.n; f=stop+1.f; goto stop+1.rd; void fact(int n,int &f) init_stack(s); while (n!=0) top=top+1; stop.n=n; n=n-1; f=1; while (top!=0) top=top-1; n=st

16、op+1.n; f=n*f; 注：此時(shí)可確定棧中只 存放n值即可。BUPT SCSTBUPT 棧的應(yīng)用棧的應(yīng)用2-整型數(shù)簡(jiǎn)單表達(dá)式求值整型數(shù)簡(jiǎn)單表達(dá)式求值前提假設(shè)前提假設(shè) 表達(dá)式語(yǔ)法正確； 表達(dá)式結(jié)束符為#算法思想算法思想 OPTR棧寄存運(yùn)算符 OPND棧寄存操作數(shù) 1)放入起始符#作為OPTR棧底元素 2)依次讀入表達(dá)式字符， 操作數(shù)：進(jìn)OPND棧； 運(yùn)算符：與OPTR.top元素比較優(yōu)先級(jí)后做相應(yīng)操作； 直至讀入#且OPTR棧只剩# 3)OPND棧底所留元素即為所求例例 5+3*(7-2)+11#OPTR OPND#53( 7 - 2+*51520+1131BUPT第三章（第二部分）隊(duì)列第

17、三章（第二部分）隊(duì)列BUPT SCSTBUPT提提 綱綱隊(duì)列的定義1鏈隊(duì)列2循環(huán)隊(duì)列3雙端隊(duì)列4BUPT SCSTBUPT3.5 隊(duì)列的定義隊(duì)列的定義隊(duì)列隊(duì)列是一種特殊的線性表，限定插入和刪除操作分別在表的兩端進(jìn)行。具有先進(jìn)先出先進(jìn)先出(FIFOFirst In First Out)的特點(diǎn)。 a0 a1 ai an-1 隊(duì)頭front隊(duì)尾 rear出隊(duì)出隊(duì)入隊(duì)入隊(duì)BUPT SCSTBUPT定義在隊(duì)列結(jié)構(gòu)上的基本運(yùn)算定義在隊(duì)列結(jié)構(gòu)上的基本運(yùn)算 (1)構(gòu)造空隊(duì)列操作 (2)判隊(duì)空否函數(shù) (3)元素入隊(duì)操作 (4)元素出隊(duì)函數(shù) (5)取隊(duì)頭元素函數(shù) (6) 隊(duì)列置空操作 (7)求隊(duì)中元素個(gè)數(shù)函數(shù)BU

18、PT SCSTBUPTn n 思考：可否用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列？如何實(shí)現(xiàn)？思考：可否用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列？如何實(shí)現(xiàn)？BUPT SCSTBUPT利用兩個(gè)棧利用兩個(gè)棧sl、s2（等容量）模擬一個(gè)隊(duì)列（等容量）模擬一個(gè)隊(duì)列 ,實(shí)現(xiàn)隊(duì)列的插入，刪除以及實(shí)現(xiàn)隊(duì)列的插入，刪除以及判隊(duì)空運(yùn)算判隊(duì)空運(yùn)算 v 棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。初始時(shí)設(shè)棧s1和棧s2均為空。v （1）用棧s1和s2模擬隊(duì)列的輸入：設(shè)s1和s2容量相等。分以下三種情況討論：若s1未滿(mǎn)，則元素入s1棧；若s1滿(mǎn)，s2空，則將s1全部元素退棧，再壓棧入s2，之后元素入s1棧；若s1滿(mǎn)，s2不空（已有出隊(duì)列元素），則不能入隊(duì)。v

19、（2）用棧s1和s2模擬隊(duì)列出隊(duì)（刪除）：若棧s2不空，退棧，即是隊(duì)列的出隊(duì)；若s2為空且s1不空，則將s1棧中全部元素退棧，并依次壓入s2中，s2棧頂元素退棧，這就是相當(dāng)于隊(duì)列的出隊(duì)。若棧s1為空并且s2也為空，隊(duì)列空，不能出隊(duì)。v （3）判隊(duì)空 若棧s1為空并且s2也為空，才是隊(duì)列空。討論：s1和s2容量之和是隊(duì)列的最大容量。其操作是，s1棧滿(mǎn)后，全部退棧并壓棧入s2（設(shè)s1和s2容量相等）。再入棧s1直至s1滿(mǎn)。這相當(dāng)隊(duì)列元素“入隊(duì)”完畢。出隊(duì)時(shí)，s2退棧完畢后，s1棧中元素依次退棧到s2，s2退棧完畢，相當(dāng)于隊(duì)列中全部元素出隊(duì)。 在棧s2不空情況下，若要求入隊(duì)操作，只要s1不滿(mǎn)，就可壓

20、入s1中。若s1滿(mǎn)和s2不空狀態(tài)下要求隊(duì)列的入隊(duì)時(shí)，按出錯(cuò)處理。BUPT SCSTBUPT3.6 鏈隊(duì)列鏈隊(duì)列用單鏈表表示的隊(duì)列類(lèi)型定義：隊(duì)頭指針 + 隊(duì)尾指針data nextfrontrear隊(duì)頭隊(duì)尾BUPT SCSTBUPT用單循環(huán)鏈表定義的隊(duì)列類(lèi)型定義：隊(duì)尾指針data nextrear隊(duì)尾BUPT SCSTBUPT3.7 循環(huán)隊(duì)列循環(huán)隊(duì)列一般用法的順序存儲(chǔ)結(jié)構(gòu)之缺陷一般用法的順序存儲(chǔ)結(jié)構(gòu)之缺陷 出隊(duì)列操作后大量移動(dòng)數(shù)據(jù)或存在“假上溢”現(xiàn)象：即存在空閑空間但無(wú)法入隊(duì)。解決方法解決方法v 平移元素法，當(dāng)發(fā)生假溢出時(shí)，就把整個(gè)隊(duì)列的元素平移到存儲(chǔ)區(qū)的首部，然后再插入新元素。這種方法需移動(dòng)大

21、量的元素，因而效率是很低的。v 循環(huán)隊(duì)列a0a1a2a3a4frontrear空閑空間BUPT SCSTBUPT循環(huán)隊(duì)列循環(huán)隊(duì)列將順序隊(duì)列的存儲(chǔ)區(qū)假想為一個(gè)環(huán)狀空間類(lèi)型定義類(lèi)型定義 一維數(shù)組(隊(duì)列空間) + 頭指針 + 尾指針01m-1m-2frontrear優(yōu)點(diǎn)優(yōu)點(diǎn)：不需要移動(dòng)元素，操作效率高，空間的利用率也很高。typedef structElemtype queueMAX;int front; /*隊(duì)頭指針*/int rear; /*隊(duì)尾指針*/sqqueue;sqqueue *q；BUPT SCSTBUPTBUPT SCSTBUPT 。 思考：循環(huán)隊(duì)列中當(dāng)前元素的個(gè)數(shù)為多少？思考：循環(huán)

22、隊(duì)列中當(dāng)前元素的個(gè)數(shù)為多少？當(dāng)前元素個(gè)數(shù)當(dāng)前元素個(gè)數(shù)n=(rear-front+maxsize)%maxsizeBUPT SCSTBUPT例例假設(shè)以數(shù)組sq8存放循環(huán)隊(duì)列元素,變量front指向隊(duì)頭元素的前一位置,變量rear指向隊(duì)尾元素，如用A和D分別表示入隊(duì)和出隊(duì)操作。請(qǐng)給出：執(zhí)行操作序列A3D1A5D2A1D2A4時(shí)的狀態(tài)。隊(duì)空的初始條件：隊(duì)空的初始條件：front=rear=0；執(zhí)行操作執(zhí)行操作A3后，后，rear=3；/ A3表示三次入隊(duì)操作表示三次入隊(duì)操作執(zhí)行操作執(zhí)行操作D1后，后，front=1；/D1表示一次出隊(duì)操作表示一次出隊(duì)操作執(zhí)行操作執(zhí)行操作A5后，后，rear=0；執(zhí)行

23、操作執(zhí)行操作D2后，后，front=3；執(zhí)行操作執(zhí)行操作A1后，后，rear=1；執(zhí)行操作執(zhí)行操作D2后，后，front=5；執(zhí)行操作執(zhí)行操作A4后，溢出。因?yàn)閳?zhí)行后，溢出。因?yàn)閳?zhí)行A3后，后，rear=4，這時(shí)隊(duì)滿(mǎn)，若再執(zhí)行，這時(shí)隊(duì)滿(mǎn)，若再執(zhí)行A操操作，則出錯(cuò)作，則出錯(cuò)。 BUPT SCSTBUPT3.8 雙端隊(duì)列雙端隊(duì)列雙端隊(duì)列 限定插入和刪除操作在線性表的兩端進(jìn)行?？梢詫⑺闯墒菞５走B在一起的兩個(gè)棧，但它與兩個(gè)棧共享存儲(chǔ)空間是不同的。共享存儲(chǔ)空間中的兩個(gè)棧的棧頂指針是向兩端擴(kuò)展的，因而每個(gè)棧只需一個(gè)指針；而雙端隊(duì)列允許兩端進(jìn)行插入和刪除元素，因而每個(gè)端點(diǎn)必須設(shè)立兩個(gè)指針。BUPT SCS

24、TBUPTv實(shí)際應(yīng)用中的特殊隊(duì)列 輸出受限的雙端隊(duì)列（即一個(gè)端點(diǎn)允許插入和刪除，另一個(gè)端點(diǎn)只允許插入）； 輸入受限的雙端隊(duì)列（即一個(gè)端點(diǎn)允許插入和刪除，另一個(gè)端點(diǎn)只允許刪除）。 如果限定雙端隊(duì)列從某個(gè)端點(diǎn)插入的元素只能從該端點(diǎn)刪除，則雙端隊(duì)列就蛻變?yōu)閮蓚€(gè)棧底相鄰接的棧了。BUPT SCSTBUPT如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作，其結(jié)構(gòu)如下：#define M 隊(duì)列可能達(dá)到的最大長(zhǎng)度typedef struct elemtp dataM; int front,rear; cycqueue; 請(qǐng)寫(xiě)出“從隊(duì)尾刪除”和“從隊(duì)頭插入”的算法。elemtp delqueue ( cycq

25、ueue Q) void enqueue (cycqueue Q, elemtp x)分析分析 用一維數(shù)組 vM實(shí)現(xiàn)循環(huán)隊(duì)列，其中M是隊(duì)列長(zhǎng)度。設(shè)隊(duì)頭指針 front和隊(duì)尾指針rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空，(rear+1)%m=front 為隊(duì)滿(mǎn)。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展，隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展。 BUPT SCSTBUPTelemtp delqueue ( cycqueue Q) /Q是如上定義的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)從隊(duì)尾刪除，若刪除成功，返回被刪除元素，否則給出出錯(cuò)信息。 if (Q.front=Q.rear) printf(“隊(duì)列空”); exit(0); Q.rear=(Q.rear-1+M)%M; /修改隊(duì)尾指針。 return(Q.data(Q.rear+1+M)%M); /返回出隊(duì)元素。BUPT SCSTBUPTvoid enqueue (cycqueue Q, elemtp x)/ Q是順序存儲(chǔ)的循環(huán)隊(duì)列，本算法實(shí)現(xiàn)“從隊(duì)頭插入”元素x。 if (Q.rear=(Q.front-1+M)%M) printf(“隊(duì)滿(mǎn)”); exit(0); Q.dataQ.front=x; /x 入隊(duì)列 Q.front=(Q.front-1+M)%M; /修改隊(duì)頭指針。 BUPT SC