隊列的基本操作及應用

1、2005.1南京南京l隊列（隊列（queue）簡稱簡稱隊隊，是一種運算受限，是一種運算受限的的線性表線性表，其限制是僅允許在表的一端，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除。進行插入，而在表的另一端進行刪除。我們把進行插入的一端稱作我們把進行插入的一端稱作隊尾隊尾（rear），），進行刪除的一端稱作進行刪除的一端稱作隊頭隊頭（front）。）。l隊列也稱作隊列也稱作先進先出表先進先出表（First In First Out，簡稱簡稱FIFO表表）。）。l隊空：當隊列中沒有元素時稱為空隊列；隊空：當隊列中沒有元素時稱為空隊列；l隊滿：當隊列中單元全部被占用；隊滿：當隊列中單元全

2、部被占用；l進隊：向隊列中插入新元素；進隊：向隊列中插入新元素；l出隊：從隊列中刪除元素；出隊：從隊列中刪除元素；l（假）溢出（假）溢出：隊尾指針指向最后一個位：隊尾指針指向最后一個位置，但隊頭前面仍有空閑的單元可被利置，但隊頭前面仍有空閑的單元可被利用。用。front=rear=-1 front=-1 rear=2 front=5 rear=8 front=5 rear=9front=rear=-1 front=-1 rear=2 front=5 rear=8 front=5 rear=9 (a) (a) 空隊空隊 ( (b)b)有有3 3個元素個元素 ( (c)c)一般情況一般情況 ( (

3、d) d) 假溢出現象假溢出現象1 1順序存儲順序存儲順序存儲的隊稱為順序存儲的隊稱為順序隊列順序隊列type queue=recordtype queue=record data:array0. data:array0.maxsizemaxsize-1 of -1 of elemtypeelemtype front, rear : integer ;front, rear : integer ; end; end; front front指向隊列中第一個元素的指向隊列中第一個元素的前一個前一個單元；單元； rear rear指向隊列中最后一個元素單元。指向隊列中最后一個元素單元。2鏈式存儲鏈

4、式存儲鏈式存儲的隊列稱為鏈式存儲的隊列稱為鏈隊鏈隊（1 1）初始化：設定）初始化：設定Q Q為一空隊列：為一空隊列：procedure procedure iniqueueiniqueue( (varvar Q:queue); Q:queue);beginbeginQ.front:=-1;Q.front:=-1;Q.rear:=-1;Q.rear:=-1;end;end;（2 2）判隊列空：若隊列）判隊列空：若隊列Q Q為空，則返回值為空，則返回值truetrue，否則返回值否則返回值falsefalse：function function qemptyqempty(Q:queue):Bool

5、ean;(Q:queue):Boolean;beginbegin qemptyqempty:=(Q.front=Q.rear):=(Q.front=Q.rear) end; end;（3 3）判隊滿：若隊列滿，則返回值）判隊滿：若隊列滿，則返回值truetrue，否則返回值否則返回值falsefalse：function function qfullqfull(Q:queue):Boolean;(Q:queue):Boolean;beginbegin QfullQfull:=:=（Q.rearQ.rearmaxsizemaxsize-1);-1); end; end;（4 4）元素進隊：若隊列

6、）元素進隊：若隊列Q Q不滿時，把元素不滿時，把元素X X插入插入到隊列到隊列Q Q的隊尾，否則返回信息的隊尾，否則返回信息“Overflow”O(jiān)verflow”：procedure procedure inqueueinqueue( (varvar Q:queue;X: Q:queue;X:elemtypeelemtype););beginbegin if if qfullqfull(Q)(Q) then then writelnwriteln(Overflow)(Overflow) else begin else begin Q.rear:=Q.rear+1; Q.rear:=Q.rear

7、+1; Q.dataQ.rear:=X; Q.dataQ.rear:=X; end endend;end;（5 5）元素出隊：若隊列）元素出隊：若隊列Q Q不空，則把隊頭元素刪不空，則把隊頭元素刪除并返回值給除并返回值給X X，否則輸出信息否則輸出信息“Underflow”Underflow”：procedure procedure delqueuedelqueue( (varvar Q:queue; Q:queue;varvar X: X:elemtypeelemtype););beginbegin if if qemptyqempty(Q)(Q) then then writelnwrit

