歐歐終於結束Stack的部分了，接下來換來介紹Queue~
我們一樣先來舉一些生活中的例子，像是我們平常要買東西、搭車等等都需要排隊，先排到隊伍中的人會先獲得購買的資格，越後面的人則要等越久才能買到想要的東西，這就像佇列一樣＼＼\٩( 'ω' )و //／／

特性

• 具有First In First Out(FIFO)先進先出性質的有序串列
• 插入元素之動作稱為enqueue，發生在尾端(rear)
• 刪除元素之動作稱為dequeue，發生在前端(front)
• 插入、刪除生在不同端（插入只能在尾，刪除只能在頭）

應用

1. OS中的job scheduling，相同priority下，利用queue來完成先到先坐的原則
2. I/O device Queue
3. Priority queue
4. 用於Simulation
5. 作為輸出工作的buffer(緩衝)
6. 排隊行為
7. 圖形的廣度追蹤(BFS)
8. 二元樹的level-order-traversal

Queue的ADT描述

1. create Q(n):建立新的佇列實體
2. Enqueue(Q,item):在佇列尾短新增元素
3. Dequeue(Q):刪除佇列前端元素

Queue的製作

[法一]用array製作

一、linear Array
宣告:
1.Q:array[1..n] of item;
2.rear,front:int=0;

• enqueue(Q,item)

  {
      if(rear==n)return "Q Full";
      else{
          rear=rear+1;
          Q[rear]=item;
          }
   }

• dequeue(Q)

  {
      if(front==rear)return "Q empty";
      else{
            front=front+1;
            item=Q[front];
            return item;
          }
   }

分析:
當rear==n條件成立時，不一定代表Q真的Full
(例如:rear=n,front=2,Q還有2個空格,並未full)
所以有空間浪費掉沒有使用

二、circular array，最多只能用(n-1)格空間
宣告:
1.Q:array[0,...,(n-1)] of item;
2.rear,front:int=0;

circular 之觀念:
rear=(rear+1)%n
front=(front+1)%n

• enqueue(Q,item)

  {
      rear=(rear+1)%n;
      if(rear==front) then return "Q Full";
      else Q[rear]=item;
   }

• dequeue(Q)

  {
      if(front==rear)return "Q empty";
      else{
            front=(front+1)%n;
            item=Q[front];
            return item;
          }
   }

分析:

1. 最多只能使用(n-1)格空間，即front所指之格無法使用
2. 若硬用此格，則無法判斷出到底是Q empty或是Q full之情況，when front==rear
3. enqueue及dequeue之time皆為O(1)
4. 判斷Q empty、Q full的條件式寫法相同

三、circular array，最多可用n格空間
宣告:
1.Q:array[0,...,(n-1)] of item;
2.rear,front:int=0;
3.Tag:Boolean=false;用以協助判斷Q empty or Q full，搭配rear,front

• enqueue(Q,item)

  {
      if(rear==front) and (Tag==True) then return "Q Full";
      else{
          rear=(rear+1)%n;
          Q[rear]=item;
          if(rear==front) then Tag=True;
          }
   }

• dequeue(Q)

  {
      if(front==rear) and (Tag==False) then return "Q empty";
      else{
            front=(front+1)%n;
            item=Q[front];
            if(front==rear) then Tag=False;
            return item;
          }
   }

分析:

1. 可充分利用n格空間
2. enqueue、dequeue time也是O(1)
3. 在enqueue及dequeue動作中，均額外多了一行if測試，所以時間會比(circular array，最多只能用(n-1)格空間)久一點

今天先到這邊，明天再來介紹linked list的作法
最近覺得人生好難，遇到很難過很挫折的事情
但還是要加油努力撐下去的對吧(´;ω;`)