---
title: 'Queues and Deques'
source: 'https://academia.sh/en/courses/data-structures/queues'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:57+00:00'
license: 'CC BY-SA 4.0'
---

# Queues and Deques

The first-in-first-out model, a queue in fixed memory using a circular buffer, the deque, and use cases.

The stack gives priority to the most recently added element. In some problems, the
expected behavior is exactly the reverse: in a job queue, the first to arrive must be
processed first; in a network buffer, packets must preserve their arrival order.

The **queue** is the abstract data type that defines this rule: **first in, first
out.**

## Queue Operations

| Operation | Meaning | Target cost |
|---|---|---|
| `enqueue` | Adds an element to the end | $O(1)$ |
| `dequeue` | Removes and returns the front element | $O(1)$ |
| `front` | Shows the front element without removing it | $O(1)$ |
| `is_empty` | Reports whether the queue is empty | $O(1)$ |

Its only difference from the stack is which end removal happens at. This small
difference makes the implementation noticeably harder: in a stack, both operations
are at the same end so a single index suffices, while in a queue the two ends must be
tracked separately.

## The Problem with a Naive Array Implementation

If a queue is built with a dynamic array, appending at the end is cheap, but taking
from the front requires shifting every element one position to the left — $O(n)$. In a
thousand-element queue, every `dequeue` call does a thousand shifts.

The first idea for avoiding the shift is to advance a head index: the element is not
deleted, it is just counted as "no longer in the queue." This makes `dequeue`
constant time but creates a new problem — space at the start of the array becomes free
and is never reclaimed. A queue that runs continuously grows its unused space without
bound.

## Circular Buffer

The solution is to wrap around to the start when the end of the array is reached. A
fixed-capacity block is treated as if its ends were joined together; this structure is
called a **circular buffer**.

Two indices are kept: `head` points to the next element to be taken; `tail` points to
the next position to be written. Advancing is done by taking the remainder modulo
capacity:

$$
\text{new position} = (\text{position} + 1) \bmod \text{capacity}
$$

The modulo operator was introduced in the Operators lesson; this use of it is its
canonical example.

```python
class CircularBuffer:
    """Fixed-capacity queue; wraps around to the start when it reaches the ends."""

    def __init__(self, capacity: int) -> None:
        self._data: list = [None] * capacity
        self._capacity = capacity
        self._head = 0
        self._count = 0

    def __len__(self) -> int:
        return self._count

    def is_full(self) -> bool:
        return self._count == self._capacity

    def is_empty(self) -> bool:
        return self._count == 0

    def enqueue(self, value) -> None:
        if self.is_full():
            raise OverflowError("buffer is full")
        tail = (self._head + self._count) % self._capacity   # position to write
        self._data[tail] = value
        self._count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("cannot dequeue from an empty buffer")
        value = self._data[self._head]
        self._data[self._head] = None                        # drop the reference
        self._head = (self._head + 1) % self._capacity       # wrap to the start
        self._count -= 1
        return value


queue = CircularBuffer(3)
queue.enqueue(12); queue.enqueue(18); queue.enqueue(7)
print(len(queue), queue.is_full())        # 3 True

print(queue.dequeue(), queue.dequeue())   # 12 18
queue.enqueue(25); queue.enqueue(14)      # written into freed slots by wrapping to the start
print(len(queue))                         # 3
print(queue.dequeue(), queue.dequeue(), queue.dequeue())   # 7 25 14
```

A buffer with capacity three has carried five elements: the new elements were written
into the freed positions by wrapping around to the start. No element was shifted, no
reallocation happened.

What happens on insertion into a full buffer is a design choice. Three options are
common: raising an error (as above), blocking the caller, or overwriting the oldest
element. The third is preferred in logging buffers that keep only the last $k$
measurements.

## A Queue with a Linked List

If a capacity limit is not wanted, a linked list that keeps both a head and a tail
pointer is used: appending at the end is done in constant time with the tail pointer,
and taking from the front with the head pointer.

Its cost was defined in the previous lesson: per-node pointer overhead and scattered
layout. The common practical solution is a combination of the two — the linked list's
nodes carry not a single element but small contiguous blocks. This achieves both
unbounded growth and reasonable cache behavior.

## Deque

A **deque** permits insertion and removal at both ends. It encompasses both the stack
and the queue: it behaves like a stack if only one end is used, and like a queue if
the two ends are used separately.

The circular buffer naturally supports the deque as well; the head index can also wrap
backward.

Its typical use is sliding-window problems: a new measurement enters at one end, and
whatever falls outside the window leaves at the other. This is the data-structure
counterpart of the sliding window pattern introduced in the Programming Fundamentals
course.

## Use Cases

- **Job queues.** In a producer–consumer arrangement, jobs are queued; order is
  preserved.
- **Buffering.** A circular buffer is used between two components running at
  different speeds; device communication in the How Computers Work course follows
  this arrangement.
- **Breadth-first search.** As will be seen in this course's final topic,
  layer-by-layer traversal in graphs runs on a queue.
- **Scheduling.** An operating system's ready-process list follows queue order under
  fair sharing.

In situations where what determines order is not arrival but priority, a queue is not
enough; a **priority queue** is required. That structure will be taken up in the heap
lesson of the trees topic.

## Queue Length Is a Metric

A queue is not only a data structure; it is an indicator of the speed difference
between two components. If queue length keeps growing, production is outpacing
consumption.

In an unbounded-capacity queue, this can stay hidden for a long time: no sign appears
until memory fills up, and then the system suddenly collapses. In a bounded-capacity
queue, a decision becomes necessary once the limit is reached — blocking the producer,
rejecting new work, or dropping the oldest item.

Blocking the producer is slowness propagating back toward the source, and it is
called **backpressure**. This concept, which came up in device-to-device
communication in the How Computers Work course, works the same way in distributed
systems.

For this reason, queue length is a monitored metric in production: its trend directly
shows where the bottleneck is.

## Cost Table

| Structure | Take from front | Insert at end | Insert at start | Capacity |
|---|---|---|---|---|
| Dynamic array (naive queue) | $O(n)$ | $O(1)$ amortized | $O(n)$ | Unbounded |
| Circular buffer | $O(1)$ | $O(1)$ | $O(1)$ | Fixed |
| Linked list (head + tail) | $O(1)$ | $O(1)$ | $O(1)$ | Unbounded |
| Deque | $O(1)$ | $O(1)$ | $O(1)$ | Varies |

## Summary

- The queue is defined by the first-in-first-out rule; its only difference from the
  stack is which end removal happens at.
- In a naive array implementation, taking from the front requires shifting; advancing
  a head index instead accumulates unused space.
- The circular buffer joins the ends with the modulo operator and makes both
  operations constant time with fixed capacity.
- Behavior on a full buffer — error, blocking, or overwriting — is a design decision.
- A linked list with head and tail pointers gives an unbounded-capacity queue; its
  cost is pointer overhead and locality.
- The deque permits both ends and is the natural structure for sliding-window
  problems.

## Next Step

So far, sequential access and operations at the ends have been covered. Search in a
sorted data set, however, is still linear: binary search cannot be done on a linked
list, because there is no jumping to the middle element. The next lesson takes up a
probabilistic solution that makes this jump possible by adding layers to the linked
structure.