佇列[常用數據結構之一]

基本信息

• 中文名：佇列

• 含義：常用數據結構之一
• 套用：計算機

簡介

佇列是一種特殊的線性表，特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，佇列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。佇列中沒有元素時，稱為空佇列。

佇列的數據元素又稱為佇列元素。在佇列中插入一個佇列元素稱為入隊，從佇列中刪除一個佇列元素稱為出隊。因為佇列只允許在一端插入，在另一端刪除，所以只有最早進入佇列的元素才能最先從佇列中刪除，故佇列又稱為先進先出（FIFO—first in first out）線性表。

順序佇列

建立順序佇列結構必須為其靜態分配或動態申請一片連續的存儲空間，並設定兩個指針進行管理。一個是隊頭指針front，它指向隊頭元素；另一個是隊尾指針rear，它指向下一個入隊元素的存儲位置，如圖所示

佇列[常用數據結構之一]

每次在隊尾插入一個元素是，rear增1；每次在隊頭刪除一個元素時，front增1。隨著插入和刪除操作的進行，佇列元素的個數不斷變化，佇列所占的存儲空間也在為佇列結構所分配的連續空間中移動。當front=rear時，佇列中沒有任何元素，稱為空佇列。當rear增加到指向分配的連續空間之外時，佇列無法再插入新元素，但這時往往還有大量可用空間未被占用，這些空間是已經出隊的佇列元素曾經占用過得存儲單元。

順序佇列中的溢出現象：

（1） "下溢"現象：當佇列為空時，做出隊運算產生的溢出現象。“下溢”是正常現象，常用作程式控制轉移的條件。

（2）"真上溢"現象：當佇列滿時，做進棧運算產生空間溢出的現象。“真上溢”是一種出錯狀態，應設法避免。

（3）"假上溢"現象：由於入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當佇列中實際的元素個數遠遠小於向量空間的規模時，也可能由於尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為"假上溢"現象。

循環佇列

在實際使用佇列時，為了使佇列空間能重複使用，往往對佇列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1 時超出了所分配的佇列空間，就讓它指向這片連續空間的起始位置。自己真從MaxSize-1增1變到0，可用取余運算rear%MaxSize和front%MaxSize來實現。這實際上是把佇列空間想像成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的佇列也就稱為循環佇列。除了一些簡單套用之外，真正實用的佇列是循環佇列。

佇列[常用數據結構之一]

在循環佇列中，當佇列為空時，有front=rear，而當所有佇列空間全占滿時，也有front=rear。為了區別這兩種情況，規定循環佇列最多只能有MaxSize-1個佇列元素，當循環佇列中只剩下一個空存儲單元時，佇列就已經滿了。因此，佇列判空的條件時front=rear，而佇列判滿的條件時front=（rear+1）%MaxSize。隊空和隊滿的情況如圖：

佇列的數組實現

佇列可以用數組Q[1…m]來存儲，數組的上界m即是佇列所容許的最大容量。在佇列的運算中需設兩個指針：head，隊頭指針，指向實際隊頭元素；tail，隊尾指針，指向實際隊尾元素的下一個位置。一般情況下，兩個指針的初值設為0，這時佇列為空，沒有元素。數組定義Q[1…10]。Q(i) i=3,4,5,6,7,8。頭指針head=2，尾指針tail=8。佇列中擁有的元素個數為:L=tail-head。現要讓排頭的元素出隊，則需將頭指針加1。即head=head+1這時頭指針向上移動一個位置，指向Q(3)，表示Q(3)已出隊。如果想讓一個新元素入隊，則需尾指針向上移動一個位置。即tail=tail+1這時Q(9)入隊。當隊尾已經處理在最上面時，即tail=10，如果還要執行入隊操作，則要發生"上溢"，但實際上佇列中還有三個空位置，所以這種溢出稱為"假溢出"。

克服假溢出的方法有兩種。一種是將佇列中的所有元素均向低地址區移動，顯然這種方法是很浪費時間的；另一種方法是將數組存儲區看成是一個首尾相接的環形區域。當存放到n地址後，下一個地址就"翻轉"為1。在結構上採用這種技巧來存儲的佇列稱為循環佇列。

佇列和棧一樣只允許在斷點處插入和刪除元素。

循環隊的入隊算法如下：

1、tail=tail+1；

2、若tail=n+1，則tail=1；

