The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Double-Ended Queues (Deques)

Next ►
►

This is the chapter where we settle the first debt from module 3. Our BoundedHistory pushed actions onto one end but, when full, discarded from the other with an O(n) pop(0) that we labeled "tolerable" at the time... while promising an elegant solution. The structure that fixes it is the double-ended queue, or deque: an ADT that allows inserting and removing in O(1) at both ends. Python ships it as collections.deque, which we already mentioned in passing in module 2 ("a block-based doubly linked list"); today we will study it in depth: its operations, its costs, its star parameter maxlen, and — just as important — when not to use it. We will also see that, in truth, we have almost written the conceptual implementation since module 2, and we will put it to work in TaskFlow with a sliding productivity window.

Contents

  1. The deque ADT: a contract with four doors
  2. Deque, stack, and queue: a generalization
  3. collections.deque in depth
  4. When NOT to use a deque
  5. The promise kept: BoundedHistory with maxlen
  6. Conceptual implementation on top of DoublyLinkedList
  7. TaskFlow: sliding window of completed tasks
  8. Classic bonus: palindromes

The deque ADT: a contract with four doors

A deque is a sequence with access restricted to the two ends, with all four combinations allowed:

Operation End Cost promise
enqueue_back(x) Right (back) O(1)
enqueue_front(x) Left (front) O(1)
dequeue_back() Right O(1)
dequeue_front() Left O(1)
front() / back() Inspect either end O(1)
is_empty() / size() — O(1) 
graph LR
    EF["enqueue_front / dequeue_front"] <--> D["[ front | ... | back ]"]
    D <--> EB["enqueue_back / dequeue_back"]

What remains forbidden — and this defines the deque against a general list — is touching the interior: there is no mid-sequence insertion or deletion in the contract. All the power is concentrated at the edges, and in exchange the edges are always O(1).

Deque, stack, and queue: a generalization

The deque is the most general of the three restricted-access ADTs we know; stack and queue are special cases obtained by closing doors:

To get... Use only... Resulting policy
A stack enqueue_back + dequeue_back LIFO (a single end)
A queue enqueue_back + dequeue_front FIFO (opposite ends)
A deque All four Both, chosen per operation

This explains why professional Python uses collections.deque as a stack and as a queue too: one well-built structure covers all three contracts. Beware, however, of the reverse reasoning: that it can be used in three ways does not mean your code should mix them. If your variable is conceptually a queue, use only the FIFO pair; the variable's name and the access discipline document the intent (it is the "expose only the contract" lesson from 04-02).

collections.deque in depth

collections.deque is the standard library's deque implementation. Internally — we previewed this in module 2 — it is a doubly linked list of blocks: instead of one node per element, it links blocks of 64 slots, which drastically reduces memory cost and the number of hops between nodes, while preserving O(1) at both ends.

Its correspondence with our contract:

ADT contract collections.deque Cost
enqueue_back(x) d.append(x) O(1)
enqueue_front(x) d.appendleft(x) O(1)
dequeue_back() d.pop() O(1)
dequeue_front() d.popleft() O(1)
front() / back() d[0] / d[-1] O(1)
size() len(d) O(1)
— (extra) d.extend(iterable), d.extendleft(iterable) O(k)
— (extra) d.rotate(n) (rotates n positions) O(min(n, len))
— (extra) maxlen (maximum length) — 
from collections import deque

d = deque(["B", "C"])       # can be created from any iterable
d.append("D")               # at the back:  B, C, D
d.appendleft("A")           # at the front: A, B, C, D
print(d[0], d[-1])          # A D  (inspecting the ends: O(1))
print(d.popleft())          # A    (FIFO if you combine append + popleft)
print(d.pop())              # D    (LIFO if you combine append + pop)
print(list(d))              # ['B', 'C']

Details worth knowing:

  • extendleft inserts the elements one by one on the left, so the iterable ends up reversed inside the deque: deque([3]); d.extendleft([2, 1]) produces 1, 2, 3. It is a common surprise.
  • rotate(1) moves the last element to the front (and rotate(-1) the other way): it is the "spin" of the CircularList from module 2, for free.
  • An empty deque raises IndexError on pop()/popleft(): the same EAFP policy we have been using in our classes since module 3.

