Queues and deques

1.1The problem: a clinic's waiting room

Patients type their names into a computer as they arrive. When the doctor is free, the computer must return the name of the patient who arrived earliest among those still waiting. A stack would be exactly wrong here: it would call the most recent arrival first. We need the opposite discipline.

1.2The Queue ADT

A trace, written front … rear:

Compare with the same pushes on a stack: there, the first pop after pushing 5 and 3 returned 3. Here dequeue returns 5.

1.3Where queues appear

• A networked printer. Jobs from many computers wait in a queue and print in the order they were sent.
• A web server. Requests that arrive faster than they can be handled wait in a queue, so nobody is starved by later arrivals.
• Round-robin scheduling. The operating system gives each running program a short slice of CPU time in turn: dequeue a program, run it briefly, enqueue it again at the back (Part 5).
• Later in the course. Breadth-first search explores a graph level by level using a queue.

2.1Attempt 1: append and pop(0)

Enqueue with L.append(e) (O(1) amortized) and dequeue with L.pop(0). It is correct, but pop(0) removes the first slot of an array, and arrays have no gaps: every remaining element must shift one place left. With n elements that is n − 1 moves, so dequeue is Θ(n) in the worst case (Θ means “exactly this order”, both an upper and a lower bound).

from timeit import timeit

for n in [10_000, 20_000, 40_000]:
    t = timeit("while L: L.pop(0)", setup=f"L = list(range({n}))", number=1)
    print(f"dequeue all {n:>7,} with list.pop(0): {t:.3f} s")

dequeue all  10,000 with list.pop(0): 0.163 s
dequeue all  20,000 with list.pop(0): 0.514 s
dequeue all  40,000 with list.pop(0): 2.121 s

Doubling n roughly quadruples the time: emptying a queue of n elements this way costs about n²/2 moves.

2.2Attempt 2: a front index

Do not shift. Keep an index f of the current front; dequeue reads L[f], sets that slot to None, and does f = f + 1. Every operation is now O(1). But the lecture asks: what happens if we keep repeating enqueue and dequeue for a long time?

class LeakyQueue:
    """Implementation #2 from the lecture: never shift, just move f forward."""
    def __init__(self):
        self._data, self._f = [], 0
    def enqueue(self, e):
        self._data.append(e)
    def dequeue(self):
        answer = self._data[self._f]
        self._data[self._f] = None       # forget the element...
        self._f += 1                     # ...but the slot stays in the list
        return answer
    def __len__(self):
        return len(self._data) - self._f

Q = LeakyQueue()
for step in range(100_000):              # a busy server: one in, one out
    Q.enqueue(step)
    Q.dequeue()
print("elements in queue:", len(Q))
print("slots in the list:", len(Q._data))

elements in queue: 0
slots in the list: 100000

The queue is empty, yet the list has grown to 100,000 slots. The front of the list fills with dead None slots that are never reused, so memory grows with the total number of operations ever performed, not with the number of elements currently stored. On a server that runs for months, that is a memory leak.

2.3The fix: wrap around

The dead slots at the front are free space. Reuse them: treat an array of size N as a ring, where the slot after N − 1 is slot 0. Moving forward one place becomes

which is i + 1 normally and 0 when i = N − 1. Two indices describe the queue:

• f: the index of the front element (the next to be dequeued);
• r: the index immediately past the rear element (where the next enqueue will write).

2.4Why slot r is always kept empty

Start with an empty queue: f = r. Now enqueue until all N slots are used. r has moved N steps and wrapped right round, so again f = r. With only f and r to look at, “empty” and “full” would be indistinguishable.

The lecture's rule removes the ambiguity: never let the array become completely full. Slot r is always kept empty, so an array of N slots holds at most N − 1 elements, and

