DSA Linear Structures

Queues

Chat messages arrive at 2,000 per second. Workers must deliver them in send order so replies never appear before the messages they answer. A stack would reverse the conversation; a priority queue would reorder by size or sender rank.

A queue preserves arrival order among items that have not yet left. Enqueue at the ; dequeue at the . That contract is the abstraction algorithms rely on.

Algorithm journey

Oldest surviving work leaves first among accepted items.

Ends: /

State which index is next removal vs next insertion.

Ring, linked head+tail, or library deque at both ends.

Block, reject, drop, grow, or throw. Write it down.

What actually happens

Naive idea: append messages to a dynamic array and remove index 0. Order is correct, but each dequeue shifts every survivor. For n enqueues and n dequeues that is Θ(n²) moves.

Better idea: keep a index or a linked head so dequeue does not move survivors, and a or tail so enqueue stays Θ(1). The invariant: if a arrived before b and both still live, a leaves before b.

The improved design still fails when you shift with pop(0) / shift(), confuse empty with full in a ring, grow without copying logical order, or leave overload unbounded until memory dies.

Invariant (FIFO)

After every successful enqueue or dequeue, the relative order of every surviving item matches arrival order. The front is the oldest survivor; the rear is where the newest accepted item was published (or the next free slot, under a stated convention).

How to choose a queue

1. Does oldest-arrived work need to leave first? BFS, fair scheduling, and message delivery fit. Newest-first needs a stack; importance-first needs a priority queue.

2. Is capacity bounded? Choose a or bounded library queue and define : block, reject, drop, coalesce, or spill.

3. Strict worst-case latency? Fixed rings avoid resize spikes. Otherwise a library deque or resizable circular array is usually the simplest correct default.

Quantitative check

n dequeues that each shift the remaining array cost about 1 + 2 + … + (n − 1) = Θ(n²) moves. The same n dequeues with a front index or ring cost Θ(n) index updates and zero survivor moves. Unweighted BFS with a proper queue is Θ(V + E); the same algorithm with list.pop(0) can degrade toward Θ((V + E)·V) on dense frontiers.

FIFO invariant

If a was enqueued before b and neither is removed early by a special policy, a must be dequeued before b. Updates preserve the relative order of every surviving item.

Two logical ends

Front identifies the next item to remove. Rear often means the next free insertion slot, not necessarily the last occupied slot. State the convention before writing formulas.

Representation matters

FIFO says nothing about cost. Θ(1) operations require a deque, a ring buffer, or a linked list with both head and tail; shifting a flat array defeats the promise.

The abstraction in one sequence

emptyenqueue(A)[A]enqueue(B)[A, B]dequeue() → A[B]

Abstract state is the sequence from front to rear. An implementation is correct when every operation has the same observable effect as updating that sequence atomically.

Interactive queue demo

Enqueue items to the back and dequeue them from the front. Watch FIFO order stay intact.

ℹ️ Ready to queue items!

FRONT

REAR

Person A0

Person B1

Person C2

Operation contracts and honest costs

The starred bounds assume the implementation named in the precondition. They are not guaranteed by the word “queue” alone.

Operation	Touches	Time	Contract
enqueue(x)	Rear / next insertion position	Θ(1)*	Adds x after every item already present.
dequeue()	Front / oldest item	Θ(1)*	Removes and returns the oldest surviving item.
peek() / front()	Front / oldest item	Θ(1)	Reads without changing logical order or size.
size()	Stored count	Θ(1)	Requires maintaining metadata on every update.
is_empty()	Count or root handles	Θ(1)	Never scan the queue to discover emptiness.
contains(x)	No privileged position	Θ(n)	FIFO order provides no search-order shortcut.

What Θ(1)* means

A linked queue needs a tail reference; otherwise enqueue must traverse to the final node and becomes Θ(n). A dynamic circular array is amortized Θ(1), but an individual growth operation is Θ(n).

API failure semantics are part of the contract

Decide whether empty dequeue returns a sentinel, returns an optional value, throws, or blocks. If every value, including None or null: is legal, a sentinel result can be ambiguous.

Circular buffer: reuse slots instead of shifting

