Queues

• FIFO
• Insert(rear/tail), Delete(front/head)

Linear Queue

• Enqueue(插入) / Dequeue(刪除)都只需要 $O(1)$ 時間.
• 末端已滿，但前面還有空間，須移動整個queue，須花費 $O(n)$ 時間。

  Empty(): front = rear
  Full():  rear - front = N
  

Circular Queue

• 可以減少搬動整個佇列的時間，無須搬動。
• Enqueue(插入) / Dequeue(刪除)都只需要 $O(1)$ 時間.
• Size = N的queue只能裝N-1筆資料，否則會無法分辨Full/Empty。 source

  Empty(): front = rear
  Full():  (rear + 1) % N = front
  

Deque

• 雙向佇列 (Deque) 兩端都可做加入與取出資料的動作。
• double-ended queue
• http://www.cplusplus.com/reference/deque/deque/

應用

• Job Scheduling (OS)
• BFS (Breadth-First Search)
• Buffer