(The textbook's own code avoids the wasted slot by storing the size as a third variable instead of r. Both designs are correct; the lecture uses f and r, so this page does too.)

2.5The length formula

Why it works: in the normal configuration (f ≤ r) the elements occupy f, …, r − 1, so there are r − f of them. Adding N and taking mod N leaves r − f unchanged, because it is between 0 and N − 1. In the wrapped configuration (r < f), there are N − f elements from f to the end and r more from 0 to r − 1: total N − f + r, which is already below N. The single formula covers both cases.

Example: N = 8, f = 6, r = 2. Elements at 6, 7, 0, 1, so 4 elements; the formula gives (8 − 6 + 2) mod 8 = 4.

2.6The operations

Algorithm len():
    return (N - f + r) mod N

Algorithm isEmpty():
    return (f = r)

Algorithm enqueue(o):
    if len() = N - 1:              # full: only slot r is free
        Q = resize(Q, 2 * N)
    Q[r] = o
    r = (r + 1) mod N

Algorithm dequeue():
    o = Q[f]
    f = (f + 1) mod N
    if 0 < len() < N / 4:          # mostly empty
        Q = resize(Q, N / 2)
    return o

The lecture's pseudocode leaves out the empty check in dequeue; real code must raise an error when f = r.

2.7Resizing, and why the front moves to 0

You cannot simply copy the old array into the first half of a bigger one. In the wrapped configuration the queue would then have a hole in the middle: the part that wrapped round to slots 0, 1, … would sit before the front instead of after it. So resize walks the queue in queue order, starting at f and wrapping, and writes the elements into slots 0, 1, …, n − 1 of the new array. Then f = 0 and r = n.

Algorithm resize(Q, newLen):
    newQ = new array of length newLen
    n = len()
    walk = f
    for i = 0 to n - 1:
        newQ[i] = Q[walk]
        walk = (walk + 1) mod N
    Q = newQ;  N = newLen
    f = 0;  r = n

2.8Why shrink at a quarter, not a half

Shrinking keeps memory proportional to the current number of elements. The threshold matters. Suppose the rule were “halve when less than half full”, and the queue sits right at a boundary: an enqueue fills the array and doubles it to exactly half full; a dequeue drops below half and halves it back to full; the next enqueue doubles again. Every single operation would copy all n elements: O(n) each, forever. This is called thrashing.

With “halve below a quarter”, after any resize the array is about half full, so at least about N/4 cheap operations must happen before the next resize in either direction. Those cheap operations pay for the copying, and every operation stays O(1) amortized.

2.9The code and its cost

class Empty(Exception):
    pass

class CircularQueue:
    """FIFO queue on a circular array, exactly as in the lecture.
    f = index of the front element
    r = index just PAST the rear element (the next free slot)
    Slot r is always kept empty, so N slots hold at most N - 1 elements."""

    def __init__(self, N=4):
        self._Q = [None] * N
        self._f = 0
        self._r = 0

    def __len__(self):
        N = len(self._Q)
        return (N - self._f + self._r) % N

    def is_empty(self):
        return self._f == self._r

    def first(self):
        if self.is_empty():
            raise Empty("queue is empty")
        return self._Q[self._f]

    def enqueue(self, o):
        if len(self) == len(self._Q) - 1:          # only slot r is left: full
            self._resize(2 * len(self._Q))
        self._Q[self._r] = o
        self._r = (self._r + 1) % len(self._Q)     # step forward, wrapping

    def dequeue(self):
        if self.is_empty():
            raise Empty("queue is empty")
        o = self._Q[self._f]
        self._Q[self._f] = None                    # help garbage collection
        self._f = (self._f + 1) % len(self._Q)
        if 0 < len(self) < len(self._Q) // 4:      # mostly empty: shrink
            self._resize(len(self._Q) // 2)
        return o

    def _resize(self, new_len):
        old, n, walk = self._Q, len(self), self._f
        self._Q = [None] * new_len
        for i in range(n):                         # copy in QUEUE order...
            self._Q[i] = old[walk]
            walk = (walk + 1) % len(old)
        self._f, self._r = 0, n                    # ...so the front is at 0

A trace on an array of 4 slots, including a wrap-around and a resize:

Q = CircularQueue(4)
Q.enqueue(5); Q.enqueue(3)
print(len(Q), Q.dequeue(), Q.is_empty(), Q.dequeue(), Q.is_empty())
Q.enqueue(7); Q.enqueue(9)
print("array:", Q._Q, " f =", Q._f, " r =", Q._r)
Q.enqueue(4)                     # r wraps from 0 to 1; queue is now full
print("array:", Q._Q, " f =", Q._f, " r =", Q._r, " len =", len(Q))
Q.enqueue(6)                     # full (3 of 4), so resize to 8 first
print("array:", Q._Q, " f =", Q._f, " r =", Q._r, " len =", len(Q))

2 5 False 3 True
array: [None, None, 7, 9]  f = 2  r = 0
array: [4, None, 7, 9]  f = 2  r = 1  len = 3
array: [7, 9, 4, 6, None, None, None, None]  f = 0  r = 4  len = 4

Look at the third line: 4 was written into slot 0, before 7 and 9 in the array, but it is behind them in the queue. The fourth line shows the resize putting everything back in queue order.

The lecture spends several slides on puzzles: build a queue using only stacks, and a stack using only queues. Nobody does this in production; Python already has both. They are here because they force you to reason precisely about cost, and because one of them is the cleanest example of amortized analysis you will see.

3.1Queue from two stacks, strategy 1: keep the oldest on top

Keep all elements in stack A arranged so that the oldest is on top. Then dequeue is just A.pop() and first is A.top(), both O(1). The work moves to enqueue: the new element must go to the bottom of A. To get it there, pour all of A into B, push the new element onto the now-empty A, and pour B back.

Algorithm enqueue(e):          # O(n)
    while not A.is_empty():
        B.push(A.pop())         # A reversed into B
    A.push(e)                   # e goes to the bottom of A
    while not B.is_empty():
        A.push(B.pop())         # everything back on top of e

dequeue():  return A.pop()      # O(1)
first():    return A.top()      # O(1)
len():      return A.len()      # O(1)

Every enqueue moves every element twice: O(n) per enqueue, every time. There is no averaging that saves it.

3.2Strategy 2: pour only when needed

Let A be the inbox and B the outbox. Enqueue always pushes onto A. Dequeue pops from B. Only when B is empty does dequeue pour all of A into B.

Why does that give the right order? A holds elements newest on top. Popping A and pushing onto B reverses them, so the oldest ends up on top of B, exactly where dequeue wants it. And while B still has elements, they are all older than anything in A (they arrived before the last pour), so serving B first is correct.

enqueue(e):  A.push(e)                     # O(1)
len():       return A.len() + B.len()      # O(1)

Algorithm dequeue():
    if A.is_empty() and B.is_empty():
        return null                        # (or raise an error)
    if not B.is_empty():
        return B.pop()
    while not A.is_empty():
        B.push(A.pop())                    # pour: O(size of A)
    return B.pop()

# first() is identical, with B.top() instead of B.pop()

class TwoStackQueue:
    """Strategy 2: A receives, B serves. Pour A into B only when B is empty."""

    def __init__(self):
        self.A, self.B = ArrayStack(), ArrayStack()
        self.work = 0                              # count push/pop operations

    def __len__(self):
        return len(self.A) + len(self.B)

    def enqueue(self, e):
        self.A.push(e); self.work += 1             # O(1)

    def _pour(self):
        if self.B.is_empty():                      # only when B has run dry
            while not self.A.is_empty():
                self.B.push(self.A.pop()); self.work += 2

    def first(self):
        self._pour()
        return self.B.top()

    def dequeue(self):
        self._pour()
        self.work += 1
        return self.B.pop()

Q = TwoStackQueue()
for x in "ABC":
    Q.enqueue(x)
print(Q.dequeue(), end=" ")                         # pours C, B, A into B
Q.enqueue("D")
print(Q.dequeue(), Q.dequeue(), Q.dequeue())        # B, C come from B; D needs a pour

Q = TwoStackQueue()
n = 100_000
for i in range(n):
    Q.enqueue(i)
    if i % 3 == 2:
        Q.dequeue()
while len(Q):
    Q.dequeue()
print("operations per element:", Q.work / n)

A B C D
operations per element: 4.0

3.3The amortized argument, carefully

One dequeue can cost O(n): when B is empty and A holds n elements, it does n pops and n pushes. So the worst case per operation is O(n). The lecture's question is the amortized cost.

Count work per element, over its whole life in the queue:

The crucial fact is “at most once”: an element in B never goes back to A, so it can never be poured again. Over any sequence of m operations, at most m elements are ever enqueued, so the total work is at most 4m, plus O(1) of bookkeeping per operation. That is O(m) for m operations: O(1) amortized per dequeue (and per first).

The code above measures exactly 4.0 operations per element. This is the same “charge the work to the element” argument that showed spans are O(n) and appends are O(1) amortized.

3.4Queue from one stack plus recursion

Recursion gives you a second stack for free: the call stack. Each recursive call can pop an element and hold it in a local variable until the call returns.

Strategy 1 (expensive enqueue). Keep the oldest on top, so dequeue = A.pop() and first = A.top(), O(1). To enqueue e at the bottom: if A is empty, push e; otherwise pop the top into temp, recursively enqueue e into the rest, then push temp back. O(n).

Strategy 2 (expensive dequeue). Enqueue = A.push(e), O(1); the oldest is at the bottom. To dequeue, pop the top into temp; if A is now empty, temp was the bottom, so return it; otherwise recursively dequeue the rest, push temp back, and return what the recursion found. O(n). first() is the same but pushes the bottom element back too.

class OneStackQueue:
    """Strategy 2 with one stack: enqueue is a push; dequeue digs out the bottom."""

    def __init__(self):
        self.A = ArrayStack()

    def enqueue(self, e):
        self.A.push(e)                   # O(1)

    def dequeue(self):                   # O(n): recursion depth = len(A)
        temp = self.A.pop()
        if self.A.is_empty():            # temp was the bottom = the oldest
            return temp
        e = self.dequeue()               # the call stack holds what we popped
        self.A.push(temp)                # put each one back on the way out
        return e

Q = OneStackQueue()
for x in "ABCD":
    Q.enqueue(x)
print(Q.dequeue(), Q.dequeue(), "left (bottom to top):", Q.A._data)

A B left (bottom to top): ['C', 'D']

Here the O(n) is not amortized away: every dequeue digs to the bottom, because nothing is ever left in a convenient order.

3.5Stack from queues

The mirror-image puzzle. A queue only gives access to its oldest element, but a stack needs the newest. Each strategy pays O(n) somewhere to bring the newest to the front.

from collections import deque            # used here only as a plain FIFO queue

class StackPushHeavy:
    """Strategy 1 (two queues): push is O(n); pop and top are O(1)."""
    def __init__(self):
        self.q1, self.q2 = deque(), deque()
    def push(self, e):
        self.q2.append(e)                       # newest goes in first...
        while self.q1:
            self.q2.append(self.q1.popleft())   # ...then everything older behind it
        self.q1, self.q2 = self.q2, self.q1     # swap names
    def pop(self):
        return self.q1.popleft()

class StackPopHeavy:
    """Strategy 2 (two queues): push is O(1); pop and top are O(n)."""
    def __init__(self):
        self.q1, self.q2 = deque(), deque()
    def push(self, e):
        self.q1.append(e)
    def pop(self):
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())   # move all but the newest
        e = self.q1.popleft()                   # the newest = top of stack
        self.q1, self.q2 = self.q2, self.q1
        return e

class StackOneQueue:
    """Strategy 3 (one queue): rotate after each push so newest is at the front."""
    def __init__(self):
        self.q = deque()
    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
    def pop(self):
        return self.q.popleft()

for S in (StackPushHeavy(), StackPopHeavy(), StackOneQueue()):
    for x in [1, 2, 3]:
        S.push(x)
    print(type(S).__name__, S.pop(), S.pop(), S.pop())

StackPushHeavy 3 2 1
StackPopHeavy 3 2 1
StackOneQueue 3 2 1

4.1The clinic, modified

Two new rules: a VIP may be inserted at the front of the line, and the person at the end of the line may give up and leave. A queue cannot do either. We need adds and removals at both ends.

4.2The Deque ADT

A deque generalises both earlier ADTs. Use only add_last and delete_first and it is a queue; use only add_last and delete_last and it is a stack.

4.3Deque on the circular array

Two of the four operations are the queue's: add_last is enqueue and delete_first is dequeue. The other two move the indices backwards:

Algorithm add_first(o):
    if len() = N - 1:
        Q = resize(Q, 2 * N)
    f = (f - 1) mod N          # step back; from 0 this wraps to N - 1
    Q[f] = o

Algorithm delete_last():
    r = (r - 1) mod N          # the last element sits just before r
    o = Q[r]
    if 0 < len() < N / 4:
        Q = resize(Q, N / 2)
    return o

This is where Python's mod rule matters: (0 - 1) % 8 is 7, so stepping back from slot 0 lands on the last slot, as a ring should. (In C or Java, -1 % 8 is −1, and you would write (f - 1 + N) % N instead.)

D = CircularDeque(4)
D.add_last(5)                     # [5]
D.add_first(3)                    # [3, 5]   f steps back from 0 to 3
D.add_first(7)                    # [7, 3, 5]
print("array:", D._Q, " f =", D._f, " r =", D._r)
print(D.first(), D.last(), len(D))
print(D.delete_last(), D.delete_first(), D.first())

array: [5, None, 7, 3]  f = 2  r = 1
7 5 3
5 7 3

After adding 5 at the back and then 3 and 7 at the front, f has stepped back from 0 to 3 to 2: the front of the deque is in slot 2 and it wraps round to 5 in slot 0. All four operations are O(1) amortized, the same as the queue.

4.4Deque on a doubly linked list

Lecture 14 gives the other implementation: a doubly linked list, where each node links to both neighbours, with dummy header and trailer nodes at the ends. Adding or removing at either end then changes a fixed handful of links, so all four operations are O(1) in the worst case, not just amortized. The Linked Lists page builds it in detail.

from collections import deque
from timeit import timeit

d = deque()
d.append("B")                     # add_last
d.appendleft("A")                 # add_first
d.append("C")
print(d)
print(d.popleft(), d.pop(), d)    # delete_first, delete_last

n = 40_000
t = timeit("while d: d.popleft()", setup=f"from collections import deque; d = deque(range({n}))", number=1)
print(f"dequeue all {n:,} with deque.popleft(): {t:.4f} s")

deque(['A', 'B', 'C'])
A C deque(['B'])
dequeue all 40,000 with deque.popleft(): 0.0010 s

5.1Queue on a singly linked list

A singly linked list (Lecture 14) keeps a head and a tail reference. Its costs are lopsided: adding at the head or tail is O(1), removing at the head is O(1), but removing at the tail is O(n), because finding the node before the tail means walking from the head.

A queue adds at one end and removes at the other. Put the front at the head and the rear at the tail: enqueue adds at the tail (O(1)), dequeue removes at the head (O(1)). The opposite choice would make dequeue a tail removal, O(n).

class LinkedQueue:
    """FIFO queue on a singly linked list: front = head, rear = tail."""

    class _Node:
        __slots__ = "_element", "_next"
        def __init__(self, element, nxt):
            self._element, self._next = element, nxt

    def __init__(self):
        self._head = self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise IndexError("queue is empty")
        return self._head._element

    def enqueue(self, e):                     # add at the TAIL: O(1)
        newest = self._Node(e, None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest         # link the old tail first...
        self._tail = newest                   # ...then move tail
        self._size += 1

    def dequeue(self):                        # remove at the HEAD: O(1)
        if self.is_empty():
            raise IndexError("queue is empty")
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        if self.is_empty():
            self._tail = None                 # removed the only node
        return answer

Q = LinkedQueue()
for x in [5, 3, 8]:
    Q.enqueue(x)
print(Q.dequeue(), Q.first(), len(Q))

5 3 2

5.2Round-robin scheduling

A round-robin scheduler cycles through a collection forever, “servicing” each element in turn, such as giving each running program a slice of CPU time. With a queue, each turn is three steps: dequeue the next element, service it, enqueue it at the back.

Lecture 14 notes a leaner structure: a circularly linked list, whose tail links back to the head, kept by a single reference to the current node. Each turn services the front and calls rotate(), which moves one reference: no node is removed or created. Both are O(1) per turn; the circular list just does less work per turn.

Formulas to know cold

• Step forward: i ← (i + 1) mod N. Step back: i ← (i − 1) mod N.
• len = (N − f + r) mod N. Empty: f = r. Full: len = N − 1.
• After resize: f = 0, r = n.

Ideas to carry forward

1. The obvious implementation can be correct and still wrong: Θ(n) dequeues or unbounded memory.
2. Reusing space by wrapping is the general trick behind ring buffers, used everywhere from keyboards to network cards.
3. Shrink at a quarter, grow when full: the gap between the thresholds is what keeps resizing amortized O(1).
4. “Each element is moved at most once” is the shape of most amortized proofs.