順序佇列

順序佇列是佇列的順序存儲結構，順序佇列實際上是運算受限的順序表。和順序表一樣，順序佇列用一個向量空間來存放當前佇列中的元素。由於佇列的隊頭和隊尾的位置是變化的，設定兩個指針front和rear分別指示隊頭元素和隊尾元素在向量空間中的位置，它們的初值在佇列初始化時均應設定為0。

基本介紹

• 中文名：順序佇列
• 外文名：sequential queue

套用背景

在現實世界中存在很多佇列的實例。例如，在電影院的售票視窗排隊等待買票的人，就是通過佇列這種數據結構組織在一起的。人們按先來後到的順序排成一隊，最先買到票的人就是最先來的人。當某人買完票，他就會從佇列的最前端離開，這就相當於刪除操作。而添加的操作卻僅能在佇列的尾部進行，因此新來的人就只能排在佇列的最後。此外，還有像公共汽車站人們排隊等車、醫院中病人排隊候診等都是顯示生活中佇列的例子。

表示方法

順序佇列通常採用一維數組進行存儲。其中，連續的存儲單元依次存放佇列中的元素。同時，使用兩個指針分別表示數組中存放的第一個元素和最後一個元素的位置。其中，指向第一個元素的指針被稱為隊頭指針front，指向最後一個元素的位置的指針被稱為隊尾指針rear。

在實際編程過程中，通常設隊頭指針指向佇列的第一個元素，隊尾指針指向隊尾元素的後一個位置。front和rear的初值在佇列初始化時均應置為0；入隊時將新元素插入rear所指的位置，然後將rear加1。出隊時，刪去front所指的元素，然後將front加1並返回被刪元素：由此可見，當頭尾指針相等時佇列為空。在非空佇列里，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一個位置。

基本操作

入隊時：將新元素插入rear所指的位置，然後將rear加1。

出隊時：刪去front所指的元素，然後將front加1並返回被刪元素。

注意：

(1)當頭尾指針相等時，佇列為空。

(2)在非空佇列里，隊頭指針始終指向隊頭元素，隊尾指針始終指向隊尾元素的下一位置。

存在問題

在普通順序佇列中，入隊操作就是先將尾指針rear後移一個單元(rear++)，然後將元素值賦給rear單元(data[rear]=X)。出隊時．則是頭指針front後移(front++)。像這樣進行了一定數量入隊和出隊操作後，可能會出現這樣的情況：尾指針rear已指到數組的最後一個元素．即rear==MAXLEN-1．此時若再執行入隊操作，便會出現隊滿“溢出”。然而，由於在此之前可能也執行了若干次出隊操作．因而數組的前面部分可能還有很多閒置的元素空間，即這種溢出並非是真的沒有可用的存儲空間，故稱這種溢出現象為“假溢出”。顯然，必須要解決這一似溢出的問題，否則順序佇列就沒有太多使用價值。