Queues: earliest waiting item first

After this page, you should be able to:

• Trace FIFO additions, observations and removals with explicit return values.

• Compare a restricted deque-backed interface with circular-array and linked queues.

Builds on: Stacks shows newest-first removal; a queue selects by arrival order.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

Julia uses one-based positions and named functions such as enqueue! rather than Python-style instance methods. Endpoint adapters use the supplied linked DequeBuffer, so they do not hide linear array-front shifts. Empty operations reject the request; null/nothing remain valid payloads.

Purpose and operation contracts¶

A queue inserts at the back and removes from the front. Its first in, first out (FIFO) rule selects the earliest inserted item still waiting. A name such as jobs does not enforce FIFO: adding and removing at the back gives LIFO instead.

The queue below grows without a configured capacity. The later fixed circular queue instead rejects a full enqueue with OverflowError, preserving every waiting item. It never silently evicts one. Duplicates and None are valid data in all these examples; a valid result of None is different from an empty-operation exception.

Representation, invariant and visual trace¶

In this adapter, the underlying deque’s left end is the front and its right end is the back. Its elements remain in arrival order, and its length is the queue size.

Python implementation¶

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def __len__(self):
        return len(self._items)

    def size(self):
        return len(self)

    def is_empty(self):
        return len(self) == 0

    def enqueue(self, item):
        self._items.append(item)

    def front(self):
        if self.is_empty():
            raise IndexError("front of empty queue")
        return self._items[0]

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

// DequeBuffer is defined in the downloadable shared support file.
class Queue {
    constructor() { this._items = new DequeBuffer(); }
    size() { return this._items.size(); }
    is_empty() { return this.size() === 0; }
    enqueue(item) { this._items.add_last(item); }
    front() { return this._items.peek_first(); }
    dequeue() { return this._items.remove_first(); }
}

mutable struct Queue
    items::DequeBuffer
end
Queue() = Queue(DequeBuffer())
Base.length(q::Queue) = q.items.n
Base.isempty(q::Queue) = length(q) == 0
enqueue!(q::Queue, item) = db_add_last!(q.items, item)
queue_front(q::Queue) = db_first(q.items)
dequeue!(q::Queue) = db_remove_first!(q.items)

Implementation choices and correctness¶

Appending at the right preserves the arrival order of all waiting items. Removing at the left selects exactly the oldest one and preserves the survivors’ order. Empty checks happen before removal, so a rejected request leaves the state unchanged. The wrapper exposes only queue operations even though its underlying deque supports more.

Using a Python list with pop(0) would also give correct FIFO results, but shift remaining references. The circular-array and head/tail linked readings show how endpoint operations work without delegating them to a library deque. This adapter is complete queue code, not an implementation of the deque’s internal storage.

Time and space costs¶

The underlying deque provides approximately O(1) endpoint additions/removals and O(1) endpoint access. Thus each exposed operation takes O(1) under the ordinary container-operation model, with O(1) wrapper workspace. Queue storage is O(n+1) for n live items. Real allocation and payload destruction can add costs outside that model.

Fixed circular storage instead uses Θ(c) allocated slots even when empty; a linked queue stores O(n+1) nodes. These are representation costs, not guarantees attached to the word “queue.” See Python’s deque reference.

When to use it¶

FIFO suits print jobs and breadth-first graph traversal. Urgency requires a priority queue, which follows a different selection rule.

Check your understanding¶

Predict the operation result and the resulting state before opening the explanation.

1. Enqueue A and B, call front() twice, then dequeue. What is returned?

2. A capacity-two circular queue contains A,B. What happens on enqueue C?

Continue to both-end access¶

Deque operations¶

A deque adds/removes at both ends. Its separate contract, implementation and costs follow next.

Rolling windows¶

The latest-readings trace explains intentional eviction as a different contract from rejecting a full queue.

Palindromes¶

The two-end comparison example uses a deque to remove matching endpoint characters.

Next: Deques.