Queue

Definition

FIFO data structure with two operations enqueue (adds element at back) and dequeue (pops element at the head). There exists:

• simple queue
• circular queue
• priority queue: add element with a corresponding priority, dequeuing pops the element having the highest priority.
• double ended queue: enqueuing and dequeuing possible from both ends.

Implementations

• simple and circular queues: dynamic array or linked list.
• priority queue: heap.
• double ended queue: vector of pointers to chunks of vectors (C++ STL implementation)
  

Complexity

Queue

Operation	Complexity
Enqueue	$O(1)$
Dequeue	$O(1)$

Append and deletion complexities of dynamic array.

Priority queue

Operation	Complexity
Enqueue	$O(log(n))$
Dequeue	$O(log(n))$

Append and deletion complexities of heap.

Deque

Operation	Complexity
Access	$O(1)$
Search	$O(n)$
Enqueue	$O(1)$ amortized
Dequeue	$O(1)$ amortized
Insert	$O(n)$
Remove	$O(n)$

TODO