Queue

data-structures

Definition

Queue

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added to the back (rear) and removed from the front.

It provides three primary operations:

1. $\mathrm{enqueue}(v)$: Adds element $v$ to the back of the queue.
2. $\mathrm{dequeue}()$: Removes and returns the element at the front of the queue.
3. $\mathrm{peek}()$: Returns the element at the front without removing it.

Visual Representation

A queue can be conceptualised as a sequence of elements where insertion and deletion happen at opposite ends:

Implementation

Array-based (Circular Buffer)

Using a fixed-size array, the queue uses two pointers, front and back. To avoid wasting space, the indices wrap around using modulo arithmetic:

• $\mathrm{back}=(\mathrm{back}+1)(\mathrm{mod}n)$
• $\mathrm{front}=(\mathrm{front}+1)(\mathrm{mod}n)$

Linked List

Using a singly linked list with a tail pointer:

• $\mathrm{enqueue}$ is an $O(1)$ operation (append to tail).
• $\mathrm{dequeue}$ is an $O(1)$ operation (remove from head).

Complexity

Operation	Time Complexity
$\mathrm{enqueue}$	$O(1)$
$\mathrm{dequeue}$	$O(1)$
$\mathrm{peek}$	$O(1)$
$\mathrm{search}$	$O(n)$