基本介紹
- 中文名：順序佇列
- 外文名：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．此時若再執行入隊操作，便會出現隊滿“溢出”。然而，由於在此之前可能也執行了若干次出隊操作．因而數組的前面部分可能還有很多閒置的元素空間，即這種溢出並非是真的沒有可用的存儲空間，故稱這種溢出現象為“假溢出”。顯然，必須要解決這一似溢出的問題，否則順序佇列就沒有太多使用價值。
