佇列


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

隊列

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

佇列表示

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

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程式設計語言的完整佇列程式,請點選這裡