8、eln(Underflow)(Underflow) else begin else begin Q.front:=Q.front+1; Q.front:=Q.front+1; X:=Q.dataQ.front; X:=Q.dataQ.front; end; end;end;end;（6 6）取隊頭元素：若隊列不空，返回隊頭）取隊頭元素：若隊列不空，返回隊頭元素的值，否則返回信息元素的值，否則返回信息“Underflow”Underflow”：function function getheadgethead(Q:queue):(Q:queue):elemtypeelemtype; ;beginb

9、egin if if qemptyqempty(Q)(Q) then then writelnwriteln(Underflow)(Underflow) else else getheadgethead:=Q.dataQ.front+1;:=Q.dataQ.front+1;end;end;l所謂循環(huán)隊列，就所謂循環(huán)隊列，就是將隊列存儲空間是將隊列存儲空間的最后一個位置繞的最后一個位置繞到第一個位置，形到第一個位置，形成邏輯上的環(huán)狀空成邏輯上的環(huán)狀空間，供隊列循環(huán)使間，供隊列循環(huán)使用，循環(huán)隊列的定用，循環(huán)隊列的定義如隊列。義如隊列。（1 1）初始化：）初始化：procedure procedur

10、e iniqueueiniqueue( (varvar Q:queue); Q:queue);beginbegin Q.front:=0; Q.front:=0; Q.rear:=0; Q.rear:=0; end; end;（2 2）判隊列空：）判隊列空：function function qemptyqempty(Q:queue):Boolean;(Q:queue):Boolean;beginbegin qemptyqempty:=(Q.front=Q.rear):=(Q.front=Q.rear) end; end;（3 3）判隊滿：）判隊滿：function function qful

11、lqfull(Q:queue):Boolean;(Q:queue):Boolean;beginbegin qfullqfull:=(Q.rear+1) mod :=(Q.rear+1) mod maxsizemaxsize=Q.front);=Q.front); end; end;（4 4）元素進隊：）元素進隊：procedure procedure inqueueinqueue( (varvar Q:queue;X: Q:queue;X:elemtypeelemtype););beginbegin if if qfullqfull(Q)(Q) then then writelnwriteln

12、(Overflow)(Overflow) else begin else begin Q.rear:=(Q.rear+1) mod Q.rear:=(Q.rear+1) mod maxsizemaxsize; ; Q.dataQ.rear:=X; Q.dataQ.rear:=X; end endend;end;（5 5）元素出隊：）元素出隊：procedure procedure delqueuedelqueue( (varvar Q:queue; Q:queue;varvar X: X:elemtypeelemtype););beginbegin if if qemptyqempty(Q)(

13、Q) then then writelnwriteln(Underflow)(Underflow) else begin else begin Q.front:=(Q.front+1) mod Q.front:=(Q.front+1) mod maxsizemaxsize; ; X:=Q.dataQ.front; X:=Q.dataQ.front; end; end;end;end;（6 6）取隊頭元素：）取隊頭元素：function function getheadgethead(Q:queue):(Q:queue):elemtypeelemtype; ;beginbegin if if q

14、emptyqempty(Q)(Q) then then writelnwriteln(Underflow)(Underflow) else else getheadgethead:=Q.data(Q.front+1) mod :=Q.data(Q.front+1) mod maxsizemaxsize;end;end;l解決主機與外部設備之間速度不匹配的解決主機與外部設備之間速度不匹配的問題（如：主機與打印機，設置一個打問題（如：主機與打印機，設置一個打印數據緩沖區(qū)）；印數據緩沖區(qū)）；l解決由多用戶引起的資源競爭問題（如：解決由多用戶引起的資源競爭問題（如：CPUCPU資源的競爭，操作系統按照

15、每個請求資源的競爭，操作系統按照每個請求的先后順序，排成一個隊列）。的先后順序，排成一個隊列）。例題例題1：1995年高中組基礎題第年高中組基礎題第4 題，從題，從入口（入口（1）到出口（）到出口（17）的可行路線圖中，）的可行路線圖中，數字標號表示關卡：數字標號表示關卡：現將上面的路線圖，按記錄結構存儲如下現將上面的路線圖，按記錄結構存儲如下 ： 請設計一種能從存儲數據中求出從入口到請設計一種能從存儲數據中求出從入口到出口經過最少關卡路徑的算法。出口經過最少關卡路徑的算法。 【問題分析與答案】【問題分析與答案】 該題是一個路徑搜索問題，根據圖示，從該題是一個路徑搜索問題，根據圖示，從入口（入