A ring maps logical offset i to physical slot (front + i) mod capacity. In this convention, front is the next removal slot and rear is the next insertion slot. A stored count distinguishes empty from full when those indices are equal.

Fixed-capacity queue · capacity 6

Watch logical order wrap around physical memory

Step through a trace that dequeues old values, reuses their slots, crosses the array boundary, becomes full, and rejects overflow.

front

rear

count

0/6

Start

Step 1 of 12

front ↓rear ↓

∅

slot 0

∅

slot 1

∅

slot 2

∅

slot 3

∅

slot 4

∅

slot 5

The buffer is empty. front = rear, and count = 0 tells us that no slot is occupied.

State test

count == 0 → empty

front = rear is ambiguous by itself; here count = 0 means empty.

Logical FIFO order

slot = (front + offset) mod 6

empty queue

Valid size

0 ≤ count ≤ C

Every successful enqueue increments once; every successful dequeue decrements once.

Physical position

slot(i) = (front + i) mod C

Logical order can cross the physical end without moving any surviving value.

Next insertion

rear = (front + count) mod C

This relation holds for the count-based representation after every completed operation.

The array-shift trap

Appending to a dynamic array is cheap, but removing index 0 usually shifts every survivor one slot left. A queue that repeatedly calls pop(0) can turn n dequeues into Θ(n²) total work.

Shifting representation

[A, B, C, D] → dequeue A

[B, C, D, _] · three moves

The physical array is kept left-aligned after every removal, which FIFO never requires.

Head index or ring

[A, B, C, D], front = 0

front = 1 · zero survivor moves

Reclaim abandoned prefix space periodically or wrap immediately with modular indexing.

In Python, prefer collections.deque.popleft(). In Java, prefer the Queue/Deque interface with ArrayDeque. JavaScript's Array.shift() should not be assumed Θ(1); a head index is a common algorithmic workaround.

Implementation choices

Representation	Mechanism	Strength	Cost / caveat
Circular array / ring buffer	Dense storage; front and rear wrap with modulo	Excellent locality, no per-item node	Fixed capacity unless a resize copies logical order
Resizable circular array	Ring buffer plus geometric growth	Amortized Θ(1) enqueue; cache-friendly	A resize is Θ(n), so latency is not strict Θ(1)
Singly linked list + tail	Head is front; tail is rear	Worst-case Θ(1) enqueue/dequeue; no resize	Allocation, pointer overhead, and weaker locality
Library deque	Usually a ring or blocks of arrays	Safe default; efficient at both ends	Exact layout and iterator rules depend on the library

Deque is an implementation capability; FIFO is a usage discipline. A deque permits updates at both ends. If code only appends at the rear and removes at the front, it is using that deque as a queue. A priority queue is different: removal follows priority, not arrival order.

Reference implementations

Prefer a standard library container unless fixed memory, predictable latency, or an embedded environment makes a custom ring necessary.

Python deque

python

from collections import deque

queue = deque()
queue.append("A")          # enqueue at rear
queue.append("B")

front = queue[0]           # peek; raises if empty
oldest = queue.popleft()   # dequeue from front
processed = queue.popleft() if queue else None

print(front, oldest, processed)  # A A B

Java ArrayDeque

java

import java.util.ArrayDeque;
import java.util.Queue;

final class QueueIdioms {
    public static void main(String[] args) {
        Queue<String> queue = new ArrayDeque<>();
        queue.offer("A"); // true for ArrayDeque; a bounded Queue may return false
        queue.offer("B");

        String front = queue.peek();    // "A"; null when empty
        String oldest = queue.poll();   // "A"; null when empty
        String processed = queue.poll(); // "B"

        System.out.println(front + " " + oldest + " " + processed); // A A B
    }
}

// add/remove/element are alternatives that throw on failure.
// Choose one failure convention and use it consistently.

Python ring

python

class RingQueue:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.data = [None] * capacity
        self.front = 0       # next removal slot
        self.rear = 0        # next insertion slot
        self.count = 0

    def enqueue(self, value):
        if self.count == len(self.data):
            return False     # explicit bounded-queue policy
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % len(self.data)
        self.count += 1
        return True

    def dequeue(self):
        if self.count == 0:
            raise IndexError("dequeue from empty queue")
        value = self.data[self.front]
        self.data[self.front] = None  # release reference
        self.front = (self.front + 1) % len(self.data)
        self.count -= 1
        return value

    def peek(self):
        if self.count == 0:
            raise IndexError("peek into empty queue")
        return self.data[self.front]

