Chapter 3 佇列 - Ian-Liu-1990/Data-Structure GitHub Wiki

１. 佇列: LIFO，插入與刪除非同一邊

• 定義 : 有序串列，插入與刪除非同一邊，操作通常先進先出，類似於排隊
• 應用 :
  1. 有優先權的作業系統排程
  2. 搜索圖型連通廣度優先
  3. 最大或最小堆積的排序

佇列Front(已經被Pop出去)與Rear(準備Push近來)的３種狀態關係，請看手寫筆記，稍微複雜

1. Rear == Front : 佇列為空(Empty)

2. Rear == Max - 1 : Front的２種狀態

   1. Front == -1 : 佇列為全滿(Full)

   2. Front != -1 : Front以前的Index都尚有空位，需要搬移

3. Rear != Max - 1 : Front不管指向哪裡，Rear之後都還有空位，還可以向後增加

• Front : 指向的位址不儲存任何東西，是空的

---

1. 初始化，全域變數宣告 :

const int N = 100
int q[N];
int front, rear;

void CreatQ(){
   front = rear = -1;
}

2. 檢查是否空

int IsQEmpty(){
  if front = rear{
    return 1
  }
  return -1
}

2. 檢查是否空滿

int IsQFull(){
   if (rear == N-1) && (front == -1){
      return 1
   }
   return -1
}

3. 插入Enqueue

int Enqueue(int d){
   if (rear == Max - 1)
        if (QueueMove() == -1) //-1全滿，移動失敗，1尚有空間，移動成功
            return -1
   q[++rear] = x;
}

4. 刪除Dequeue : Front指向的位置是空的

int Dequeue(){
   if(IsQEmpty){
     front = rear = -1;
     return -1;
   }
   return q[++front] // front表示位置沒有值，需要先向前才能Dequeue有值!!!
}

5. Queue向前移動 : Front指向的位置是空的

int  QueueMove(){
   int i;
   if(front ==-1)
      return -1 // 全滿，無法移動
   for(i = front + 1; i <= rear; i++)
        q[i - front - 1 ] = q[i]; // 由後往前移動
   rear = rear - front - 1; // 移動完rear的位置；rear = 9, front = 5, [0~4]空著，["6"~9]使用中
   front = -1; // 移動完front回到-1 !!!!!
}

---

２. 佇列應用

３. 環狀佇列

• 變革 : 邏輯上，頭尾相接，並為了減少一般佇列當Rear == MAX-1 && Front != -1時搬動整個佇列的問題

• ３個佇列變化 :

1. Double-Ended Queue,Dequeue，雙向佇列(兩邊皆可刪除，增加)

2. Input-Restricted Dequeue，兩邊皆可刪除但只能由一邊插入

3. Output-Restricted Dequeue，兩邊皆可插入但只能由一邊刪除

• ３個實作方法
• 全域變數宣告 :

const int N = 100;
int q[N];
int front, rear;

1. 基本環狀佇列時作法 : 陣列大小N，做多只能放N-1，每次刪除，增加時間O(N)

• 初始 :

void CreateQ(){
  front = rear = N - 1;   
}

• 檢查全滿或全空

int IsQueueEmpty(){ if(front == rear) return 1}

int IsQueueFull(){ if ((rear+1)%N == front) return 1 ;}

1. 插入Enqueue

void Enqueue(int d){
   if(IsQFull)
      return -1
   
   rear = (rear + 1)%N;
   q[rear] = d
}

2. 刪除Dequeue

void Dequeue(){
   if(IsQEmpty)
     return -1;
   front = (front+1)%N; // front表示位置沒有值，需要先向前才能Dequeue有值!!!
   return q[front];
}