16、口（1 1）到出口（）到出口（1717）可以有多種途徑，其）可以有多種途徑，其中最短的路徑只有一條，那么如何找最短路中最短的路徑只有一條，那么如何找最短路徑是問題的關鍵；徑是問題的關鍵； 根據題意，用一維數組存儲各關卡號根據題意，用一維數組存儲各關卡號（設（設NONO），），用另一個數組存儲訪問到某關卡用另一個數組存儲訪問到某關卡號的號的前趨卡號所在數組單元下標前趨卡號所在數組單元下標（設（設PREPRE）；）； 由于本題是一個典型的圖的遍歷問題，由于本題是一個典型的圖的遍歷問題，此題采用的是圖的廣度優(yōu)先遍歷算法，并此題采用的是圖的廣度優(yōu)先遍歷算法，并利用隊列的方式存儲頂點之間的聯系。即利用隊

17、列的方式存儲頂點之間的聯系。即訪問一個點，將其后繼結點入隊，并存儲訪問一個點，將其后繼結點入隊，并存儲它的它的前趨結點所在單元下標前趨結點所在單元下標，直到最后從，直到最后從（1717）點出口；）點出口； 從最后出口的關卡號（從最后出口的關卡號（1717）開始回訪）開始回訪它的前趨卡號，則回返的搜索路徑便是最它的前趨卡號，則回返的搜索路徑便是最短路徑（跳過許多不必要搜索的關卡）；短路徑（跳過許多不必要搜索的關卡）； 從列表中可以看出出口關卡號（從列表中可以看出出口關卡號（1717）的）的被訪問路徑最短的是：被訪問路徑最短的是：（1717）（1616）（1919）（1818）（1 1）開始開始

18、根據題意，要求從存儲數據中寫出從入根據題意，要求從存儲數據中寫出從入口到出口的最少關卡路徑的算法是：口到出口的最少關卡路徑的算法是：從隊列的最后一個關卡號開始，依次回訪從隊列的最后一個關卡號開始，依次回訪它的前驅頂點，所得到的路徑即為最短路它的前驅頂點，所得到的路徑即為最短路徑。徑。算法如下：算法如下：i:=1;i:=1;while noi17 dowhile noi17 do i:=i+1 i:=i+1repeatrepeat write(,noi, ); write(,noi, ); write(- ); write(- ); i:=prei; i:=prei;until i=0;unti

19、l i=0; 例題例題2 2：有：有1010升油在升油在1010升的容器中，另升的容器中，另有兩個有兩個7 7升和升和3 3升的空容器，現要求用升的空容器，現要求用這三個容器倒油，使得最后在這三個容器倒油，使得最后在1010升和升和7 7升的容器中各有升的容器中各有5 5升油。升油。提示：三個容器可以看作三個變量提示：三個容器可以看作三個變量 C10C10，C7C7，C3C3，每次倒油的可能性只有每次倒油的可能性只有如下六種情況：如下六種情況： C10C10向向C7C7倒油倒油 C10C10向向C3C3倒油倒油 C7C7向向C10C10倒油倒油 C7C7向向C3C3倒油倒油 C3C3向向C10

20、C10倒油倒油 C3C3向向C7C7倒油倒油（1 1）從一個容器的狀態(tài)（三個容器中油的）從一個容器的狀態(tài)（三個容器中油的容量）看，雖然有可能經過上述六種倒油的容量）看，雖然有可能經過上述六種倒油的方法產生六種容器狀態(tài)，但實際上這六種新方法產生六種容器狀態(tài)，但實際上這六種新產生的容器狀態(tài)，許多是已經出現過的狀態(tài)。產生的容器狀態(tài)，許多是已經出現過的狀態(tài)。例如初始狀態(tài)（例如初始狀態(tài)（10,0,010,0,0）表示）表示 C10=10C10=10，C7=0C7=0，C3=0C3=0，經過上述六種倒油方法只能產經過上述六種倒油方法只能產生出兩種新的容器狀態(tài)（生出兩種新的容器狀態(tài)（3,7,03,7,0），