Java ring

java

import java.util.NoSuchElementException;

final class RingQueue<T> {
    private final Object[] data;
    private int front; // next removal slot
    private int rear;  // next insertion slot
    private int count;

    RingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        data = new Object[capacity];
    }

    boolean enqueue(T value) {
        if (count == data.length) return false; // bounded-queue policy
        data[rear] = value;
        rear = (rear + 1) % data.length;
        count++;
        return true;
    }

    @SuppressWarnings("unchecked")
    T dequeue() {
        if (count == 0) throw new NoSuchElementException("empty queue");
        T value = (T) data[front];
        data[front] = null; // release reference
        front = (front + 1) % data.length;
        count--;
        return value;
    }

    @SuppressWarnings("unchecked")
    T peek() {
        if (count == 0) throw new NoSuchElementException("empty queue");
        return (T) data[front];
    }
}

Another valid ring convention deliberately leaves one slot unused: empty when front == rear, full when (rear + 1) % C == front. An array of C slots then stores at most C − 1 items. Do not mix that convention with the count-based formulas above.

Why geometric growth is amortized Θ(1)

When an unbounded ring is full, allocate roughly twice the capacity and copy items in logical FIFO order, not raw physical order. Then set front = 0 and rear = count.

Python

python

def grow(self):
    old = self.data
    old_capacity = len(old)
    larger = [None] * (2 * old_capacity)

    for i in range(self.count):
        larger[i] = old[(self.front + i) % old_capacity]

    self.data = larger
    self.front = 0
    self.rear = self.count

Java

java

final class ResizableRingQueue<T> {
    private Object[] data;
    private int front;
    private int rear;
    private int count;

    ResizableRingQueue(int initialCapacity) {
        if (initialCapacity <= 0) throw new IllegalArgumentException();
        data = new Object[initialCapacity];
    }

    private void grow() {
        Object[] old = data;
        Object[] larger = new Object[2 * old.length];

        for (int i = 0; i < count; i++) {
            larger[i] = old[(front + i) % old.length];
        }

        data = larger;
        front = 0;
        rear = count;
    }
}

Aggregate argument

Across growth from 1 to n items, copies form a geometric sum: 1 + 2 + 4 + … < 2n. Spread over n enqueues, total work is Θ(n), so average cost per enqueue is Θ(1).

Latency caveat

Amortized does not mean every call is fast. Real-time systems often choose a fixed-capacity ring to keep each operation worst-case Θ(1), then define overflow behavior explicitly.

BFS: the queue controls discovery order

Breadth-first search dequeues vertices in nondecreasing distance from the sources. In an unweighted graph, every newly discovered edge extends a shortest known path by exactly one, and FIFO finishes the entire current frontier before deeper vertices.

Graph BFS

Python

python

from collections import deque

def bfs(graph, source):
    distance = {source: 0}
    parent = {source: None}
    queue = deque([source])

    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in distance:
                # Mark when enqueued, not when dequeued.
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)

    return distance, parent

Java

java

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

final class BreadthFirst {
    record Result<T>(Map<T, Integer> distance, Map<T, T> parent) {}

    static <T> Result<T> bfs(Map<T, List<T>> graph, T source) {
        Map<T, Integer> distance = new HashMap<>();
        Map<T, T> parent = new HashMap<>();
        Queue<T> queue = new ArrayDeque<>();
        distance.put(source, 0);
        parent.put(source, null);
        queue.offer(source);

        while (!queue.isEmpty()) {
            T vertex = queue.poll();
            for (T neighbor : graph.getOrDefault(vertex, List.of())) {
                if (!distance.containsKey(neighbor)) {
                    distance.put(neighbor, distance.get(vertex) + 1);
                    parent.put(neighbor, vertex);
                    queue.offer(neighbor);
                }
            }
        }
        return new Result<>(distance, parent);
    }
}

Level-order batches

