Queues

Abstract Data Type

A queue is a first-in, first-out (FIFO) collection. Elements are added at the rear and removed from the front. Operations:

Operation	Description
ENQUEUE(Q, x)	Add element $x$ to the rear of the queue
DEQUEUE(Q)	Remove and return the front element
FRONT(Q)	Return the front element without removing it
IS-EMPTY(Q)	Return true iff queue contains no elements

Circular Array Implementation

A fixed-capacity array Q[1..n] with two indices: head (front of queue) and tail (first free slot after the rear). Both wrap around modulo $n$ using an inc helper:

inc(x): return (x == Q.length) ? 1 : x + 1

• Initially: head = tail = 1 (empty queue).
• Enqueue: store at Q[tail], then tail = inc(tail).
• Dequeue: retrieve Q[head], then head = inc(head).
• Empty: head == tail.
• Full: inc(tail) == head (or equivalently head == tail + 1 modulo $n$).

All operations are $\Theta(1)$. At most $n-1$ items can be stored (one slot is sacrificed to distinguish full from empty, since both would have head == tail).

Linked List Implementation

Maintain head (front) and tail (rear) pointers. Enqueue adds at the tail, dequeue removes from the head. Both operations are $\Theta(1)$. No capacity limit.

ENQUEUE(Q, x):
    node = new Node(value=x, next=NIL)
    if Q.tail == NIL:
        Q.head = Q.tail = node
    else:
        Q.tail.next = node
        Q.tail = node

DEQUEUE(Q):
    if Q.head == NIL: error "empty"
    x = Q.head.value
    Q.head = Q.head.next
    if Q.head == NIL: Q.tail = NIL
    return x

Circular Buffer Variant

The circular array queue is also known as a circular buffer. It is widely used in operating systems for kernel pipes and I/O buffering. It avoids the allocation/deallocation overhead of linked lists and provides cache-friendly linear memory access.

Deque (Double-Ended Queue)

A deque supports insertion and deletion at both ends: PUSH-FRONT, PUSH-BACK, POP-FRONT, POP-BACK. It can be implemented with a doubly linked list or a circular array, all operations $\Theta(1)$. A deque generalises both stacks and queues.

Applications

Application	How the queue is used
Task scheduling	FIFO scheduling: tasks processed in arrival order
Breadth-first search	Discovered vertices are enqueued; processed in FIFO order
Print queues	Jobs printed in submission order
Buffering / I/O	Data buffered between producer and consumer (circular buffer)
Message passing	Messages delivered in order between threads/processes

Comparison: Stack vs. Queue

Aspect	Stack	Queue
Order	LIFO	FIFO
Insert called	Push	Enqueue
Remove called	Pop	Dequeue
Array implementation	One index (top)	Two indices (head, tail) with wrap
Full detection	top == n	inc(tail) == head
Applications	Recursion, undo, parsing	Scheduling, BFS, buffering

Summary

Property	Circular Array	Linked List
ENQUEUE	$\Theta(1)$	$\Theta(1)$
DEQUEUE	$\Theta(1)$	$\Theta(1)$
FRONT	$\Theta(1)$	$\Theta(1)$
IS-EMPTY	$\Theta(1)$	$\Theta(1)$
Max capacity	$n-1$ items	Unbounded
Space	$\Theta(n)$ pre-allocated	Per-element
Principle	FIFO