Queue (abstract data type)

A queue is a abstract collection data type where the primary operations are enqueue which adds an element and dequeue which removes. It is a First-In-First-Out (FIFO) data structure, the first element pushed must be the first one removed.

Linked List Based

The Linked List based implementation works by keeping a pointer to the start and end of the list. Dequeueing removes the first element of the list, much like the linked list stack, enqueueing utilises the pointer to the end of the list to add an item at the end of the list in constant time.

Properties

• $O(1)$ enqueue
• $O(1)$ dequeue
• $O(n)$ space

Array Based

The array based implementation works by keeping a two arrays left and right. Dequeue is $O(1)$ even though it includes a $O(n)$ reverse operation. This is because the reverse happens at a $1/n$ frequency.

Properties

• $O(1)$ enqueue
• Amortized $O(1)$ dequeue
• $O(n)$ space