佇列可以用陣列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)。
佇列可以用陣列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)。