Queue

A queue is a FIFO (First In, First Out) data structure. Elements enter at the REAR and leave from the FRONT — just like a line of people waiting.

Interactive Visualization

NEW ITEMS →
enqueue
REAR
12
45
7
88
FRONT
31
← OUT
dequeue

🛒 Think of a checkout line: new shoppers join the back (REAR), the cashier serves from the front (FRONT). First in, first out.

Add element to the REAR. Always O(1) — direct write + pointer increment.
Enqueue
O(1)
Dequeue
O(1)
Peek / Search
O(1) / O(n)

Enqueue — step by step

Initial queue — 5 elements, 2 free slotslength=5 capacity=7
enqueue →
FRONT
12
[0]
45
[1]
7
[2]
88
[3]
REAR
31
[4]
free
[5]
free
[6]
← dequeue
FRONT (dequeue from here) REAR (enqueue here) enqueuing dequeuing
Our queue holds 5 elements with capacity for 7. The FRONT pointer marks where we dequeue; the REAR points to the next free slot. FIFO: first in, first out — like a line at a store.
🎮 Live Queue Playground
← enqueue (REAR)dequeue (FRONT) →
free
[3]
free
[4]
free
[5]
REAR
7
[2]
45
[1]
FRONT
12
[0]
length = 3capacity = 6front = 0rear = 2

How it Works

  • FIFO order: The first element enqueued is always the first one dequeued. No random access.
  • Two pointers: front tracks where to dequeue; rear tracks where to enqueue.
  • O(1) both ways: Enqueue and dequeue are both constant-time — neither requires shifting elements.
  • Overflow / Underflow: Enqueue on a full queue = overflow. Dequeue on an empty queue = underflow. Always guard against both.

Queue vs Array — Key Insight

Deleting from the front of an array costs O(n) because every element must shift left.

A queue uses a FRONT pointer instead of actually moving data — so dequeue is always O(1). This is the fundamental advantage of a queue over a raw array for FIFO access.

Full Operation Summary

OperationTimeSpaceNotes
enqueue(x)O(1) amortisedO(1)Write at rear, increment rear pointer
dequeue()O(1)O(1)Read front, advance front pointer — no shifting
peek() / front()O(1)O(1)Return arr[front] without modifying state
isEmpty()O(1)O(1)Check if front == -1 or length == 0
isFull()O(1)O(1)Check if rear == capacity − 1 (bounded queues)
search(x)O(n)O(1)Must scan all elements — no random access

Common Use Cases

BFS (Graph Traversal)

Breadth-first search uses a queue to visit nodes level by level.

Task Scheduling

OS process queues, printer spoolers, job queues — FIFO fairness.

Event Loops

Browser event queues, Node.js I/O callbacks — process events in order.

Buffering / Streaming

Network packets, video buffering — receive in order, process in order.

When NOT to Use a Queue

  • Need random access — queues don't support index lookup. Use an array.
  • Need LIFO order — use a Stack instead (push/pop from same end).
  • Need priority ordering — use a Priority Queue / heap for highest-priority-first.
  • Need both-end access — use a Deque (double-ended queue) for O(1) front and rear ops.