Stack & Queue · 02 / 04

Queue & DequeQueues and deques

Circular array implementation, double-ended queues.

Used for: Job scheduling, message queues, BFS

Time complexityO(1)

Space complexityO(n)

DifficultyIntro

PrerequisitesArray & Dynamic Array, Stack

01Why it exists

Print spoolers, message queues and job scheduling

Several people send print jobs at once, and whoever sent theirs first should print first. Systems like Kafka and RabbitMQ line messages up the same way: producers add at the back, consumers take from the front.

Why this fitsA queue's first-in-first-out rule is the definition of fairness. Everyone can only join at the back, service always starts at the front, and nobody jumps the line.

Why BFS goes level by level

Breadth-first search has to finish everything at distance 1 before it looks at distance 2. What actually guarantees that order?

Why this fitsPush discovered nodes into a queue in order and always process the one discovered earliest. First in, first out automatically keeps "closest to the start goes first". The demo in the BFS lesson is a queue in motion.

Why using a Python list as a queue is slow

Someone dequeues with list.pop(0), and the program grinds to a halt once the data grows.

Why this fitsRemoving from the front of an array shifts every remaining element forward: O(n). A circular array advances head instead of moving anything, which is what deque does (a linked list of blocks, in fact). Once you know why, you know to switch to deque.

Reach for it when you see:First in first out, waiting in line, fair processing, level by level, BFS, producers and consumers, operations needed at both ends.

02The core idea

A queue takes items in at one end and lets them out at the other: enqueue adds at the back, dequeue removes from the front. That is first in, first out (FIFO) — whatever went in earliest comes out first. A stack remembers what happened most recently, a queue remembers what happened earliest; the two are a matched pair, and the difference between them is the difference between DFS and BFS.

Building a queue on a plain array has one trap: removing from the front means shifting everything behind it forward, which is O(n). The fix is a circular array. Keep head and size; dequeuing just moves head forward one slot, and the back of the queue sits at (head + size) % capacity, wrapping to 0 when it runs off the end. Both ends are then O(1), and the memory stays contiguous and cache-friendly. A linked list works too, at the cost of an extra pointer per node.

A deque (double-ended queue) allows adds and removes at both ends. It is a stack and a queue at once, and both Python's collections.deque and C++'s std::deque ship as standard. The monotonic queue in the next chapter is built on exactly this ability to pop from the back as well as the front.

03The algorithm

1When you need first-in-first-out, use deque in Python and std::queue in C++. Do not use a list's pop(0).
2To implement a fixed-capacity queue yourself, use a circular array: track head and size (not head and tail, which leaves empty and full indistinguishable).
3Enqueue: buf[(head + size) % cap] = x, then increment size. When it is full, either report failure or grow the buffer.
4Dequeue: head = (head + 1) % cap, then decrement size. Nothing is moved.
5The BFS skeleton: enqueue the start node, then while queue, dequeue one node, process it and enqueue any neighbour not yet seen. To split it into levels, record the queue's length at the top of each round.

04Interactive demo

A circular array of capacity 6. Enqueue a few times, then dequeue a few times, and watch tail wrap around to the front of the array while head advances without moving a single element.

Backing array (size 0 / 6)

[0]

tail

[1]

[2]

[3]

[4]

[5]

Logical order (front → back): empty

A circular array of capacity 6. head points at the front element; tail = (head + size) % 6 is the next free slot.

05Code

How to use the built-in deque and queue, the circular array implementation, and a queue built from two stacks — the example from the amortised analysis lesson, with the full code here.

from collections import deque

# Use deque, not list: list.pop(0) is O(n)
q = deque()
q.append(1)          # enqueue at the back, O(1)
q.append(2)
q.popleft()          # dequeue from the front, O(1) -> 1
q[0]                 # peek at the front

# A deque works at both ends, so it also serves as a stack or a sliding window
d = deque([1, 2, 3])
d.appendleft(0)      # push at the front
d.pop()              # remove from the back


# A fixed-capacity queue on a circular array (LeetCode 622)
class CircularQueue:
    def __init__(self, k):
        self.buf = [None] * k
        self.cap = k
        self.head = 0        # index of the front element
        self.size = 0

    def enqueue(self, x):
        if self.size == self.cap:
            return False
        tail = (self.head + self.size) % self.cap   # wraps around
        self.buf[tail] = x
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0:
            return False
        self.head = (self.head + 1) % self.cap      # nothing moves, head just advances
        self.size -= 1
        return True

    def front(self):
        return -1 if self.size == 0 else self.buf[self.head]


# A queue built from two stacks (LeetCode 232): amortised O(1)
class QueueWithStacks:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        if not self.outbox:                  # only pour across once outbox is empty
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

06Practice

LeetCode 232Implement Queue using StacksEasy
LeetCode 225Implement Stack using QueuesEasy
LeetCode 622Design Circular QueueMedium
LeetCode 933Number of Recent Calls (a sliding time window)Easy
LeetCode 102Binary Tree Level Order Traversal (a queue, level by level)Medium
LeetCode 641Design Circular DequeMedium

PreviousStack NextMonotonic Stack