04 - Lists, Stacks, Queues, and Deques

A text editor has to undo the last change, a browser has to go back to the previous page, a printer has to serve jobs in the order in which they arrived, an emergency room has to let the red code go first. These are four different behaviors (last in, first out; first in, first out; both ends; by priority) and each has a name and a structure. The wrong choice is not visible with ten elements and ruins you with a hundred thousand, which is why here every cost is a count and every structure is written and tested.

This is the fourth article in the Algorithms and Data Structures series. It helps to have read the amortized analysis of the first article, because it will reappear twice, and the one on search and hash tables, whose resizing you find again here. The listings are in Python 3.14 with the standard library only (python3 -I), the outputs are the ones obtained by running them twice with an identical result, and the independent reference for each structure is almost always the standard library implementation on random sequences with a fixed seed.

Dynamic array or linked list: who pays for what

A dynamic array keeps the elements contiguous in memory: reading index k is a single access, but inserting in the middle forces you to move everything that follows. A linked list keeps each element in a node that points to the next: inserting after a node you have already reached costs one pointer, but reaching the k-th costs k hops. The listing implements both and counts the array's moves and the list's hops, after testing them against list on 3,000 insertions and reads at random positions.

# Dynamic array versus linked list: count the element moves and the hops between nodes
import random

class ArrayList:
    def __init__(self):
        self.buf, self.n, self.cost = [None] * 4, 0, 0
    def insert(self, i, x):
        if self.n == len(self.buf):                  # full: double and copy
            new = [None] * (2 * len(self.buf))
            for j in range(self.n):
                new[j] = self.buf[j]; self.cost += 1
            self.buf = new
        for j in range(self.n, i, -1):               # shift right everything after i
            self.buf[j] = self.buf[j - 1]; self.cost += 1
        self.buf[i] = x
        self.n += 1
    def get(self, i):
        return self.buf[i]                           # a single access, no cost to count
    def to_list(self):
        return self.buf[:self.n]

class Node:
    __slots__ = ("val", "next")
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

class LinkedList:
    def __init__(self):
        self.head, self.n, self.cost = None, 0, 0
    def insert(self, i, x):
        if i == 0:
            self.head = Node(x, self.head)
        else:
            node = self.head
            for _ in range(i - 1):                   # one hop for every node traversed
                node = node.next; self.cost += 1
            node.next = Node(x, node.next)
        self.n += 1
    def get(self, i):
        node = self.head
        for _ in range(i):
            node = node.next; self.cost += 1
        return node.val
    def to_list(self):
        out, node = [], self.head
        while node:
            out.append(node.val); node = node.next
        return out

rng = random.Random(10)
for cls in (ArrayList, LinkedList):                  # correctness against list: 3000 random insertions and reads
    s, ref = cls(), []
    for t in range(3000):
        i = rng.randint(0, len(ref))
        s.insert(i, t); ref.insert(i, t)
        j = rng.randrange(len(ref))
        assert s.get(j) == ref[j]
    assert s.to_list() == ref
print("ArrayList and LinkedList consistent with list on 3000 operations")

print(f"{'operation on n=1000':<28} {'array: moves':>19} {'list: hops':>13}")
for label, pos in (("insert at the head", 0), ("insert in the middle", 500), ("insert at the tail", 1000)):
    a, l = ArrayList(), LinkedList()
    for k in range(1000):
        a.insert(a.n, k); l.insert(l.n, k)
    a.cost = l.cost = 0                              # the counter is reset: only the measured operation counts
    a.insert(pos, -1); l.insert(pos, -1)
    print(f"{label:<28} {a.cost:>19} {l.cost:>13}")
l.cost = 0
l.get(999)
print(f"{'read index 999':<28} {'0':>19} {l.cost:>13}")

# Output:
# ArrayList and LinkedList consistent with list on 3000 operations
# operation on n=1000                 array: moves    list: hops
# insert at the head                          1000             0
# insert in the middle                         500           499
# insert at the tail                             0           999
# read index 999                                 0           999