The maxlen parameter

The gem for our purposes: a deque created with deque(maxlen=k) never exceeds k elements. If it is full and you append, it automatically discards the element at the opposite end (the front); with appendleft, it discards the one at the back. All in O(1):

from collections import deque

latest = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    latest.append(x)
    print(list(latest))
# [1]
# [1, 2]
# [1, 2, 3]
# [2, 3, 4]   ← the 1 discarded itself, no pop(0), no O(n)
# [3, 4, 5]

Compare with the previous lesson on circular queues: maxlen gives you the "discard the oldest" policy of EventLog, but without writing the class. Which to use? deque(maxlen=k) in everyday Python; the handcrafted CircularQueue when you need total control (or when you program in a language without a built-in deque) — and, above all, to understand what the magic does inside.

When NOT to use a deque

No structure is free on every operation; the deque pays for its O(1) at the ends with an expensive interior:

Operation list deque
x[i] at the ends O(1) O(1)
x[i] in the middle O(1) O(n) — it must hop block to block
Slices x[a:b] O(k) Not directly supported
insert/del in the middle O(n) O(n) (and against the ADT's spirit)
sort() O(n log n) Does not exist (must go through list)
append / pop at the back amortized O(1) O(1)
insert(0) / pop(0) O(n) O(1) (appendleft/popleft)

Practical rule: if your access pattern is "at the ends", deque; if it is "by index at any position" or you need sorting and slicing, list. A deque used as a random-access array (loops with d[i] over the middle) hides an O(n²) as treacherous as the looped pop(0) we denounced in module 1 — the symmetric trap.

The promise kept: BoundedHistory with maxlen

Recall the module 3 problem: keep the user's last k actions for undo, discarding the oldest when the limit is exceeded. Our list version pushed with append (fine) but discarded with pop(0) (O(n), "tolerable" for small k). The deque rewrite is almost anticlimactic in its brevity:

from collections import deque

class BoundedHistory:
    """The user's last k actions. Deque version: everything O(1).

    Same contract as the module 3 version; only the engine changes.
    """

    def __init__(self, limit):
        self._actions = deque(maxlen=limit)

    def record(self, action):
        self._actions.append(action)      # if full, maxlen discards
                                          # the oldest at the front: O(1)

    def undo(self):
        if self.is_empty():
            raise IndexError("no actions to undo")
        return self._actions.pop()        # LIFO at the back: O(1)

    def is_empty(self):
        return len(self._actions) == 0

    def size(self):
        return len(self._actions)

Look at the anatomy: record/undo work at the back (stack behavior, as "undo" demands), while maxlen discards at the front (queue behavior). Two active ends at once: that is why neither the plain stack nor the plain queue was enough, and why the deque is the structure for bounded histories. The public contract has not changed since module 3 — client code intact, cost improved: the perfect ADT victory.

Conceptual implementation on top of DoublyLinkedList

And if we had to implement it ourselves? The surprise is that we almost already did. The DoublyLinkedList from module 2 keeps head, tail, and DoubleNode nodes with prev and next; that is why it can insert and remove at both ends in O(1) (to remove at the tail, the prev link hands us the second-to-last node without traversing — exactly what the singly linked list lacked in 04-02). A deque is, conceptually, a DoublyLinkedList with the contract restricted to the ends:

class Deque:
    """Teaching deque: wraps the DoublyLinkedList from module 2
    and exposes ONLY the end operations."""

    def __init__(self):
        self._items = DoublyLinkedList()

    def enqueue_front(self, x):
        self._items.insert_front(x)        # O(1): rewires the head

    def enqueue_back(self, x):
        self._items.insert_back(x)         # O(1): rewires the tail

    def dequeue_front(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty deque")
        return self._items.remove_front()  # O(1)

    def dequeue_back(self):
        if self.is_empty():
            raise IndexError("dequeue from an empty deque")
        return self._items.remove_back()   # O(1) thanks to 'prev'

    def front(self):
        if self.is_empty():
            raise IndexError("front of an empty deque")
        return self._items.head.data

    def back(self):
        if self.is_empty():
            raise IndexError("back of an empty deque")
        return self._items.tail.data

    def is_empty(self):
        return self._items.size == 0

    def size(self):
        return self._items.size

There are no new algorithms: only a contract wall around a structure that already knew how to do it all. It is the same move as Queue over LinkedList (04-02) and Stack over list (module 3). The difference between this class and collections.deque is engineering, not concept: the 64-element blocks save memory and speed up the constants, but the Big O is identical.

TaskFlow: sliding window of completed tasks

Let's give the deque its TaskFlow debut with a first-class professional pattern: the sliding window. The team wants the dashboard to show the moving average of tasks completed per day over the last 7 days: each day the new figure enters and the one from 8 days ago "falls off". That is exactly deque(maxlen=7) plus a maintained sum:

from collections import deque

class ProductivityWindow:
    """Moving average of tasks completed/day over the last k days."""

    def __init__(self, days=7):
        self._window = deque(maxlen=days)
        self._sum = 0                         # maintained sum: average in O(1)

    def close_day(self, completed):
        if len(self._window) == self._window.maxlen:
            self._sum -= self._window[0]      # the day about to fall off (front: O(1))
        self._window.append(completed)        # the new day enters (maxlen discards)
        self._sum += completed

    def moving_average(self):
        if not self._window:
            return 0.0
        return self._sum / len(self._window)


# --- Usage: two weeks of the team's work ---
dashboard = ProductivityWindow(days=7)
for day, completed in enumerate([3, 5, 2, 4, 6, 1, 0, 7, 8, 6, 5, 9, 4, 3], 1):
    dashboard.close_day(completed)
    print(f"day {day:2}: completed={completed}  7-day average={dashboard.moving_average():.2f}")

The fine details, which are what make this O(1) per day:

  • The maintained sum: recomputing sum(self._window) on every query would be O(k). Instead, when the window slides we subtract the value leaving and add the one entering: the average stays available in O(1). This "update, don't recompute" pattern is a close relative of the MinStack from module 3, which maintained the minimum instead of searching for it.
  • Reading self._window[0] before the append: once maxlen is reached, append discards the front silently; if we had not subtracted it beforehand, the sum would be corrupted. The [0] access is an end → O(1), within the deque's rules.
  • During the first days (window not yet full) the average is computed over the days available: len(self._window) handles that by itself.

This same sliding-window skeleton solves server load averages, sensors, stock quotes... and a tricky variant (the window maximum) awaits you in the exercises of 04-06.

Classic bonus: palindromes

The canonical deque exercise: is a phrase a palindrome (does it read the same forwards and backwards)? With a deque, the idea is physical: compare the two ends and keep closing the pincers:

from collections import deque

def is_palindrome(text):
    letters = deque(c.lower() for c in text if c.isalnum())  # strips spaces/punctuation
    while len(letters) > 1:
        if letters.popleft() != letters.pop():   # front vs back: both O(1)
            return False
    return True                                  # 0 or 1 letters left: symmetric

print(is_palindrome("Never odd or even"))                 # True
print(is_palindrome("TaskFlow"))                          # False

Each turn consumes one letter from each end: n/2 comparisons, all O(1) → O(n) total. Doing it with a list and pop(0) would be O(n²); the deque is the difference between the algorithm and its caricature.

Common Mistakes and Tips

  • Indexing the interior of a deque in a loop: for i in range(len(d)): use(d[i]) is O(n²) because each central d[i] is O(n). Iterate with for x in d (O(n) total) or convert to list if you truly need indices.
  • Forgetting that maxlen discards silently: there is no exception or warning when an append evicts the oldest. If your logic depends on the element falling off (like the sum in ProductivityWindow), capture it before the append.
  • extendleft reverses: d.extendleft([1, 2, 3]) leaves 3, 2, 1, ... at the front. If you want to preserve the order, d.extendleft(reversed(sequence)).
  • Using a deque when you need sorting or slicing: neither sort() nor d[2:5] exists. If your algorithm asks for them often, the right structure was a list (or keeping order with sorted insertion, module 2).
  • Tip: when torn between list and deque, first write down the operations your code will perform (not the ones it "might"), and mark them in this lesson's cost table. The right structure usually singles itself out — it is the method we have been applying since the cost table of module 1.

Exercises

Exercise 1: trace of the four doors

Starting from an empty deque, trace the contents (front to back) after each operation: enqueue_back(2), enqueue_front(1), enqueue_back(3), dequeue_front(), enqueue_front(0), dequeue_back(), dequeue_back(). Also state what each dequeue_* returns. Which classic structure would you have obtained if every operation had been enqueue_back/dequeue_front?

Exercise 2: last k errors, with non-destructive reading

With deque(maxlen=k), write the RecentErrors class for TaskFlow: log(message) stores an error (discarding the oldest if k is exceeded) and listing() returns a list with the errors from most recent to oldest, without modifying the deque. Every log must be O(1).

Exercise 3: moving average robust to days without data

Extend ProductivityWindow with a close_day_no_data() method for holidays: the window must slide (the day counts, and evicts the oldest if applicable) but the day contributes no tasks and must not count in the denominator of the average. Hint: enqueue (value, counts_in_average) tuples or the value None, and maintain, besides _sum, a _valid_days counter.

Solutions

Solution 1:

Operation Deque (front → back) Returns
enqueue_back(2) 2 —
enqueue_front(1) 1, 2 —
enqueue_back(3) 1, 2, 3 —
dequeue_front() 2, 3 1
enqueue_front(0) 0, 2, 3 —
dequeue_back() 0, 2 3
dequeue_back() 0 2

With only enqueue_back + dequeue_front we would have used the deque as a FIFO queue (the operation pair from the generalization table).

Solution 2:

from collections import deque

class RecentErrors:
    def __init__(self, k=10):
        self._errors = deque(maxlen=k)

    def log(self, message):
        self._errors.append(message)           # O(1); maxlen discards the old

    def listing(self):
        return list(reversed(self._errors))    # a copy, most recent first

reversed(deque) iterates back to front in O(n) without touching the deque, and list(...) materializes the copy: the client can do whatever it wants with it without corrupting the history. Logging remains O(1) because the O(n) cost is only paid on query.

Solution 3:

class ProductivityWindow(ProductivityWindow):   # extending the class
    def __init__(self, days=7):
        super().__init__(days)
        self._valid_days = 0

    def _slide(self, incoming):
        if len(self._window) == self._window.maxlen:
            outgoing = self._window[0]
            if outgoing is not None:          # only subtract if it counted
                self._sum -= outgoing
                self._valid_days -= 1
        self._window.append(incoming)

    def close_day(self, completed):
        self._slide(completed)
        self._sum += completed
        self._valid_days += 1

    def close_day_no_data(self):
        self._slide(None)                     # takes up a slot, adds no data

    def moving_average(self):
        if self._valid_days == 0:
            return 0.0
        return self._sum / self._valid_days

The idea: None is a "gap with a right to a slot": it slides the window (and may evict old days) but neither adds nor counts. When it leaves the window, a None subtracts nothing either. Common mistake here: using 0 instead of None — the sum would come out right, but the denominator would count the holiday and unfairly sink the average!

Conclusion

The deque completes our family of queues: four end operations, all O(1), of which stack and queue are special cases. We have squeezed collections.deque — append/appendleft/pop/popleft, rotate, and the decisive maxlen that discards the old for free — learned its real limit (the interior is O(n): it is not a random-access array), kept the module 3 promise by rewriting BoundedHistory in four O(1) lines, and confirmed that the conceptual implementation was the DoublyLinkedList from module 2 with a restricted contract. As a bonus, TaskFlow debuts a productivity dashboard with a sliding-window moving average at O(1) per day. With this, the module's theory is complete: FIFO queue, circular queue, priority queue, and deque. The next lesson brings no new concepts: it brings six progressive exercises where these four structures — and the stacks from module 3 — work together on TaskFlow. It is time to consolidate; see you in the gym.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved