本文的所有代碼均由C++編寫

六 隊列

文章目錄

• 六 隊列
• • 6.1 隊列的定義
  • 6.2 隊列的抽象數據類型
  • 6.3 順序隊列（循環隊列）
  • • 6.3.1 順序隊列的定義及初始化
    • 6.3.2 入隊
    • 6.3.3 出隊
    • 6.3.4 獲取隊頭元素
    • 6.3.5 獲取隊列長度
    • 6.3.6 回過頭來
  • 6.4 鏈式隊列
  • • 6.4.1 鏈式隊列的定義及初始化
    • 6.4.2 入隊
    • 6.4.3 出隊
  • 6.5 循環隊列和鏈式隊列的對比

6.1 隊列的定義

與棧相反，隊列(Queue)是一種先進先出(Fisrt in first out，FIFO)的結構。在此，我們先給出隊列的定義：

隊列是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表

舉一個生活中的例子，如下圖所示：

對的，你沒看錯，隊列實際上就這么簡單，我們把往隊列中添加結點叫做入隊，往隊列中刪除結點叫做出隊。入隊的一端叫隊尾，出隊的一端叫隊頭，這都是可以和生活中聯系起來的。

我們把上面的圖抽象一下，變成下面的形式：

隊列在程序設計中應用地非常頻繁，比如鍵盤輸入字母到記事本上，你依次輸入god，總不能記事本上面寫的是dog吧。

學過操作系統的朋友也了解就緒隊列這個名詞，在進程調度中，隊列也經常出現，在時間片調度算法中，一個進程從隊頭上處理器運行的時候，當時間片輪換時，這個進程若未執行完成，將會回到該就緒隊列的隊尾。

6.2 隊列的抽象數據類型

同樣，隊列也可以用線性表來表示，當然也就分為了順序隊列和鏈式隊列了。在探討這些之前，我們先了解一下隊列的抽象數據類型：

ADT 隊列(Queue) Data同線性表。元素具有相同的類型，相鄰元素具有前驅和后繼關系。 OperationInitQueue(*Q):初始化操作，建立一個空隊列Q。DestroyQueue(*Q):若隊列Q存在，則銷毀它。ClearQueue(*Q):將隊列Q清空。QueueEmpty(Q):若隊列Q為空，返回true，否咋返回false。Gethead(Q,*e):若隊列Q存在且非空，用e返回隊列Q的隊頭元素。EnQueue(*Q,e):若隊列Q存在，插入新元素e到隊列Q中并成為隊尾元素。DeQueue(*Q,e):刪除隊列Q中隊頭元素，并用e返回其值。QueueLength(Q):返回隊列Q的元素個數。 endADT

6.3 順序隊列（循環隊列）

6.3.1 順序隊列的定義及初始化

對于隊列的定義，同樣無需多講，上代碼。

//靜態數組大小 #define MaxSize 10//順序隊列定義 typedef int QElemType;typedef struct SqQueue {QElemType data[MaxSize];//靜態數組存放隊列元素int front, rear;//隊頭和隊尾指針 }SqQueue;//初始化 void InitQueue(SqQueue& Q) {Q.front = 0;Q.rear = 0; }

如果需要判斷隊列是否為空，只需判斷隊頭指針是否等于隊尾指針即可。

//判空 bool QueueEmpty(SqQueue Q) {if (Q.rear == Q.front)return true;elsereturn false; }

6.3.2 入隊

對于入隊，我們需要注意一個事情。

假設我們用一個靜態數組來存放隊列，那么隊頭指針指向隊頭元素，隊尾指針指向隊尾元素。當添加隊列元素時，隊尾指針+1，而當刪除隊列元素時，隊頭指針+1，也就是說，當隊尾指針等于靜態數組最大容量的時候，只能說明添加隊列的元素剛好處于數組最后，而不能說明隊列容量不足。這個情況在《大話數據結構》中叫做假溢出。

換而言之，隊頭元素不一定在數組的0號索引，隊尾數組不一定在數組的MaxSize號索引。

這樣的做法有別于我們前面講到的順序表的插入，在順序表中，我們插入是當插入一個元素，所有往后的元素都要移動一位，但是這樣就會造成時間復雜度過大，其花的時間都在移動元素上。為了解決時間問題，我們才拋出上述的做法。

那我們如何來處理順序隊列判斷是否溢出呢？

這個問題的拋出，引出了順序隊列的本名：循環隊列。我們在此給出循環隊列的定義：

我們把隊列中頭尾相接的順序存儲結構稱為循環隊列。

我們來嘗試處理這個問題，采用的方法有兩種。什么意思呢？我們發現當新元素入隊時，隊尾指針跟著新元素，如上圖所示，我們最開始初始化是讓front指針和rear指針重合，所以再次重合時就是隊列溢出的時候，由此我們可以引出第一個方法：

設置一個標志flag，最開始初始化時，front == rear，此時flag = 0，表示隊列為空，第二次front == rear，此時flag = 1，表示隊列溢出。