The output shows two opposite profiles on a structure of a thousand elements. Inserting at the head costs the array 1,000 moves and the list zero hops; inserting in the middle costs 500 against 499; reading the last index costs the array one access and the list 999 hops. The list wins only when the insertion point is already in hand (a cursor, the head); as soon as you have to reach it, the cost of finding it cancels the gain. Inserting at the tail of the list costs 999 hops because this version does not keep a pointer to the last node: with that pointer it would be constant, but it is an optimization I chose not to implement, so as not to confuse the two costs.

There is a third cost that these counts do not see: memory locality. In the array neighboring elements are close together, in the list the nodes can be anywhere. I did not measure it (these are counts, not times) and I do not quote a factor: it is enough for you to know that at equal count the array has a head start, and it is the reason why Python's list, which is a dynamic array, is the default choice. For amortized insertion at the tail, what was seen in the first article applies, and in Python the operation l.pop(k) costs O(n − k) according to the documentation.

Stack: last in, first out

A stack has two operations, push and pop from the top, and both have constant cost. The structure is needed every time you have to remember "where to return" in reverse order: undo, recursion, parsing. The classic example is checking that round, square and curly brackets are balanced. Every opening is pushed, every closing must match the last one opened and not yet closed. The listing stops at the first error and compares the result with a completely different reference: repeatedly deleting the adjacent empty pairs (), [], {} until the string no longer changes.

# Stack (LIFO): balanced brackets. The check stops at the first error
import random

PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(s):
    stack, ops = [], 0
    for ch in s:
        if ch in "([{":
            stack.append(ch); ops += 1               # open: push
        elif ch in PAIRS:
            ops += 1
            if not stack or stack.pop() != PAIRS[ch]:    # close: it must match the last one opened
                return False, ops
    return not stack, ops

def balanced_reference(s):                           # independent reference: delete adjacent pairs as long as possible
    prev = None
    while prev != s:
        prev, s = s, s.replace("()", "").replace("[]", "").replace("{}", "")
    return s == ""

rng = random.Random(11)
positives = 0
for _ in range(20000):
    s = "".join(rng.choice("()[]{}") for _ in range(rng.randrange(0, 13)))
    ok, ops = balanced(s)
    assert ok == balanced_reference(s) and ops <= len(s)    # each character costs at most one operation
    positives += ok
print("20000 random strings: they agree with the reference; balanced:", positives)

for s in ("{[()()]}", "([)]", "((", "())"):
    print(f"{s!r:>12} ->", balanced(s))

# Output:
# 20000 random strings: they agree with the reference; balanced: 1683
#   '{[()()]}' -> (True, 8)
#       '([)]' -> (False, 3)
#         '((' -> (False, 2)
#        '())' -> (False, 3)

On 20,000 random strings of length up to 12 the two methods always agree (1,683 are balanced), and the number of operations on the stack never exceeds the length of the string: every character is pushed or popped at most once, so the check is linear. The four final lines show the interesting cases: ([)] has the same number of opens and closes as a correct expression but fails at the third operation, because the stack cannot answer "yes" to a closing that does not match the top. A simple bracket counter would not see it.

In Python the stack is a list with append and pop, because both work on the final end and are O(1), amortized for append. No dedicated class is needed unless you want to prevent access to the middle. The same stack, used by the runtime for function calls, has a depth limit: if a recursion is as deep as the input, converting it into a loop with an explicit stack, as in the quick sort of the second article, is the standard fix.

Queue: first in, first out, with two stacks

A queue returns the elements in arrival order. It can be built with two stacks: new requests are pushed onto one (the "inbox"), and when you need to extract you take from the second (the "outbox"); only when this is empty do you transfer the whole first stack, which reverses the order and puts the oldest on top. The listing tests it against collections.deque on 50,000 random operations and counts the transfers.

