隊列(queue)：隊列是隻允許在-端進行插入操作，而在另-端進行删除操作的線性表。隊列是一種先進先出 (First In First Out) 的線性表，簡稱 FIFO。允許插入的一端稱為隊尾，允許删除的一端稱為隊頭。

隊列

隊列（Queue）與棧一樣，是一種線性存儲結構，它具有如下特點：

• 隊列中的數據元素遵循“先進先出”（First In First Out）的原則，簡稱FIFO結構。
• 在隊尾添加元素，在隊頭删除元素。

線性表有順序存儲和鍊式存儲，棧是線性表，所以有這兩種存儲方式。隊列作為一種特殊的線性表，也同樣存在着這兩種存儲方式。

我們假設一個隊列有 n 個元素，則順序存儲的隊列需建立一個大于 n 的數組，并把隊列的所有元素存儲在數組的前 n 個單元，數組下标為0的一端即是隊頭。

隊列的順序存儲

順序存儲的入隊操作：

所謂的入隊列操作，其實就是在隊尾追加一個元素，不需要移動任何元素，因此時間複雜度為O(1)。

順序存儲的入隊操作

順序存儲的出隊操作：

隊列與棧不同的是，隊列元素的出隊是在隊頭，即下标為0的位置，所以隊列中的所有元素都得向前移動，以保證隊列的隊頭，也就是下标為0的位置不為空，此時時間複雜度為O(n)

順序存儲的出隊操作

我們發現隊列的順序存儲與現實情況非常相似，大家排隊做核酸，先來的人先去做，當第一個人做完核酸離隊後，其他人都向前進一位。我們可以發現，現在我們是限制了元素必須存儲在順序表的前 n 個元素，如果我們不限制元素在順序表的位置，該如何做呢。

front 指針指向隊頭元素 ， rear 指針指向隊尾元素的下一個位置。假設數組的長度為 5，初始狀态，空隊列時 front 與 rear指針均指向下标為0的位置；

空隊列

然後入隊a1、 a2、 a3、a4，front指針依然指向下标為0位置，而rear指針指向下标為4的位置。

入隊

出隊 a1、a2 ，則front指針指向下标為2的位置， rear 不變。

出隊

再入隊 a5，此時數組已經溢出了，但是下标為0，1的位置實際上是空閑的。

假溢出

由上圖我們發現，隊列的大小是5，但實際上我們隻有3個元素，由于 rear 指針已經在數組尾部，再進行入隊就發生了數組的越界，這就是順序隊列的“假溢出”現象。

解決假溢出的辦法就是後面滿了，就從頭開始，也就是頭尾相接的循環。我們把隊列的這種頭尾相接的順序存儲結構稱為循環隊列。

循環隊列

我們接着處理上面入隊 a5元素的操作，如果是循環隊列，我們可以把 rear 指針指向下标0的位置。

循環隊列

接着入隊a6，将它放置于下标為0處， rear 指針指向下标為1處。

入隊

接着入隊a7，将它放置于下标為1的位置， rear 指針指向下标為2處。

入隊

此時我們發現 rear 與 front 相等，隊列卻滿了，這不就與空隊列為空的判斷條件沖突了嗎；在實際開發中，我們會預留一個空位置，就是數組隻有一個空位置時，我們就認為隊列滿了。

隊滿

由于 rear 可能比 front大，也可能比 front小，所以盡管它們隻相差一個位置時就是隊滿的情況，但也可能是相差整整一圈。 我們假設隊列的大小為QueueSize。

• 空隊列：rear=front；
• 隊列滿：(rear 1) % QueueSize=front
• 隊列元素的個數：(rear-front QueueSize) %QueueSize

隊列的鍊式存儲結構，其實就是線性表的單鍊表，隻不過它隻能尾進頭出而已， 我們把它簡稱為鍊隊列 。為了操作上的方便，我們将隊頭指針指向鍊隊列的頭結點，而隊尾指針指向終端結點。

隊列的鍊式存儲結構

空隊列時， front和 rear都指向頭結點。

空隊列

數據結構：

class Node<T>{ //數據 T data; //下一個元素指針 Node next; } class Queue{ //頭指針 Node front; //尾指針 Node rear; }

1、鍵盤的輸入與輸出，比如你微信聊天輸入god，由于隊列是先進先出所以出來就是 god，如果是棧就是 dog。

2、打印機的任務

3、編程語言中線程池的任務隊列

4、現在很多的消息中間件MQ

5、圖的遍曆

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!