Queue - 佇列

Queue跟Stack一樣都是有順序性的，存與取之間有一定的規則。直觀來看，Queue其實就像隊列，排頭的當然先服務，後到的就得等前面完事才能往前走，當然，我們不考慮插隊的情形，每次要加入這個隊伍的，都必須排在隊伍尾端，所以成了FIFO(First in First out)的型式。

1.Queue ADT

• Queue CreatQ(maxQueueSize) ：創造一個空的quene
• Boolen IsFull(quene,maxQueuesize)：判斷quene是否滿了，
• Boolen isEmpty(queue)：判斷quene是否為空
• Quene Add(queue,item)：添入item是quene
• Element Delete(queue)：刪除quene中的一個物件，並把它傳回給item

Queue的操作都與Stack類似，主要有兩個不同：

其一是stack有一方是底，我們只需要一直把東西丟進去丟進去，不過quene則是兩端皆開放的，要分別處理排頭跟排尾，所以我們需要兩個變數(front , rear)來儲存quene的頭跟尾，而front與rear的初始值一樣可以當作-1，配合於isEmpty的判斷上。

• add : rear = rear +1
• delete : front = front +1;

第一，從上述的操作，我們可以看出quene會不斷地往右偏移，所以在判斷isFull時，我們不能僅考慮rear是否>maxQuenesize，我們要思考的是，這個隊列是不是真的滿了？如果沒滿，則要把整個隊列往左平移。

2.Circular Queue

它是一個環狀的queue，這能解決上述第二個問題，不過他也得付出一點代價，即只能放MAX_Queue_Size - 1個元素，剩下一個必須用來判斷queue為空或為滿。

3.其他quene形式

• Double ended queue：兩端都能放且兩端都能拿的queue
• Priority queue：元素在queue的位置跟它的priority值有關，跟進入queue的時間無關
• Double ended priority queue