# FIFO queue built with two stacks: amortized O(1) cost, but a single dequeue can cost n
import random
from collections import deque

class TwoStackQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []
        self.moves = 0                               # transfers from one stack to the other
        self.worst_dequeue = 0
    def enqueue(self, x):
        self.inbox.append(x)
    def dequeue(self):
        cost = 1
        if not self.outbox:                          # only if the outbox stack is empty is everything transferred
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.moves += 1; cost += 1
        self.worst_dequeue = max(self.worst_dequeue, cost)
        return self.outbox.pop()

# correctness against collections.deque on 50000 random operations (fixed seed)
rng = random.Random(12)
q, ref, pushes = TwoStackQueue(), deque(), 0
for step in range(50000):
    if ref and rng.random() < 0.45:
        assert q.dequeue() == ref.popleft()
    else:
        q.enqueue(step); ref.append(step); pushes += 1
assert q.moves <= pushes                             # each element is transferred AT MOST once
print(f"consistent with deque; enqueue: {pushes}, total transfers: {q.moves} (<= enqueue)")

# the unfavorable case: n enqueues and then n dequeues in a row
for n in (1000, 100000):
    q = TwoStackQueue()
    for k in range(n):
        q.enqueue(k)
    for k in range(n):
        assert q.dequeue() == k
    print(f"n={n}: total transfers {q.moves}, per element {q.moves / n:.2f}, most expensive dequeue {q.worst_dequeue}")

# Output:
# consistent with deque; enqueue: 27266, total transfers: 24353 (<= enqueue)
# n=1000: total transfers 1000, per element 1.00, most expensive dequeue 1001
# n=100000: total transfers 100000, per element 1.00, most expensive dequeue 100001

Each element is transferred at most once, so the total transfers do not exceed the enqueue operations (24,353 against 27,266 in the random sequence, and exactly n in the unfavorable scenario). The amortized cost of an operation is therefore constant: it is a count, you had seen the logic of it in the first article. But the "most expensive dequeue" is 1,001 with a thousand elements and 100,001 with a hundred thousand: a single extraction can cost n. If you have a maximum latency to guarantee, this queue is fine for throughput, not for the worst case.

Deque: both ends at constant cost

A deque (double-ended queue) adds and removes at both ends. The natural way to build it is a circular buffer: an array with a head index, in which "before position 0" is the last cell, and which doubles when it fills up. The listing implements it and verifies it against collections.deque on 50,000 mixed operations (append, appendleft, pop, popleft), also checking the length at every step.

# Deque on a circular buffer: amortized O(1) at both ends. Then: why list.pop(0) is a mistake
import random, time
from collections import deque

class RingDeque:
    def __init__(self):
        self.buf, self.head, self.n = [None] * 4, 0, 0
    def _grow(self):
        if self.n == len(self.buf):
            old = [self.buf[(self.head + i) % len(self.buf)] for i in range(self.n)]
            self.buf, self.head = old + [None] * len(old), 0
    def append(self, x):
        self._grow(); self.buf[(self.head + self.n) % len(self.buf)] = x; self.n += 1
    def appendleft(self, x):
        self._grow(); self.head = (self.head - 1) % len(self.buf); self.buf[self.head] = x; self.n += 1
    def pop(self):
        i = (self.head + self.n - 1) % len(self.buf)
        x, self.buf[i] = self.buf[i], None; self.n -= 1
        return x
    def popleft(self):
        x, self.buf[self.head] = self.buf[self.head], None
        self.head = (self.head + 1) % len(self.buf); self.n -= 1
        return x

rng = random.Random(13)
d, ref = RingDeque(), deque()
for step in range(50000):                            # 50000 random operations on the two ends
    op = rng.randrange(4)
    if op == 0:
        d.append(step); ref.append(step)
    elif op == 1:
        d.appendleft(step); ref.appendleft(step)
    elif ref and op == 2:
        assert d.pop() == ref.pop()
    elif ref:
        assert d.popleft() == ref.popleft()
    assert d.n == len(ref)
