Basic Operations on a Queue

Build a queue on a plain array and something strange happens: after enough enqueue/dequeue cycles it shouts Overflow — while holding a single element, with the array mostly empty. The naive design literally leaks usable space. The fix is one of the prettiest tricks in this whole topic, and it’s a single operator.

There are three reasonable ways to build a queue. We’ll do all three — they’re each instructive — and end with what you’d actually use in production.

The API is the same for all of them: enqueue, dequeue, peek, isEmpty.

In real code, reach for your language’s built-in: Python’s collections.deque, Java’s ArrayDeque (used as a queue), C++‘s std::queue. They’re already O(1) on both ends. But knowing how they work makes you a better engineer.

Part 1 — Linear array (the naive way)

Two indices: front (where to dequeue) and rear (where to enqueue lands).

Enqueue (insert at the rear)

ALGORITHM enqueue(val)
    if rear == MAX - 1
        report Overflow; return
    if front == -1 and rear == -1
        front = rear = 0
    else
        rear = rear + 1
    queue[rear] = val

Dequeue (remove from the front)

ALGORITHM dequeue()
    if front == -1 or front > rear
        report Underflow; return
    val = queue[front]
    if front == rear
        front = rear = -1     // queue is now empty
    else
        front = front + 1
    return val

Peek (look at the front)

Predict first

A linear-array queue has capacity 100. You enqueue and dequeue in a loop for a while. It now holds just ONE element — yet enqueue reports Overflow. Why?

⚠️

The big problem with the linear version: once front advances past slot 0, those slots are wasted forever (unless we shift, which is O(n) per dequeue). After enough enqueue/dequeue cycles, you’ll get Overflow even when the queue has only one element. That’s why we have the circular version below.

Part 2 — Circular array (the proper way)

Same idea, but front and rear wrap around using modular arithmetic. Capacity stays usable forever.

The state we need: a fixed-size array, front, rear, and an explicit count (cleaner than the “is front == rear empty or full?” trick).

Enqueue (wraps around)

ALGORITHM enqueue(val)
    if count == capacity
        report Overflow; return
    queue[rear] = val
    rear = (rear + 1) mod capacity
    count = count + 1

Dequeue (also wraps)

ALGORITHM dequeue()
    if count == 0
        report Underflow; return
    val = queue[front]
    front = (front + 1) mod capacity
    count = count - 1
    return val

See it wrap

Push past the end of the ring and watch rear jump back to slot 0:

Try it: Circular Queue

Watch how front and rear wrap around the ring with modular arithmetic.

Enqueue a few, dequeue from the front a couple of times, then enqueue some more. Notice that rear wraps around to fill the slots front left behind — that’s the win.

Recall the wrap

The entire fix is one operator on both indices. Fill in the lines that wrap rear and front:

python · fill in the blanks0/2 hints

def enqueue(self, val):
  if self.is_full():
      return
  self.data[self.rear] = val
  # ??? wrap the index back to 0 at the end
  self.count += 1
 
def dequeue(self):
  if self.is_empty():
      return None
  val = self.data[self.front]
  # ??? wrap the index back to 0 at the end
  self.count -= 1
  return val

Part 3 — Linked list (no fixed capacity)

Two pointers: head (front, where we dequeue) and tail (rear, where we enqueue). Both operations are O(1), no resizing.

Enqueue (append at the tail)

ALGORITHM enqueue(val)
    node = new Node(val)
    if tail == NULL
        head = tail = node
    else
        tail.next = node
        tail = node

Dequeue (remove from the head)

ALGORITHM dequeue()
    if head == NULL
        report Underflow; return
    val = head.data
    head = head.next
    if head == NULL
        tail = NULL          // queue is now empty
    return val

Walk through it

Trace on a linked-list-backed queue

Step 0 / 9 — (idle)

dequeue ←front

(empty)

← enqueuerear

size: 0

Part 4 — Just use the built-in

⚠️

Python gotcha: never use a list as a queue. list.pop(0) shifts every remaining element down — that’s O(n) per dequeue. Always use collections.deque.

Summary

	Linear array	Circular array	Linked list
Enqueue	O(1)	O(1)	O(1)
Dequeue	O(1)	O(1)	O(1)
Capacity	Fixed, wasteful	Fixed, fully reusable	Unbounded
Memory	Contiguous	Contiguous	Scattered + pointer cost
Best when	Almost never	Fixed-size, bounded buffer	Unknown / variable size

Linear is mostly a teaching tool — the circular version fixes its main flaw. In real code, the choice is between circular array (fixed, cache-friendly) and linked list (unbounded). Most standard libraries pick the array path with dynamic resizing.

Quick check

Why must you never use a plain Python list as a queue (with list.pop(0))?

You’ve now built a queue three ways and seen the modular-arithmetic trick that makes the circular version reusable. Next: queue variants — the deque (both ends), circular queue, and priority queue — each a small twist on what you just learned.

Introduction Variants

Finished this page?