[C語言] 以鏈結串列(Linked List) 實作資料結構的佇列(Queue)

佇列(Queue)稱為FIFO (First In First Out)的資料結構。

定義：Queue是一個有序的線性串列，如同日常生活中隨處可見的排隊人潮，排隊的隊伍是在尾端(rear/tail)加入隊伍，如果佇列在尾端插入資料；當前端(front/head)離開隊伍，就如同佇列在前端刪除資料。

佇列的基本操作，如下所示：
1. Push(data)：在尾端加入新資料
2. Pop：從前端取出資料
3. getFront：回傳最舊的資料
4. getTail：回傳最新的資料
5. getSize：回傳Queue裡的資料個數
6. IsEmpty：檢查Queue是否是空的

以鏈結串列(Linked List)實作佇列(Queue)：

#include 
#include 

struct Node{
  int data;
  struct Node *next;
};

typedef struct Node Queue_Node;
Queue_Node * front = NULL;
Queue_Node * tail = NULL;
int size = 0;

int main() {
  for(int i =0; i<5;i++){
    size+=1;
    push(rand()%100);
  }
  
  printf("佇列最前面的資料為:%d\n",getFront());
  printf("佇列最後面的資料為:%d\n",getTail());
  printf("佇列的總數為:%d\n\n",getSize());
  
  while(front!=NULL)
    printf("佇列刪除的資料為:%d\n",pop());
  return 0;
}

void push(int a){
  Queue_Node * new_add_node;
  new_add_node = (Queue_Node*)malloc(sizeof(struct Node));

  new_add_node->data = a;
  new_add_node->next = NULL;
  
  if(tail==NULL)
    front = new_add_node;
  else
    tail->next=new_add_node;
    
  tail=new_add_node;
}

int pop(){
  Queue_Node *pt = front;
  int i = front->data;
  front = front->next;
  free(pt);  
  return i;  
}

int isEmpty(){
  if(front==NULL)
    return 1;
  else
    return 0;
}

int getFront(){
  return front->data;
}

int getTail(){
  return tail->data;
}

int getSize(){
  return size;
}

程式會依序印出：
佇列最前面的資料為:83
佇列最後面的資料為:93
佇列的總數為:5

佇列刪除的資料為:83
佇列刪除的資料為:86
佇列刪除的資料為:77
佇列刪除的資料為:15
佇列刪除的資料為:93

可以看看底下示意圖：

延伸閱讀：

2021手機賺錢APP「aifian」掃電子發票拿現金 + 生活數據啟動現金回饋

2021數位貨幣推薦｜HI DOLLARS 剛出不久的加密貨幣，每天免費領取HI DOLLARS！

iHerb網購保健食品(葉黃素、益生菌、維生素D3)超划算，使用折扣碼更優惠！