21、表示），表示C10C10向向C7C7倒油的結果和（倒油的結果和（7,0,37,0,3），表示），表示C10C10向向C3C3倒油的結果。如果再增加應該表示新容器狀倒油的結果。如果再增加應該表示新容器狀態(tài)是由什么狀態(tài)產生的指示態(tài)是由什么狀態(tài)產生的指示prepre，那么用這那么用這三個容器倒油的過程就可以用隊列的方法來三個容器倒油的過程就可以用隊列的方法來實現了。實現了。（2 2）隊列可以理解為一個數組，數組元素是如下記錄：）隊列可以理解為一個數組，數組元素是如下記錄： RECORDRECORD C10,C7,C3, pre: integer;C10,C7,C3, pre: integer; EN

22、D; END;數組下標為容器狀態(tài)號。下面是倒油過程的隊列：數組下標為容器狀態(tài)號。下面是倒油過程的隊列：當倒油產生出第當倒油產生出第1919個容器狀態(tài)時已達到了題解的個容器狀態(tài)時已達到了題解的目的。這時只要根據目的。這時只要根據prepre中的狀態(tài)號中的狀態(tài)號1717可以回溯到可以回溯到第第1717個容器狀態(tài)的個容器狀態(tài)的prepre值為值為1515，依次可再獲得，依次可再獲得1313，1111，9 9，7 7，5 5，2 2，1 1容器狀態(tài)號，從而即可得到本容器狀態(tài)號，從而即可得到本題的倒油過程（共倒題的倒油過程（共倒9 9次），而且是最少的倒油次數。次），而且是最少的倒油次數。注意注意, ,

23、從一個容器中向另一個容器中倒油從一個容器中向另一個容器中倒油, ,人人操作是很直觀的操作是很直觀的, ,對編程來說則必須考慮對編程來說則必須考慮: :1) 1) 有沒有油可倒有沒有油可倒? ?2) 2) 究竟倒多少究竟倒多少? ?可能要全部倒入另一容器可能要全部倒入另一容器, ,也可能只要倒一部分另一容器已經滿了。也可能只要倒一部分另一容器已經滿了。例題例題3 3：迷宮問題：迷宮問題右圖是一個簡單的右圖是一個簡單的迷宮，迷宮圖中陰影部迷宮，迷宮圖中陰影部分是不通的路徑，處于分是不通的路徑，處于迷宮中的每個位置都可迷宮中的每個位置都可以向以向8 8個方向探索著按個方向探索著按可行路徑前進。迷宮圖

24、可行路徑前進。迷宮圖中陰影部分是不通的路徑，處于迷宮中的每個中陰影部分是不通的路徑，處于迷宮中的每個位置都可以向位置都可以向8 8個方向探索著按可行路徑前進。個方向探索著按可行路徑前進。假設出口位置在最右下角（假設出口位置在最右下角（6 6，8 8），入口在最），入口在最左上角（左上角（1 1，1 1），試問能否設計出尋找一個從），試問能否設計出尋找一個從入口到出口的最短路徑的算法呢？入口到出口的最短路徑的算法呢？ 圖中的（圖中的（1 1，1 1）（2 2，2 2）（3 3，3 3）（3 3，4 4）（4 4，5 5）（4 4，6 6）（5 5，7 7）（6 6，8 8）便是所求的一個這種路徑

25、。）便是所求的一個這種路徑?！舅惴ǚ治觥俊舅惴ǚ治觥?為了設計求走迷宮的路徑，首先要對為了設計求走迷宮的路徑，首先要對迷迷宮進行描述，一種很宮進行描述，一種很自然的想法是把迷宮自然的想法是把迷宮變?yōu)樽優(yōu)? 0，1 1值的二維數值的二維數組，對上例而言可化組，對上例而言可化為：為：探索路徑的選擇可描述為：探索路徑的選擇可描述為：這樣一來，迷宮中每個位置可探索的情況這樣一來，迷宮中每個位置可探索的情況就分為：就分為： 只有三個探索方向的位置：如（只有三個探索方向的位置：如（1 1，1 1）；）； 有五個探索方向的位置：如（有五個探索方向的位置：如（3 3，1 1）；）； 有八個探索方向的位置：如（