Python

python

def level_order(root):
    if root is None:
        return []

    queue = deque([root])
    levels = []
    while queue:
        width = len(queue)       # snapshot this level's boundary
        level = []
        for _ in range(width):
            node = queue.popleft()
            level.append(node.value)
            queue.extend(node.children)
        levels.append(level)
    return levels

Java

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

final class LevelOrder {
    record Node<T>(T value, List<Node<T>> children) {}

    static <T> List<List<T>> traverse(Node<T> root) {
        if (root == null) return List.of();
        List<List<T>> levels = new ArrayList<>();
        Queue<Node<T>> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int width = queue.size(); // snapshot this level's boundary
            List<T> level = new ArrayList<>(width);
            for (int i = 0; i < width; i++) {
                Node<T> node = queue.remove();
                level.add(node.value());
                queue.addAll(node.children());
            }
            levels.add(level);
        }
        return levels;
    }
}

Multi-source BFS

Python

python

def nearest_source(graph, sources):
    distance = {}
    queue = deque()

    for source in sources:
        if source not in distance:  # deduplicate sources
            distance[source] = 0
            queue.append(source)

    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance

Java

java

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

final class MultiSourceBfs {
    static <T> Map<T, Integer> nearestSource(
            Map<T, List<T>> graph, Iterable<T> sources) {
        Map<T, Integer> distance = new HashMap<>();
        Queue<T> queue = new ArrayDeque<>();

        for (T source : sources) {
            if (distance.putIfAbsent(source, 0) == null) queue.offer(source);
        }

        while (!queue.isEmpty()) {
            T vertex = queue.poll();
            for (T neighbor : graph.getOrDefault(vertex, List.of())) {
                if (!distance.containsKey(neighbor)) {
                    distance.put(neighbor, distance.get(vertex) + 1);
                    queue.offer(neighbor);
                }
            }
        }
        return distance;
    }
}

Discovery invariant

discover once ⇒ enqueue once

Mark on enqueue so a vertex enters at most once, even if many frontier vertices point to it.

Distance invariant

front has minimum unsettled distance

All distance d vertices leave before distance d + 1 vertices in an unweighted graph.

Complexity

Θ(V + E) time · Θ(V) extra

With adjacency lists, each vertex enqueues once and each edge is examined once (twice for undirected storage).

Bounded queues turn overload into a policy

An unbounded queue can hide overload until memory is exhausted. A bounded queue makes capacity finite, so producers must react when arrivals outpace service. That reaction is backpressure when it slows or refuses upstream work.

Policy	When full	Semantic trade-off
Block producer	Wait until space exists	Preserves accepted work; pushes delay upstream
Reject / fail fast	Return an error immediately	Caller retries, degrades, or sheds load explicitly
Drop newest	Discard the arriving item	Protects backlog; suitable only when new work is expendable
Drop oldest	Evict front, then enqueue	Keeps data fresh but deliberately breaks ordinary queue retention
Coalesce / sample	Merge redundant work	Useful for refreshes, telemetry, and state updates
Spill durably	Move overflow to disk or a broker	Survives process loss at higher latency and complexity

Queue length is stored waiting work, not throughput. If sustained arrival rate exceeds sustained service rate, increasing capacity mainly delays the failure and increases waiting time. Capacity handles bursts; it cannot repair a permanently underprovisioned consumer.

Producer–consumer and concurrency caveats

Correct single-threaded indices do not make a queue safe for concurrent producers and consumers. Shared updates must appear atomic, and blocking queues must coordinate both “not empty” and “not full” conditions.

Use a concurrent queue abstraction

Prefer a language/runtime blocking queue, channel, or documented concurrent queue. It defines memory visibility, wakeups, contention behavior, and whether operations are linearizable.

Check-then-act races

is_empty() followed by dequeue() is not one atomic action: another consumer may win between calls. Use try-dequeue, a locked critical section, or a blocking take operation.

Wait in a loop

Condition-variable waits can wake spuriously, and another thread may consume the state first. Recheck the full/empty predicate while holding the associated lock.

Define shutdown

A consumer blocked forever after producers exit is a liveness bug. Close the queue, cancel waits, or enqueue an agreed sentinel, with one sentinel per consumer when required.