print("RingDeque consistent with collections.deque on 50000 operations; elements left:", d.n)

# emptying a queue of n elements with list.pop(0): every extraction moves all the others
for n in (1000, 2000, 4000):
    print(f"n={n}: moves with pop(0) = n(n-1)/2 = {n * (n - 1) // 2}; with deque.popleft = 0")

# indicative measurement: only the order of magnitude of the ratio is reported, which changes from machine to machine
n = 30000
lst, dq = list(range(n)), deque(range(n))
t0 = time.perf_counter()
while lst:
    lst.pop(0)
t_list = time.perf_counter() - t0
t0 = time.perf_counter()
while dq:
    dq.popleft()
t_deque = time.perf_counter() - t0
print("emptying 30000 elements: pop(0) more than 10 times slower than popleft?", t_list > 10 * t_deque)

# Output:
# RingDeque consistent with collections.deque on 50000 operations; elements left: 74
# n=1000: moves with pop(0) = n(n-1)/2 = 499500; with deque.popleft = 0
# n=2000: moves with pop(0) = n(n-1)/2 = 1999000; with deque.popleft = 0
# n=4000: moves with pop(0) = n(n-1)/2 = 7998000; with deque.popleft = 0
# emptying 30000 elements: pop(0) more than 10 times slower than popleft? True

The instructive part is the comparison with list.pop(0). Python's documentation says that lists, optimized for fixed-length operations, incur O(n) memory movement costs for pop(0) and insert(0, v), and recommends the deque for working at both ends; the same goes for collections.deque, which guarantees thread-safe appends and pops with approximately the same O(1) performance from either side. In the model of the listing, emptying a queue of n elements with pop(0) moves n(n − 1)/2 elements in total (7,998,000 with n = 4,000), against zero for the deque. The indicative measurement of the last line confirms the order of magnitude (more than ten times slower with 30,000 elements on this machine): it is the only time in this article, and it should not be read as a value but as a threshold, because it changes between machines and runs.

The practical consequence is simple. A list as a queue works as long as it has a few dozen elements, and becomes the bottleneck when it grows. If you are writing a breadth-first traversal of a graph, as you will see in the article on BFS and DFS, the frontier to explore is a queue, and the right structure is the deque.

Priority queue: the binary heap

A priority queue always returns the smallest (or largest) element among those present, not the oldest. The standard implementation is a binary heap: a tree stored in an array in which every node is smaller than its children, so the minimum is always at position 0. Inserting adds at the end and sifts up swapping with the parent as long as needed; extracting replaces the root with the last element and sifts it down. The listing implements the heap counting the comparisons and verifies it against heapq, both with mixed operations and by emptying it.

# Priority queue: binary min-heap with counted comparisons, verified against heapq
import heapq, random

