昨天介紹了用array的方式做Queue，今天來介紹用linked list製作!

[法二]用linked list製作

一、single linked list
宣告:
1.Node structure is:

• enqueue(Q,item)
  觀念:
  case1:Q原先為空
  
  case2:Q原先非空
  

  {
      New(t);
      t➝Data=item;
      t➝link=Null;
      if(Front==Null) then Front=t; //Q空
      else Rear➝link=t; //Q非空
      Rear=t;
   }

• dequeue(Q)
  觀念:
  

  {
      if(front==Null) then return "Q empty";
      else{
            ①t = Front;
            ②item = Front➝Data;
            ③Front = Front➝link;
            ④free(t);
            if(front==Null) then rear = Null;
            return item;
          }
   }

二、circular linked list

只用一個pointer即可表示尾及前端
即rear:指向尾端
rear➝link:前端

宣告:
1.Node structure is:

• enqueue(Q,item)
  觀念:
  case1:Q原先為空
  
  case2:Q原先非空
  

  {
      New(t);
      t➝Data=item;
      if(Rear==Null) then t➝link=t; //Q空
      else{ //Q非空
          t➝link=Rear➝link;
          Rear➝link=t;
      }
      rear=t; //剛插入的t變成rear
   }

• dequeue(Q)

  {
      if(Rear==Null) then return "Q empty";
        ①t = Rear➝link;
        ②item = (Rear➝link)➝Data;
        ③Rear➝link = (Rear➝link)➝link;
        ④free(t);
   }

Queue的種類

1. FIFO Queue
2. Priority Queue
   不一定遵守FIFO性質，而是支持插入任意權值元素及刪除最大(or最小)權值之動作，常用於OS中製作Queue之最適合的資料結構
3. Double-ended Queue(雙邊佇列)
   Queue的任意兩端皆可插入即刪除元素
4. Double-ended priority Queue
   此Queue支持插入任意權值元素、刪除最大權值元素、刪除最小權值元素
   製作此Queue之Data structure有min-max heap、deap及SMMH