3、若head=tail，即尾指針與頭指針重合了，表示元素已裝滿佇列，則作上溢出錯處理；

4、否則，Q(tail)=X，結束（X為新入出元素）。

佇列和棧一樣，有著非常廣泛的套用。

注意：（1）有時候佇列中還會設定表頭結點，就是在隊頭的前面還有一個結點，這個結點的數據域為空，但是指針域指向隊頭元素。

（2）另外，上面的計算還可以利用下面給出的公式cq.rear=(cq.front+1)/max;

當有表頭結點時，公式變為cq.rear=(cq.front+1)/（max+1）。

佇列的鍊表實現

在佇列的形成過程中，可以利用線性鍊表的原理，來生成一個佇列。

基於鍊表的佇列，要動態創建和刪除節點，效率較低，但是可以動態增長。

佇列採用的FIFO(first in first out)，新元素（等待進入佇列的元素）總是被插入到鍊表的尾部，而讀取的時候總是從鍊表的頭部開始讀取。每次讀取一個元素，釋放一個元素。所謂的動態創建，動態釋放。因而也不存在溢出等問題。由於鍊表由結構體間接而成，遍歷也方便。

佇列的基本運算

（1）初始化佇列：Init_Queue(q) ，初始條件：隊q 不存在。操作結果：構造了一個空隊；

（2）入隊操作： In_Queue(q,x),初始條件： 隊q 存在。操作結果： 對已存在的佇列q，插入一個元素x 到隊尾，隊發生變化；

（3）出隊操作： Out_Queue(q,x)，初始條件: 隊q 存在且非空，操作結果： 刪除隊首元素，並返回其值，隊發生變化；

（4）讀隊頭元素：Front_Queue(q,x)，初始條件: 隊q 存在且非空，操作結果： 讀隊頭元素，並返回其值，隊不變；

（5）判隊空操作：Empty_Queue(q)，初始條件： 隊q 存在，操作結果： 若q 為空隊則返回為1，否則返回為0。

操作	類型	作用	返回值	例子
length(s)	函式	求字元串s的長度	整型	s:="123456789"; l:=length(s);{l的值為9}
copy（s,w,k)	函式	複製s中從w開始的k位	字元串	s:="123456789"; s1:=copy(s,3,5);{s1的值是'34567'}
val(s,k,code)	過程	將字元串s轉為數值，存在k中；code是錯誤代碼		var s:string;k,code:integer; begin s:="1234"; val(s,k,code); write(k);{k=1234}
str(i,s)	過程	將數值i轉為字元串s		i:=1234; str(i,s); write(s);{s="1234"}
Delete(s,w,k)	過程	在s中刪除從第w位開始的k個字元		s := 'Honest Abe Lincoln'; Delete(s,8,4); Writeln(s); { 'Honest Lincoln' }
Insert(s1, S, w)	過程	將s1插到s中第w位		S := 'Honest Lincoln'; Insert('Abe ', S, 8); { 'Honest Abe Lincoln' }
Pos(c, S)	函式	求字元c在s中的位置	整型	S := ' 123.5'; i :=Pos(' ', S);{i的值為1}
+	運算符	將兩個字元串連線起來		s1:="1234"; s2:="5678"; s:=s1+s2;{'12345678'}

在STL中，對佇列的使用很是較完美

下面給出循環佇列的運算算法:

(1)將循環佇列置為空

//將佇列初始化

SeQueue::SeQueue()

{ front=0;

rear=0;

cout<<"init!"<<endl;

}

(2)判斷循環佇列是否為空

int SeQueue::Empty()

{ if(rear==front) return(1);

else return(0);

}

(3)在循環佇列中插入新的元素x

void SeQueue::AddQ(ElemType x)

{ if((rear+1) % MAXSIZE==front) cout<<" QUEUE IS FULL! "<<endl;

else{ rear=(rear+1) % MAXSIZE;

elem[rear]=x;

cout<<" OK!";

}

}

(4)刪除佇列中隊首元素

ElemType SeQueue::DelQ()

{ if(front==rear)

{ cout<<" QUEUE IS EMPTY! "<<endl; return -1;}

else{ front=(front+1) % MAXSIZE;

return(elem[front]);

}

}

(5)取佇列中的隊首元素

ElemType SeQueue::Front()

{ ElemType x;

if(front== rear)

cout<<"QUEUE IS EMPTY "<<endl;

else x= elem[(front+1)%MAXSIZE];

return (x);

}