class MinHeap:
    def __init__(self):
        self.a, self.comparisons = [], 0
    def _less(self, x, y):
        self.comparisons += 1
        return x < y
    def push(self, x):
        a = self.a; a.append(x); i = len(a) - 1
        while i > 0 and self._less(a[i], a[(i - 1) // 2]):       # sifts up while smaller than its parent
            a[i], a[(i - 1) // 2] = a[(i - 1) // 2], a[i]
            i = (i - 1) // 2
    def pop(self):
        a = self.a; top, last = a[0], a.pop()
        if a:
            a[0], i = last, 0
            while True:                                          # sifts down swapping with the smaller child
                c = 2 * i + 1
                if c >= len(a):
                    break
                if c + 1 < len(a) and self._less(a[c + 1], a[c]):
                    c += 1
                if not self._less(a[c], a[i]):
                    break
                a[i], a[c] = a[c], a[i]; i = c
        return top

rng = random.Random(14)
for _ in range(500):                                             # mixed operations, comparison with heapq
    h, ref = MinHeap(), []
    for _ in range(200):
        if ref and rng.random() < 0.4:
            assert h.pop() == heapq.heappop(ref)
        else:
            v = rng.randrange(1000); h.push(v); heapq.heappush(ref, v)
    assert [h.pop() for _ in ref] == [heapq.heappop(ref) for _ in range(len(ref))]
print("MinHeap consistent with heapq on 500 mixed sequences of push and pop")

class C:                                                         # heapq's heapify works in place: a class records the comparisons
    calls = 0
    def __init__(self, k): self.k = k
    def __lt__(self, o): C.calls += 1; return self.k < o.k

print(f"{'n':>6} {'n push (random)':>17} {'n push (decreasing)':>21} {'heapq heapify':>17} | {'mean pop':>10} {'2 lg n':>7}")
for n in (1000, 10000):
    vals = rng.sample(range(10**6), n)
    h = MinHeap()
    for v in vals:
        h.push(v)
    c_random = h.comparisons
    h2 = MinHeap()
    for v in range(n, 0, -1):                                    # worst case for insertion: each new one is the minimum
        h2.push(v)
    c_worst = h2.comparisons
    h.comparisons = 0
    for _ in range(n):
        h.pop()
    C.calls = 0
    arr = [C(v) for v in vals]
    heapq.heapify(arr)
    print(f"{n:>6} {c_random:>17} {c_worst:>21} {C.calls:>17} | {h.comparisons / n:>10.1f} {2 * (n.bit_length() - 1):>7}")

# equal priority: an arrival counter in the tuple keeps FIFO order among equal elements
tasks, h, count = [("print", 2), ("backup", 1), ("mail", 2), ("log", 1)], [], 0
for name, prio in tasks:
    heapq.heappush(h, (prio, count, name)); count += 1
print("output order:", [heapq.heappop(h)[2] for _ in range(len(tasks))])

# Output:
# MinHeap consistent with heapq on 500 mixed sequences of push and pop
#      n   n push (random)   n push (decreasing)     heapq heapify |   mean pop  2 lg n
#   1000              2248                  7987              1639 |       15.0      18
#  10000             22703                113631             16443 |       21.7      26
# output order: ['backup', 'log', 'print', 'mail']

The numbers have three readings. Building a heap with n insertions costs about 2.2 comparisons per element on random data (2,248 for n = 1,000), but 7,987 if every new element is the minimum (decreasing sequence): it is the worst case of insertion, close to n lg n. Building it in one go with heapq.heapify costs fewer than 2n comparisons (1,639 against 2,000), because it works from the bottom: the nodes close to the leaves have little to sink. And each extraction costs on average 15.0 comparisons at n = 1,000 and 21.7 at n = 10,000, within the limit 2·⌊lg n⌋ (18 and 26). So inserting and removing are O(log n), and building from a ready-made list is worthwhile.

The last line solves a practical problem: if two tasks have the same priority, the heap does not guarantee that they come out in arrival order (the heapq documentation notes that sorting done with a heap is not stable). The solution is the one recommended by the documentation: put an arrival counter in the tuple as a second criterion. In the listing "backup" and "log" (priority 1) come out in the order they arrived, then "print" and "mail" (priority 2). For comparisons between elements that cannot be compared, the counter also avoids the comparison error between the tasks themselves.

Synchronized structures: queue.Queue between threads

When several threads use the same queue, the shared state must be protected. The standard library's queue module provides FIFO, LIFO and priority queues that, as the documentation says, implement all the required locking semantics. The listing puts three producers and two consumers on a queue limited to eight slots, in a single process and without opening ports, and verifies that no item is lost or duplicated.

# queue.Queue is already synchronized: three producers and two consumers in the same process (no network, no port)
import queue, threading

q = queue.Queue(maxsize=8)                       # bounded queue: put() blocks if it is full
results, lock = [], threading.Lock()
PRODUCERS, ITEMS = 3, 1000

def producer(pid):
    for i in range(ITEMS):
        q.put((pid, i))

def consumer():
    while True:
        item = q.get()
        if item is None:                         # sentinel: end of work
            q.task_done()
            return
        with lock:
            results.append(item)
        q.task_done()

consumers = [threading.Thread(target=consumer) for _ in range(2)]
producers = [threading.Thread(target=producer, args=(p,)) for p in range(PRODUCERS)]
for t in consumers + producers:
    t.start()
for t in producers:
    t.join()
for _ in consumers:
    q.put(None)
for t in consumers:
    t.join()

print("items delivered:", len(results), "out of", PRODUCERS * ITEMS)
print("none lost or duplicated:", sorted(results) == sorted((p, i) for p in range(PRODUCERS) for i in range(ITEMS)))
# with TWO consumers the order of writing into 'results' is not guaranteed; the order of RETRIEVAL is: it is checked with just one
q2 = queue.Queue()
for i in range(5):
    q2.put(i)
print("a single consumer, retrieval order:", [q2.get() for _ in range(5)])

# Output:
# items delivered: 3000 out of 3000
# none lost or duplicated: True
# a single consumer, retrieval order: [0, 1, 2, 3, 4]

Two things to note. The queue has a maximum capacity (maxsize=8): when it is full put blocks the producer, and this passes the pressure upstream instead of letting memory grow without limit. And the retrieval order is FIFO, but the order in which two consumers write the result is not guaranteed: that is why the check compares sorted collections and not lists, and the retrieval order is verified with a single consumer. Java's concurrent queues (BlockingQueue, ConcurrentLinkedQueue) have similar purposes, but I did not run them for this article and I do not describe them.

Which structure to choose

• Access by index and insertions at the tail: dynamic array (list), with constant access and amortized append.
• Undo, recursion, parsing: stack, again a list used only from the end.
• Processing in arrival order: collections.deque, never list.pop(0).
• Always the most urgent first: heap, with heapq and an arrival counter for ties.
• Several threads: queue.Queue, with bounded capacity to pass the pressure along.

The entries are not interchangeable alternatives: each answers a different question about the order in which you want to retrieve the data. The question to ask is always the same, before choosing the name: in what order do I want back what I put in, and at which ends do I work? The linked list, which does not appear in the list, has a place only when you already have a cursor on the insertion point and need no access by index.

Exercises

1. Add to LinkedList a pointer to the last node and verify that insertion at the tail costs zero hops.
2. Extend the bracket check to return the position of the first error, and verify it against a brute-force reference.
3. Make the two-stack queue also report the maximum length reached by the outbox stack, and verify that it never exceeds the number of elements present in the queue.
4. Implement a max-heap by reversing the direction of the comparisons and verify it with heapq on the negated values.

The third exercise makes visible the invariant of the two-stack queue: the outbox stack contains the oldest elements in exit order, and once empty it is refilled only by transfer. The fourth is a habit to have: in Python heapq offers only the minimum, and the maximum is obtained by negating the keys.

Frequently asked questions

Why not use list.pop(0) for a queue?

Because every extraction moves all the other elements: emptying a queue of n elements costs n(n − 1)/2 moves. collections.deque extracts from the head at constant cost.

Is a queue with two stacks really O(1)?

It is on average: every element is transferred at most once, so the total transfers do not exceed the insertions. A single extraction can however cost n, if the outbox stack is empty.

How do you keep arrival order in a priority queue?

You insert into the heap a tuple (priority, arrival counter, task): on equal priority the counter decides, which is the tie-breaker indicated by the heapq documentation.

What you can do now

You can say which structure answers which retrieval order, and you can justify it with a count: array moves against list hops, amortized transfers of the two-stack queue, heap comparisons. You have written a circular deque, you have seen why pop(0) on a list is a mistake, and you can make tasks of equal priority come out in arrival order. In the article on binary search trees and AVLs the same idea of a structure in the array gives way to pointers, and the heap comes back as a tree.

The same series also includes the closing article on dynamic programming.