我們還可以有一種方法，即犧牲一個位置。當隊列滿的時候，數組中還有一個空閑單元。

由此我們可以引入第二個方法：

在判別滿的情況時我們的條件是(rear+1)% == front。

rear和front在數組中的位置那個在0號位那個在MaxSize號位是可以自己指定的，考慮到循環的問題，它們相遇有可能是在同一圈，也有可能相差了一圈后相遇，所以我們的判別溢出條件應該為(rear+1)%MaxSize = front。

上面可能有點亂，我們來看看下面的例子：

在上圖的左邊front處于0號位，rear處于4號位，按照上面我們說的，(4+1)%5 = 0，說明隊列已滿；如上圖所示右邊front處于2號位，rear處于1號位，如上所說(1+1)%5 = 2，說明隊列已滿。

取余運算是除法中的術語，取余數是指整數除法中被除數未被除盡部分，如7%2 = 1。這是大的數取余一個小的數；而當一個小的數取余一個大的數時，商為0，所以余數為自己，如2%5 = 2。

讓我們回到本小節的主題，入隊。既然弄清楚原理，代碼也好寫了。

//入隊 bool EnQueue(SqQueue& Q, QElemType x) {if ((Q.rear + 1) %MaxSize == Q.front) {return false;}//新元素插入隊尾Q.data[Q.rear] = x;//移動隊尾指針Q.rear = (Q.rear + 1) % MaxSize;return true; }

6.3.3 出隊

當然的，如果是要刪除隊列中的元素，即把隊頭元素刪除，當然需要注意的是注意判空。

//出隊 bool DeQueue(SqQueue& Q, QElemType& x) {//判斷隊列是否為空if (Q.rear == Q.front) {return false;//隊列為空無法刪除}x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true; }

6.3.4 獲取隊頭元素

//獲取隊頭元素 bool GetHead(SqQueue Q, QElemType& x) {if (Q.rear == Q.front)return false;//隊空則報錯x = Q.data[Q.front];return true; }

6.3.5 獲取隊列長度

//獲取隊列長度 bool QueueLength(SqQueue Q,QElemType &x) {x = (Q.rear + MaxSize - Q.front) % MaxSize;return true; }

6.3.6 回過頭來

上面講述了兩種方法來判斷是否溢出，我們在鏈棧中還采用了統計表長的方式來判斷棧棧，那么在隊列中我們同樣可以這么做，用一個整形的length來記錄隊列長度，當隊列長度大于MaxSize時，即隊列溢出，所以我們可以用條件if(length == MaxSize)來作為判斷條件。

根據初始化的不同，實際上對應的代碼都會有所不同，采用什么方法去判斷滿隊列就會有三種不同寫法，而在空隊列時，初始化兩個指針指向何處也會導致代碼的不同。在本筆記中，我們采用的是隊頭和隊尾指向同一個位置，當添加一個元素時，隊尾指針會移向隊尾元素的下一位；而在某些題目或教材中，隊尾指針可能是指向隊尾元素的。

在考研中，以上三種方法均有可能出現，望周知。

6.4 鏈式隊列

隊列的鏈式存儲結構，其實就是線性表的單鏈表，只不過它只能尾進頭出罷了。我們把它簡稱為鏈隊列。

對于鏈隊列來說，用帶頭結點的方式去實現就會更好一些。其中隊頭指針指向頭結點，隊尾指針指向隊尾元素，以便進行插入操作。接下來我們來看看如何實現。

6.4.1 鏈式隊列的定義及初始化

typedef struct LinkNode {ElemType data;struct LinkNode* next; }LinkNode;typedef struct {LinkNode* front, * rear; }LinkQueue;

對于初始化來說，代碼實現如下：

void InitQueue(LinkQueue& Q) {Q.front = Q.rear = new LinkNode;Q.front->next = NULL; }

6.4.2 入隊

鏈式結構入隊只需在添加結點于隊尾元素之后，更改隊尾指針指向即可。

//入隊 void EnQueue(LinkQueue& Q, ElemType x) {LinkNode* s = new LinkNode;//生成一個新結點s->data = x;s->next = NULL;Q.rear->next = s;//新結點插入rear之后Q.rear = s;//修改rear指針位置 }

6.4.3 出隊

//出隊 bool DeQueue(LinkQueue& Q, ElemType& e) {if (Q.front == Q.rear)return false;LinkNode* p = Q.front->next;e = p->data;Q.front->next = p->next;if (Q.rear == p)Q.rear = Q.front;delete(p);return true; }

6.5 循環隊列和鏈式隊列的對比

對于循環隊列和鏈式隊列來說，在時間復雜度上它們的基本操作都是常數時間，即都為O(1)。而對于空間上來說，循環隊列一開始長度就定死，而鏈式隊列則較為靈活。所以我們可以總結如下：

在可以確定隊列長度最大值的情況下，建議用循環隊列。如果無法預估隊列長度，則建議用鏈隊列。

總結

以上是生活随笔為你收集整理的数据结构杂谈（六）——队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。