使用C語言實現資料結構 - 佇列

概述

佇列是一種類似於棧的資料結構，主要區別在於第一個插入的元素也是第一個被移除的元素（FIFO - 先進先出），而棧是基於LIFO（後進先出）原則的。

隊列表示

基本操作

• 插入/入隊 (enqueue) − 將一個元素新增到佇列的尾部。

• 移除/出隊 (dequeue) − 從佇列的頭部移除一個元素。

在本文中，我們將使用陣列來實現佇列。佇列還支援其他一些操作，如下所示。

• 窺視 (Peek) − 獲取佇列頭部元素。

• 是否已滿 (isFull) − 檢查佇列是否已滿。

• 是否為空 (isEmpty) − 檢查佇列是否為空。

插入/入隊操作

每當一個元素插入到佇列中時，佇列都會增加尾部索引以供後續使用，並將該元素儲存在儲存空間的尾部。如果尾部到達最後一個索引，則會將其環繞到最底部的儲存位置。這種安排稱為環繞，這樣的佇列稱為迴圈佇列。此方法也稱為入隊操作。

void insert(int data){
   if(!isFull()){
      if(rear == MAX-1){
         rear = -1;            
      }       
      intArray[++rear] = data;
      itemCount++;
   }
}

移除/出隊操作

每當需要從佇列中移除一個元素時，佇列會使用頭部索引獲取該元素並增加頭部索引。作為環繞安排，如果頭部索引大於陣列的最大索引，則將其設定為0。

int removeData(){
   int data = intArray[front++];
   if(front == MAX){
      front = 0;
   }
   itemCount--;
   return data;  
}

示例

QueueDemo.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6

int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;

int peek(){
   return intArray[front];
}
bool isEmpty(){
   return itemCount == 0;
}
bool isFull(){
   return itemCount == MAX;
}
int size(){
   return itemCount;
}
void insert(int data){
   if(!isFull()){
      if(rear == MAX-1){
         rear = -1;            
      }       
      intArray[++rear] = data;
      itemCount++;
   }
}
int removeData(){
   int data = intArray[front++];
   if(front == MAX){
      front = 0;
   }
   itemCount--;
   return data;  
}
int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // front : 0
   // rear  : 4
   // ------------------
   // index : 0 1 2 3 4 
   // ------------------
   // queue : 3 5 9 1 12
   insert(15);

   // front : 0
   // rear  : 5
   // ---------------------
   // index : 0 1 2 3 4  5 
   // ---------------------
   // queue : 3 5 9 1 12 15
   if(isFull()){
      printf("Queue is full!\n");   
   }

   // remove one item 
   int num = removeData();
   printf("Element removed: %d\n",num);
   // front : 1
   // rear  : 5
   // -------------------
   // index : 1 2 3 4  5
   // -------------------
   // queue : 5 9 1 12 15

   // insert more items
   insert(16);

   // front : 1
   // rear  : -1
   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15

   // As queue is full, elements will not be inserted. 
   insert(17);
   insert(18);

   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15
   printf("Element at front: %d\n",peek());

   printf("----------------------\n");
   printf("index : 5 4 3 2  1  0\n");
   printf("----------------------\n");
   printf("Queue:  ");
   while(!isEmpty()){
      int n = removeData();           
      printf("%d ",n);
   }   
}

輸出

如果我們編譯並執行上述程式，則會產生以下輸出：

Queue is full!
Element removed: 3
Element at front: 5
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 5 9 1 12 15 16