Terminal

enqueue(x):
  lock
  while count == capacity and queue is open: wait(not_full)
  if queue is closed: fail
  write x; increment count; signal(not_empty)
  unlock
 
dequeue():
  lock
  while count == 0 and queue is open: wait(not_empty)
  if count == 0 and queue is closed: report end-of-stream
  read item; decrement count; signal(not_full)
  unlock

This is monitor-style pseudocode, not a lock-free algorithm. Specialized single-producer/single-consumer rings can use atomic indices, but memory ordering and cache-line contention make that a separate concurrency topic.

Queue-shaped algorithm variants

Ordinary BFS

Use FIFO when every edge has equal unit cost. The queue orders nodes by hop distance.

0–1 BFS

Use a deque for edge weights 0 or 1: push a zero-cost relaxation to the front and a one-cost relaxation to the back.

Priority queue search

Use a heap for Dijkstra when nonnegative edge weights vary. This intentionally abandons FIFO for minimum tentative distance.

Monotonic deque

Maintain candidates at both ends for sliding-window extrema. It is not merely a FIFO queue because dominated rear elements are removed.

Round-robin scheduling

Dequeue a task, give it a time slice, then re-enqueue unfinished work. Fairness still depends on admission and task weights.

Work queues

Workers consume jobs from a shared queue; work stealing instead gives workers local deques to reduce contention and rebalance load.

Edge cases worth testing

Empty queue

peek/dequeue follows the documented failure policy; indices and count do not change.

One item

after its dequeue, both logical ends describe the same empty state.

Rear wraps

enqueue writes slot 0 after the final physical slot without reordering survivors.

Front wraps

dequeue advances from C − 1 to 0 and releases the removed reference.

Completely full

front may equal rear; count or a reserved slot disambiguates it from empty.

Overflow

reject, block, drop, overwrite, or grow exactly as the public contract states.

Resize while wrapped

copy front-to-rear logical order rather than raw array order.

Duplicate values

identity and arrival order remain distinct even when values compare equal.

Legal null values

do not also use null as an ambiguous empty result.

Capacity 0 or 1

validate capacity and exercise modulo/full logic at the smallest legal size.

Long wrap trace

run many more than C operations to expose stale slots and off-by-one errors.

Concurrent close

blocked producers and consumers wake and observe a defined terminal state.

How to choose among queue shapes

1
Does oldest-arrived work need to leave first?
If yes, begin with a FIFO queue. If removal depends on priority, use a priority queue; if both ends matter, use a deque.
2
Is capacity bounded?
Choose a ring or bounded library queue and write down what full means: block, reject, drop, coalesce, or spill.
3
Do you need strict worst-case latency?
A fixed ring avoids resizing. Otherwise a library deque or resizable circular array usually gives the best simplicity and locality.
4
Will multiple threads or processes touch it?
Use a concurrency-aware queue or channel; do not add ad hoc check-then-act logic around a single-threaded container.

Common failure modes

Order: enqueue at rear; dequeue oldest at front.
Indices: state whether rear is last item or next free slot.
Costs: include tail, capacity, and amortization preconditions.
Rings: use count or reserve a slot; never mix conventions.
BFS: mark discovered when enqueued, not when dequeued.
Systems: bound backlog, define overload, and define shutdown.

Exercises

Enqueue A, B, C then dequeue once. Which item leaves, and what is the front? Restate the invariant for the survivors.
Compare total move cost for n = 10⁵ dequeues using array pop(0) versus a front-index ring. When would you still prefer a linked queue with head and tail?
A ring of capacity 4 uses front == rear for both empty and full. Give a concrete fill/drain sequence that makes those states indistinguishable, then fix it with a count or a reserved slot.

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): queues and BFS with FIFO frontiers.
Python collections.deque documentation (amortized O(1) append/popleft).
Java Queue / ArrayDeque and BlockingQueue contracts (offer/poll vs add/remove; bounded backpressure).

Takeaway

A queue is a FIFO contract with two ends. Once front, rear, capacity, and empty/full policies are explicit, BFS, message pipelines, and ring buffers become variations of the same invariant with different overflow rules.