26、有八個探索方向的位置：如（3 3，2 2）；）； 能否不分情況統一按八種情況探索前能否不分情況統一按八種情況探索前進的路徑呢？只要把原始迷宮數據修正如進的路徑呢？只要把原始迷宮數據修正如下即可達到目的（外加一圈不通的圍墻）；下即可達到目的（外加一圈不通的圍墻）；Mg:array0.m+1,0.n+1 of integer;Mg:array0.m+1,0.n+1 of integer;探索方向可用探索方向可用x x，y y的增量組成數組：的增量組成數組：ZlZl:array1.8,1.2 of :array1.8,1.2 of 1.11.1 第二個要解決的問題應當考慮探索前進路第二個要解決的問題

27、應當考慮探索前進路徑時如何把探索的蹤跡記錄下來，記錄的蹤跡徑時如何把探索的蹤跡記錄下來，記錄的蹤跡一般應包括來處和當前位置，現設計如下順序一般應包括來處和當前位置，現設計如下順序隊列來完成探索路徑的蹤跡：隊列來完成探索路徑的蹤跡：type type sqtypesqtype=array1.r of record=array1.r of record x,y:integer; x,y:integer;當前坐標當前坐標 pre:0.r;pre:0.r; 前趨位置前趨位置 end;end;這里的這里的r r一般一般=m mn n，即迷宮的最大空位數目即迷宮的最大空位數目 var var sq: sq

28、:sqtypesqtype; ; 例如：從（例如：從（1 1，1 1）入口進入到達（）入口進入到達（3 3，3 3），往下探索時隊列），往下探索時隊列sqsq的情況：的情況： 注意，前趨采用了僅登記前趨在隊列中的序注意，前趨采用了僅登記前趨在隊列中的序號（前趨是由號（前趨是由frontfront指針指示的數據元素）；指針指示的數據元素）； 為了防止被探索過的蹤跡被重復探索，被探為了防止被探索過的蹤跡被重復探索，被探索到的可通行路徑需在迷宮中做上標記，這里采索到的可通行路徑需在迷宮中做上標記，這里采用在迷宮數據中將用在迷宮數據中將0 0換成換成-1-1的方法實現，這樣在走的方法實現，這樣在走出迷

29、宮時可以再出迷宮時可以再把迷宮數據還原把迷宮數據還原為原來的樣子。為原來的樣子。例如上例，探索例如上例，探索到位置（到位置（3 3，3 3）的迷宮數據為：的迷宮數據為： 最后根據隊列最后根據隊列sqsq中的存儲信息和指針位中的存儲信息和指針位置，即可鏈接成從迷宮入口到出口的最短路置，即可鏈接成從迷宮入口到出口的最短路徑。就上例而言，徑。就上例而言，sqsq隊列的最后情況為：隊列的最后情況為： 當當rearrear指針指示的數據元素已到達出口指針指示的數據元素已到達出口（6 6，8 8）時，根據）時，根據rearrear所據元素的前趨序號所據元素的前趨序號即可獲得所要的走迷宮的最短路徑（回溯）。

30、即可獲得所要的走迷宮的最短路徑（回溯）。例題例題4 4：產生數（：產生數（20022002年年NOIPNOIP普及組第普及組第3 3題）題） 給出一個整數給出一個整數n n（n2000n2000）和和k k個變換規(guī)則（個變換規(guī)則（k15k15） 規(guī)則：規(guī)則： 1 1個數字可以變換成另個數字可以變換成另1 1個數字；個數字； 規(guī)則中，右邊的數字不能為零。規(guī)則中，右邊的數字不能為零。 例如：例如：n=234n=234，k=2k=2規(guī)則為規(guī)則為 2 5 2 5 3 6 3 6 上面的整數上面的整數234234經過變換后可能產生出的整數為經過變換后可能產生出的整數為（包括原數）（包括原數） 234 2

31、34534534264264564564 共共4 4種不同的產生數種不同的產生數 求經過任意次的變換（求經過任意次的變換（0 0次或多次），能產生出多次或多次），能產生出多少個不同的整數。少個不同的整數。 僅要求輸出不同整數個數。僅要求輸出不同整數個數?！締栴}分析】【問題分析】 本題考察了同學們三方面的能力：本題考察了同學們三方面的能力： 數的表示，如何處理；數的表示，如何處理； 轉換規(guī)則如何表示；轉換規(guī)則如何表示； 隊列的應用，包括入隊、出隊以及隊的查找。隊列的應用，包括入隊、出隊以及隊的查找。注意點：注意點： 數以字符串的形式輸入，為了計算方便，經過數以字符串的形式輸入，為了計算方便，經過

