User Tools

Site Tools

This is an old revision of the document!


A queue is a 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.


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

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.

λ Queue_List-based

queue.1422894502.txt.gz · Last modified: 2016/04/02 16:41 (external edit)