資料結構和演算法教學 » 佇列

佇列

佇列是一個抽象的資料結構，與堆疊有些相似。較對比於棧，佇列開啟兩端。 一端總是用來插入資料(排隊)，另一個是用來刪除資料(離隊)。 佇列使用先入先出的方法，即，第一儲存的資料項先被存取。如下：

隊列

佇列中的一個真實的例子可以是單向的車道單行道，其中車輛第一進入，第一離開。更多真實世界的例子可以看出，佇列在售票視窗和巴士站。

佇列表示

正如我們現在知道，在佇列中存取兩端出於不同的原因，如下圖試圖解釋佇列表示資料結構 -

Queue Example

與棧，佇列相同，也可以使用陣列，連結串列，指標和結構來實現。為簡單起見，我們將使用一維陣列實現佇列。

基本操作

佇列操作可能涉及到初始化或定義佇列，利用它完成從記憶體中清除它。在這裡，我們將試著去了解使用佇列相關的基本操作 -

  • enqueue() ? 新增（儲存）專案到佇列中。

  • dequeue() ? 從佇列中刪除（存取）專案。

很少有更多的功能需要在上述佇列提高操作效率。它們有 -

  • peek() ? 獲得在佇列前面的元素而不移除它。

  • isfull() ? 檢查佇列是否已滿。

  • isempty() ? 檢查佇列是否為空。

在佇列中，我們總是出隊（或存取）資料，通過前面的指標，查詢（或儲存）我們把後面的指標的幫助下將佇列中的資料指出。

讓我們先來了解一個佇列的輔助功能 ?

peek()

像棧，此功能可以看到在佇列的前部的資料。peek() 函式演算法如下 ? 

begin procedure peek

   return queue[front]
   
end procedure

在C語言中 peek()函式的實現- 

int peek() {
   return queue[front];
}

isfull()

由於我們使用一維陣列實現的佇列，我們只是檢查後指標要達到最大範圍（MAXSIZE），以確定佇列已滿。在情況下，我們保持佇列以迴圈連結串列的形式，該演算法將有所不同。isfull()函式演算法如下： 

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

在C語言中的 isfull()函式的實現 - 

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

isempty()

isEmpty()函式演算法 - 

begin procedure isempty

   if front is less than MIN  OR front is greater than rear return true
   else
      return false
   endif
   
end procedure

如果前面的值小於 MIN 或 0，它告訴佇列尚未初始化，因此空。

下面是C語言程式設計程式碼 - 

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

入隊操作

由於佇列維護兩個資料指標，前部和後部，其操作比堆疊相對較難實現。

應採取以下步驟來將資料排入佇列（插入）到一個佇列 -

  • Step 1 ? 檢查佇列是否已滿

  • Step 2 ? 如果佇列已滿，產生溢位錯誤，然後退出

  • Step 3 ? 如果佇列未滿，增加尾部指標指向下一個空的空間

  • Step 4 ? 新增資料元素到佇列位置，其中後方（rear）指向

  • Step 5 ? 返回成功

Insert Operation

有時，我們還要檢查，如果佇列被初始化或不處理任何意外情況。

排入佇列的操作演算法 

procedure enqueue(data)      
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   
   queue[rear] ← data
   
   return true
   
end procedure

排入佇列 enqueue() 函式的 C語言的實現- 

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

解列操作

從佇列中存取資料是兩個任務的過程 ? 存取前在這裡指的是所指向的資料，以及存取後刪除資料。將採取以下步驟來執行解列操作 -

  • Step 1 ? 檢查佇列是否為空

  • Step 2 ? 如果佇列為空，產生溢錯誤，然後退出

  • Step 3 ? 如果佇列不為空，存取資料，並向前指向

  • Step 3 ? 增量前指標指向下一個可用的資料元素

  • Step 5 ? 返回成功

Remove Operation

演算法解列操作 - 

procedure dequeue
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front - 1
   
   return true
end procedure

出佇列 dequeue() 的C語言實現： 

int dequeue() {

   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

對於C程式設計語言的完整佇列程式，請點選這裡