佇列的基本操作及應用
【教學目的】
（1）掌握佇列的定義及佇列的儲存結構（順序儲存、鏈式儲存）；
（2）掌握佇列的基本操作運算：建佇列、插入、刪除、佇列空等；
（3）掌握迴圈佇列的概念及運算；
（4）能夠利用佇列解決一些實際問題：寬度優先搜尋演算法
【教學重點】
綜合運用佇列結構解決實際問題。
【教學過程】
一、佇列的定義
前面所講的棧是一種後進先出的資料結構，而在實際問題中還經常使用一種「先進先出」 （fifo―first in first out）的資料結構：即插入在表一端進行，而刪除在表的另一端進行，我們將這種資料結構稱為隊或佇列，把允許插入的一端叫隊尾（rear），把允許刪除的一端叫隊頭（front）。如圖1所示是乙個有5 個元素的佇列。
入隊的順序依次為a1、a2、a3、a4、a5，出隊時的順序將依然是a1、a2、a3、a4、a5。
顯然，佇列也是一種運算受限制的線性表，所以又叫先進先出表。
在日常生活中佇列的例子很多，如排隊買東西，排頭的買完後走掉，新來的排在隊尾。
二、基本術語
（1）隊空：當佇列中沒有元素時稱為空佇列；
（2）隊滿：當佇列中單元全部被占用；
（3）進隊：向佇列中插入新元素；
（4）出隊：從佇列中刪除元素；
（5）（假）溢位：隊尾指標指向最後乙個位置，但隊頭前面仍有空閒的單元可被利用。
三、佇列操作示意圖
front=rear=－1 front=－1 rear=2 front=5 rear=8 front=5 rear=9
(a) 空隊 (b)有3個元素 (c)一般情況 (d) 假溢位現象
四、佇列的儲存結構
與線性表、棧類似，佇列也有順序儲存和鏈式儲存兩種儲存方法。
1．順序儲存
順序儲存的佇列稱為順序佇列。因為佇列的隊頭和隊尾都是活動的，因此，除了佇列的資料區外還有隊頭、隊尾兩個指標。順序佇列的型別定義如下：
type queue=record
data : array[0..maxsize-1] of elemtype
front, rear : integer ;
end;
front指向佇列中第乙個元素的前乙個單元；rear指向佇列中最後乙個元素的單元。
2．鏈式儲存
鏈式儲存的佇列稱為鏈隊。和鏈棧類似，用單鏈表來實現鏈隊，根據隊的fifo原則，為了操作上的方便，我們分別需要乙個頭指標和尾指標，如圖2所示。
五、佇列的基本運算
（1）初始化：設定q為一空佇列：
procedure iniqueue(var q:queue);
begin
end;
（2）判佇列空：若佇列q為空，則返回值true，否則返回值false：
function qempty(q:queue):boolean;
begin
qempty:=(
end;
（3）判隊滿：若佇列滿，則返回值true，否則返回值false：
function qfull(q:queue):boolean;
begin
qfull:=（
end;
（4）元素進隊：若佇列q不滿時，把元素x插入到佇列q的隊尾，否則返回資訊「overflow」：
procedure inqueue(var q:queue;x:elemtype);
begin
if qfull(q)
then writeln(『overflow』)
else begin
end end;
（5）元素出隊：若佇列q不空，則把隊頭元素刪除並返回值給x，否則輸出資訊「underflow」：
procedure delqueue(var q:queue;var x:elemtype);
begin
if qempty(q)
then writeln(『underflow』)
else begin
x:=end;
end;
（6）取隊頭元素：若佇列不空，返回隊頭元素的值，否則返回資訊「underflow」：
function gethead(q:queue):elemtype;
begin
if qempty(q)
then writeln(『underflow』)
else gethead:=
end;
六、迴圈佇列
所謂迴圈佇列，就是將佇列儲存空間的最後乙個位置繞到第乙個位置，形成邏輯上的環狀空間，供佇列迴圈使用，迴圈佇列的定義如佇列。
當儲存空間的最後乙個位置已被使用而要進行入隊運算時，只要儲存空間第乙個位置空閒，便可將元素加入到第乙個位置，即將儲存空間的第乙個位置作為隊尾。採用首尾相接的迴圈佇列結構後，可以有效地解決假溢位的問題，避免資料元素的移動。
七、迴圈佇列的基本運算
（1）初始化：設定q為一空佇列：
procedure iniqueue(var q:queue);
begin
end;
（2）判佇列空：若佇列q為空，則返回值true，否則返回值false：
function qempty(q:queue):boolean;
begin
qempty:=(
end;
（3）判隊滿：若佇列滿，則返回值true，否則返回值false：
function qfull(q:queue):boolean;
begin
qfull:=(( mod maxsize=
end;
（4）元素進隊：若佇列q不滿時，把元素x插入到佇列q的隊尾，否則返回資訊「overflow」：
procedure inqueue(var q:queue;x:elemtype);
begin
if qfull(q)
then writeln(『overflow』)
else begin
mod maxsize;
end end;
（5）元素出隊：若佇列q不空，則把隊頭元素刪除並返回值給x，否則輸出資訊「underflow」：
procedure delqueue(var q:queue;var x:elemtype);
begin
if qempty(q)
then writeln(『underflow』)
else begin
mod maxsize;
x:=end;
end;
（6）取隊頭元素：若佇列不空，返回隊頭元素的值，否則返回資訊「underflow」：
function gethead(q:queue):elemtype;
begin
if qempty(q)
then writeln(『underflow』)
else gethead:= mod maxsize];
end;
八、佇列的應用
佇列在電腦科學領域中所起的作用：
1、解決主機與外部裝置之間速度不匹配的問題（如：主機與印表機，設定乙個列印資料緩衝區）；
2、解決由多使用者引起的資源競爭問題（如：cpu資源的競爭，作業系統按照每個請求的先後順序，排成乙個佇列）。
九、典型例題
例題1：2023年高中組基礎題第4 題，從入口（1）到出口（17）的可行路線圖中，數字標號表示關卡：
現將上面的路線圖，按記錄結構儲存如下 ：
請設計一種能從儲存資料中求出從入口到出口經過最少關卡路徑的演算法。
【問題分析與答案】
① 該題是乙個路徑搜尋問題，根據圖示，從入口（1）到出口（17）可以有多種途徑，其中最短的路徑只有一條，那麼如何找最短路徑是問題的關鍵；
② 根據題意，用一維陣列儲存各關卡號（設no），用另乙個陣列儲存訪問到某關卡號的前趨卡號所在陣列單元下標（設pre）；
③ 由於本題是乙個典型的圖的遍歷問題，此題採用的是圖的廣度優先遍歷演算法，並利用佇列的方式儲存頂點之間的聯絡。即訪問乙個點，將其後繼結點入隊，並儲存它的前趨結點所在單元下標，直到最後從（17）點出口；
④ 從最後出口的關卡號（17）開始回訪它的前趨卡號，則回返的搜尋路徑便是最短路徑（跳過許多不必要搜尋的關卡）；
⑤ 從列表中可以看出出口關卡號（17）的被訪問路徑最短的是：
（17）←（16）←（19）←（18）←（1）←開始
⑥ 根據題意，要求從儲存資料中寫出從入口到出口的最少關卡路徑的演算法是：
從佇列的最後乙個關卡號開始，依次回訪它的前驅頂點，所得到的路徑即為最短路徑。
演算法如下：
i:=1;
while no[i]<>17 do
i:=i+1
repeat
write(『(『,no[i],』)』);
write(『<-『);
i:=pre[i];
until i=0;
例題2：有10公升油在10公升的容器中，另有兩個7公升和3公升的空容器，現要求用這三個容器倒油，使得最後在10公升和7公升的容器中各有5公升油。
【演算法分析】
提示：三個容器可以看作三個變數 c10，c7，c3，每次倒油的可能性只有如下六種情況：
① c10向c7倒油 ② c10向c3倒油 ③ c7向c10倒油
④ c7向c3倒油 ⑤ c3向c10倒油 ⑥ c3向c7倒油
（1）從乙個容器的狀態（三個容器中油的容量）看，雖然有可能經過上述六種倒油的方法產生六種容器狀態，但實際上這六種新產生的容器狀態，許多是已經出現過的狀態。例如初始狀態（10,0,0）表示 c10=10，c7=0，c3=0，經過上述六種倒油方法只能產生出兩種新的容器狀態（3,7,0），表示c10向c7倒油的結果和（7,0,3），表示c10向c3倒油的結果。如果再增加應該表示新容器狀態是由什麼狀態產生的指示pre，那麼用這三個容器倒油的過程就可以用佇列的方法來實現了。
鏈式料線規範
精益求精大牧人 目錄一 使用者須知2 二 安全注意事項2 三 安裝工具與人員2 四 系統簡介3 五 安裝4 六 除錯9 七 使用說明9 八 日常保養11 九 維修方法11 一 使用者須知 1.本系統是通過特製鏈條在驅動電機的拖動下，在料槽裡運動，拖動料箱裡的飼料，到達料槽的各處，達到均勻餵料。可以滿...
鏈式發展聚力公升級
湯陰縣產業集聚工作綜述 地處中原腹地的湯陰縣有諸多令人羨慕的光環 國家新型工業化產業示範基地 全國食品工業強縣 全國模範勞動關係和諧工業園區 河南省迴圈經濟試點單位 河南省承接產業轉移示範區 河南省高新技術特色產業基地 河南省發展又好又快產業集聚區 2010中原十大活力產業集聚區 河南省戰略新興產業...
佇列基本概念 迴圈佇列
線性結構的兩種常見應用 佇列定義 一種可以實現 先進先出 的儲存結構，即 一端入，一端出 隊首 front 出隊，隊尾 rear 入隊 注 若front指向隊首，則rear指向隊尾最後乙個有效元素的下乙個元素 若rear指向隊尾，則front指向隊首第乙個有效元素的下乙個元素 分類 鏈式佇列 用鍊錶...