Basic Operations on a Queue

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)

⚠️

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.

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.

Next: queue variants — circular, deque, and priority queues.

Introduction Variants