隊列及其基本運算

1)隊列

隊列即是允許在一端進行插入，而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，通常用一個尾指針指向隊尾;允許刪除的一端稱為隊首，通常用一個隊首指針指向排隊元素的前一個位置。

隊列遵循的規則是：先進先出或后進后出

2)循環隊列及其運算

隊列的順序存儲結構一般采用循環隊列的形式。

循環隊列，即是次隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。

在循環隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從排頭指針front指向的后一個位置到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。

循環隊列的初始狀態為空，即rear=front=m。這里m即為隊列的存儲空間。

循環隊列的基本運算：入隊運算和退隊運算。

入隊運算：每進行一次入隊運算，隊尾指針加1。當隊尾指針rear=m+1時，即表示隊列空間的尾部已經放置了元素，則下一個元素應該旋轉到隊列空間的首部，即rear=1

退隊運算：每退隊一個元素，排頭指針加1。當排頭指針front=m+1時，即排頭指針指向隊列空間的尾部，退隊后，排頭指針指向隊列空間的開始，即front=1。

在隊列操作時，循環隊列滿時，front=rear，隊列空時，也有rear=front，即在隊列空或滿時，排頭指針和隊尾指針均指向同一個位置。要判斷隊列空或滿時，還應增加一個標志，s值的定義：

判斷隊列空與隊列滿的條件下：

隊列空的條件：s=0

隊列滿的條件：s=1、front=rear

(1)入隊運算(2)退隊操作

更多精彩資訊請關注查字典資訊網，我們將持續為您更新最新資訊!