32、類型轉換存入整型數組中；類型轉換存入整型數組中； 對數的比較也很困難，只能逐位比較，處理時對數的比較也很困難，只能逐位比較，處理時用一個隊列用一個隊列q q，開始時隊列開始時隊列q q中只有中只有n n。【數據結構】【數據結構】 str:string; 輸入開始的數輸入開始的數 y,y1:array1.4 of 0.9; 工作單元工作單元 q:array1.2000,1.4 of 0.9; 隊列，設長度隊列，設長度2000 front,rear:integer; 存入和取出指針存入和取出指針 p:array1.20,1.2 of 0.9; 存儲變換規(guī)則，即存儲變換規(guī)則，即pi,1pi,2【算法

33、流程】算法流程】 front:=1; rear:=1; while front=rear do begin q出隊出隊y; 根據規(guī)則，擴展根據規(guī)則，擴展y，生成新數生成新數xi 逐個檢查逐個檢查xi，如果如果xi不在隊列不在隊列q中，則中，則xi入隊，否則不入隊；入隊，否則不入隊； front:=front+1; end; 輸出輸出front值，即為所求的個數。值，即為所求的個數。l寬度優(yōu)先搜索在樹中又叫按層次遍歷。對于樹而言，寬度優(yōu)先搜索在樹中又叫按層次遍歷。對于樹而言，寬度優(yōu)先搜索的思路可以描述為：訪問根結點，依次寬度優(yōu)先搜索的思路可以描述為：訪問根結點，依次訪問根結點的每一個子結點（第二

34、層結點），再通過訪問根結點的每一個子結點（第二層結點），再通過這些結點訪問第三層結點這些結點訪問第三層結點。l寬度優(yōu)先搜索與深度優(yōu)先搜索相比，時間復雜度都是寬度優(yōu)先搜索與深度優(yōu)先搜索相比，時間復雜度都是相同的，不同的僅僅在于結點訪問的順序不同。它們相同的，不同的僅僅在于結點訪問的順序不同。它們在完全遍歷的問題上應該說差不多，但是在有些問題在完全遍歷的問題上應該說差不多，但是在有些問題上，比如求最優(yōu)解，有時寬度優(yōu)先搜索較深度優(yōu)先搜上，比如求最優(yōu)解，有時寬度優(yōu)先搜索較深度優(yōu)先搜索好，如倒酒問題。為了求一個最優(yōu)解，如果使用深索好，如倒酒問題。為了求一個最優(yōu)解，如果使用深度優(yōu)先搜索并不能保證找到的解最

35、優(yōu)，只有搜索完整度優(yōu)先搜索并不能保證找到的解最優(yōu)，只有搜索完整棵樹，找到所有解，再比較它們的優(yōu)劣，才能從中求棵樹，找到所有解，再比較它們的優(yōu)劣，才能從中求出最優(yōu)解，這顯然不如寬度優(yōu)先搜索簡單。出最優(yōu)解，這顯然不如寬度優(yōu)先搜索簡單。l一般說來寬度優(yōu)先搜索可以利用隊列實現，主要用一般說來寬度優(yōu)先搜索可以利用隊列實現，主要用于解決求一種狀態(tài)通過幾種規(guī)定的操作以最少次數于解決求一種狀態(tài)通過幾種規(guī)定的操作以最少次數變換到另一種狀態(tài)的問題。變換到另一種狀態(tài)的問題。l下面是利用隊列搜索的一般步驟：下面是利用隊列搜索的一般步驟：（1）初始狀態(tài)入隊；）初始狀態(tài)入隊；（2）i:=1；（3）對隊頭的狀態(tài)進行第對隊頭的狀態(tài)進行第i種操作，存儲結果；種操作，存儲結果；（4）檢查結果是否出現過，若未出現過，則此結果）檢查結果是否出現過，若未出現過，則此結果進隊，記下此結果及其前趨；進隊，記下此結果及其前趨；（5）若結果即為所求，至步驟（）若結果即為所求，至步驟（7）；）；（6）若）若i=n，隊列第一