資料結構複習(七) : 隊列 Queue

今天來到線性表最後一個章節了!! 學到這邊大概是期中考的範圍吧 !大概吧?其實我也忘了在考什麼，不過記得把考古題做熟，觀念搞懂，一定能拿到高分的!! (新章給分超甜的 !)，接下來正式進入Queue的章節吧!!

大家肯定都有排過隊的經驗吧! 我們國小老師常常說，凡事講究一個 "先來後到"，其中 "先來" 指的是先到隊伍的人可以優先出去 ; "後到" 指的是時間比較晚的人要排在後面。 我們也可以這樣理解: First In First Out 先進先出(FIFO)。Queue的基本操作有這些 :

1. Queue createQueue(int MaxSize);    //建立空Queue
2. bool isFull/isEmpty (Queue Q);     //是否為滿/空   
3. bool AddQ(Queue, ElementType X);   //加入進表尾
4. ElementType DeleteQ(Queue);        //刪除表頭並返回表頭

一、 鏈式隊列 :

由於順序隊列較為複雜，我們先講鏈式隊列。和堆疊不同的是，由於尾端插入，表頭刪除，我們常常需要知道頭尾的節點在哪裡，因此我們需要個結構 :

typedef struct Node * PtrToNode;
struct Node {    //隊列的節點
  ElementType Data;
  PtrToNode Next;
};
typedef struct QNode * PtrToQNode;
struct QNode{        //指向表頭尾的結構
  PtrToNode Front;   //表頭指針
  PtrToNode Rear;    //表尾指針
};
typedef PtrToQNode Queue;

powered by 小畫家

1. 建立Queue (createQueue) :

Queue createQueue(){
  Queue Q = (Queue) malloc(sizeof(struct QNode));
  Q->Front = NULL;
  Q->Rear = NULL;
  return Q;
}

2. 是否為空 (isEmpty) :

bool isEmpty(Queue Q){
  return (Q->Front == NULL);
}

3. 壓入 (AddQ) :

bool AddQ(Queue Q, ElementType X){
  PtrToNode temp = (PtrToNode)malloc(sizeof(struct Node));
  temp->Data = X;
  temp->Next = NULL;
  if(isEmpty(Q)){        //如果為空，則為第一節點，Front&Rear指向它
    Q->Front = temp;
    Q->Rear = temp;
  }else{                 //非空，則放在Rear指向的節點之後
    Q->Rear->Next = temp;
    Q->Rear=temp;
  }
  return true;
}

4. 彈出 (DeleteQ) :

ElementType DeleteQ(Queue Q){
  if(isEmpty(Q)){
    printf("是空的");
    return -1;
  }else{
    PtrToNode temp = Q->Front;
    ElementType Num = temp->Data;
    if(Q->Front == Q->Rear)    //全隊列只剩下一個節點時，指向NULL
      Q->Front=Q->Rear=NULL;
    else
      Q->Front = temp->Next;
    free(temp);
    return Num;
  }
}

二、順序隊列 :

順序隊列一般先將Front&Rear設定為-1，當有資料進入時Rear+1，當有資料出去時Front+1，更為複雜的一點就是對空間的是用效率，在同樣的擁有Front&Rear去控制資料的進出時，常常最終會出現假溢出的情況 (明明還有空間但卻不能繼續放資料了)，如下看圖 :

圖摘自<<數據結構>> (第二版) P.84 圖3.12

其實並未完全填滿但卻出現了Rear==MaxSize-1的滿員情況，我們必須想一個更好的方法解決它!! 答案出來了，我們放成一個圓形 !! 如下圖，雖然資料同樣的隨著Front&Rear不斷移動，但卻始終在同一個圓中!! 利用公式 Front(or Rear) % MaxSize 可以實現折返到初始點。

現在又有另一個問題了，假使現在初始化Front&Rear皆為0，當進入一個Rear+1 ， 出去一個 Front+1 ，Rear==Front ，所以隊列為空，但!! MaxSize=3，Front=0 ，Rear近來3個 Rear=3，Rear%MaxSize=0，Front==Rear 滿的時候同樣會被判定為空，空與滿無法區別這該怎麼辦呢?

其因是Front&Rear無法帶來足夠的資訊，解決辦法有兩種:

1. 建立 int Size 紀錄節點數量是否==MaxSize
2. 不放滿

不放滿如上圖C可見，隊列空的條件是Front==Rear，而隊列滿的條件是 (Rear+1)%MaxSize ==Front，犧牲一單位空間，換取空與滿不同條件。以下是第二種方法的實現結構與方法 :

typedef int Position;
typedef struct QNode * PtrToQNode;
struct QNode{
  ElementType *Data;
  Position Front,Rear;
  int MaxSize;
};
typedef PtrToQNode Queue;

1. 建立隊列 (createQueue) :

Queue createQueue(int MaxSize){
  Queue Q = (Queue)malloc(sizeof(struct QNode));
  Q->Data=(ElementType *)malloc(sizeof(ElementType)*MaxSize);
  Q->MaxSize=MaxSize;
  Q->Front=Q->Rear=0;
  return Q;
}

2. 是否為空/滿 (isEmpty/Full) :

bool isEmpty(Queue Q){
  return (Q->Rear == Q->Front);
}
bool isFull(Queue Q){
  return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}

3. 插入 (AddQ) :

bool AddQ(Queue Q,ElementType X){
  if(isFull(Q)){
    printf("已經滿了");
    return false;
  }else{
    Q->Rear = (Q->Rear+1)%Q->MaxSize;    //Rear+1
    Q->Data[Q->Rear]=X;
    return true;
  }
}

4. 刪除 (Delete) :

ElementType DeleteQ(Queue Q){
  if(isEmpty(Q)){
    printf("已空");
    return -1;
  }else{
    Q->Front = (Q->Front+1)%Q->MaxSize;  //Front+1
    return Q->Data[Q->Front];            //由於空一格
  }
}

這一章節特別難，其實我也是拼命看書才寫的，記住多畫圖能更好的理解。如果能理解這些觀念，想必期中考必定能拿高分 !! (其實不用到能寫出來啦!)下一次就是來到頂頂大名的 "樹" 了。

題外話 : 真的只要把考古題做熟了就會過了!

完整程式碼 :

1. 鏈式 :

2 順序:

參考資料 :

1. 《数据结构》（第2版），陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著，高等教育出版社，2016年6月
2. https://www.icourse163.org/course/ZJU-93001

資料結構複習(六) : 堆疊 Stack

資料結構複習(八) : 樹