3.3 Deques: Both Ends and Sliding Windows

Prerequisites: Stack, Queue. This section first clarifies the four endpoint operations, then handles the boundaries of maxlen and extendleft, and finally uses a monotonic deque to reduce the sliding window maximum to Θ(n).

The Operation Contract at Both Ends

A double-ended queue (deque), commonly pronounced "deck," opens up at both ends. It supports four fundamental operations:

Direction	Insert	Remove
Left end / front	appendleft(x)	popleft()
Right end / back	append(x)	pop()

A stack exposes only one end with its LIFO (last-in, first-out) behavior; a queue enforces a fixed FIFO (first-in, first-out) pattern, with entries at the back and removals from the front; a deque offers all four endpoint operations to the caller. A deque can simulate both stack and queue behavior, but the fact that a data structure can implement a certain abstraction does not mean that these abstractions are synonymous.

Python deque's Cost Boundaries

The Python collections.deque documentation describes appending and popping from both ends as approximately O(1). It's well-suited for use cases like work queues, recent records, bidirectional scanning, and monotonic queues.

It is not a general replacement for random-access lists:

• d[0] and d[-1] access at the ends is O(1);
• Index access slows toward the middle, taking O(n) in the worst case;
• Operations involving lookup or internal positioning (such as insert, remove, and index) do not fall under the guarantees provided by endpoint operations.

If your primary operations involve reading or modifying elements at intermediate indices, list is typically a better fit. The appearance of list.pop(0) or list.insert(0, x) should signal a reevaluation of the container choice. Whether to switch to deque should be determined by considering queue size, operation frequency, and interface constraints.

Run All Four Endpoint Operations

The following complete program verifies all four endpoint operations, then runs a sliding-window algorithm:

from collections import deque
from operator import index as integer_index

def max_sliding_window(nums, k):
    k = integer_index(k)
    if not 1 <= k <= len(nums):
        raise ValueError("k must satisfy 1 <= k <= len(nums)")

    candidates = deque()
    maxima = []
    for index, value in enumerate(nums):
        while candidates and candidates[0] <= index - k:
            candidates.popleft()
        while candidates and nums[candidates[-1]] < value:
            candidates.pop()
        candidates.append(index)
        if index >= k - 1:
            maxima.append(nums[candidates[0]])
    return maxima

if __name__ == "__main__":
    jobs = deque()
    jobs.append("job B")
    jobs.append("job C")
    jobs.appendleft("job A")
    jobs.appendleft("urgent job")

    print(f"Deque state: {list(jobs)}")
    print(f"Removed left: {jobs.popleft()}")
    print(f"Removed right: {jobs.pop()}")

    values = [1, 3, -1, -3, 5, 3, 6, 7]
    print(f"Window maxima: {max_sliding_window(values, 3)}")

    assert list(jobs) == ["job A", "job B"]
    print("Double-ended queue check passed")

Deque state: ['urgent job', 'job A', 'job B', 'job C']
Removed left: urgent job
Removed right: job C
Window maxima: [3, 3, 5, 5, 6, 7]
Double-ended queue check passed

The first four writes produce:

Left end                               Right end
urgent job <- job A <- job B <- job C

popleft removes the urgent job, and pop removes job C. Jobs A and B remain. A deque does not decide which end represents the front; the algorithm's contract does.

Bounded deque: What happens when it's full

Creating deque(maxlen=n) limits the number of retained elements to n:

from collections import deque

recent = deque(["event 1", "event 2"], maxlen=3)
recent.append("event 3")
recent.append("event 4")

assert list(recent) == ["event 2", "event 3", "event 4"]
assert recent.maxlen == 3

When the queue is full and elements are added from the right append, Python discards the leftmost element; when elements are added from the left appendleft, it discards the element from the right. This suits "only retain the most recent N items" agreements but is unsuitable for task queues that cannot silently drop data.

There's another easy-to-miss difference: when performing insert(index, value) on a bounded deque that is full, if the insertion would exceed maxlen, it throws IndexError and does not automatically make space on the other end. maxlen=0 is valid: an append leaves the deque empty. A negative maxlen raises ValueError.

from collections import deque

right_append = deque([1, 2, 3], maxlen=3)
right_append.append(4)
assert list(right_append) == [2, 3, 4]

left_append = deque([1, 2, 3], maxlen=3)
left_append.appendleft(0)
assert list(left_append) == [0, 1, 2]

extendleft reverses the input order

extendleft is equivalent to repeatedly executing appendleft:

from collections import deque

letters = deque(["d"])
letters.extendleft(["a", "b", "c"])

assert list(letters) == ["c", "b", "a", "d"]

First, a is placed at the left end, then b moves to the left of a, and finally c ends up at the very left. As a result, the input order is reversed within the deque. To preserve order at the left end, use reversed(items) when items is reversible, such as a list. A one-shot iterator must first be buffered.

from collections import deque

def is_palindrome(text):
    chars = deque(char.lower() for char in text if char.isalnum())
    while len(chars) > 1:
        if chars.popleft() != chars.pop():
            return False
    return True

assert is_palindrome("Never odd or even")
assert not is_palindrome("river")

The palindrome function keeps isalnum() characters and applies lower() to each one. It returns True for empty or punctuation-only input. This demonstrates pairing at both ends, without fully handling Unicode normalization, case mappings across characters, or grapheme clusters. Scanning and constructing the deque take Θ(n) worst-case work and storage.

Maintain a Sliding-Window Maximum with a Deque

Given an array and width k, report the maximum each time the window moves one position right.

A brute-force approach scans all k elements for each window, resulting in a time complexity of Θ((n-k+1)k), commonly written as O(nk). Using a monotonic deque, we maintain indices that could still become the maximum in future windows, reducing the total cost to Θ(n).

Three Invariants

After processing index i (before the first full window, these describe the prefix seen so far):

1. The deque contains only indices within the current window [i-k+1, i];
2. The values corresponding to these indices decrease or stay the same from front to back;
3. The index at the front of the deque corresponds to the maximum value in the current window.

The example code first removes indices that have exited the window from the front, then removes any candidates at the back that are strictly smaller than the new value. Equal values stay in index order. When an older equal value leaves the window, the newer one can take its place.

Why Can Smaller Tail Elements Be Removed?

Suppose we have indices j < i and nums[j] < nums[i], and a new element i appears to the right with a larger value. In any future window that includes both, j can never be the maximum, because when i exits the window, j has already left. Thus, j can be permanently removed.

Manual Computation of the First Few Windows

The array is [1, 3, -1, -3, 5, 3, 6, 7], with k=3:

Index Read	Current Value	Candidate Indices (front → back)	Maximum in Current Window
0	1	[0]	Not yet full
1	3	[1]	Not yet full
2	-1	[1, 2]	3
3	-3	[1, 2, 3]	3
4	5	[4]	5
5	3	[4, 5]	5

Each index is added exactly once. It leaves at most once, either from the front on expiration or from the back when dominated. Total operations are therefore proportional to n. At most k candidates are retained, using O(k) auxiliary space; the n-k+1 returned maxima require separate Θ(n-k+1) output space.

Input Boundaries

The input nums must support constant-time indexing, and its values must have a consistent total order with constant-time comparisons. Values such as NaN fall outside that contract. k must be an integer satisfying 1 <= k <= len(nums). A noninteger raises TypeError; empty input, k=0, or k>n raises ValueError. Another interface could return an empty list for invalid windows, but its code and tests must agree.

Choose deque or list

Workload	Better starting point	Reason
Appending and removing from the right end	list or deque	Both support efficient endpoint operations
Frequent appending and removing from both ends	deque	All four endpoint operations are directly available
Heavy random access by index	list	deque's middle-index access is O(n)
Fixed retention of the most recent N items	deque(maxlen=N)	Built-in bounded eviction semantics
Frequent modifications at arbitrary intermediate positions	Re-examine the algorithm	deque does not guarantee constant-time operations in the middle

This table provides a starting point, not a substitute for measurement. Actual performance depends on element size, memory usage, concurrency contracts, and library version.

Deque Interfaces in Python, Java, and C++

Language	Type	Left add / left retrieve	Right add / right retrieve	Important boundaries
Python	collections.deque	appendleft / popleft	append / pop	Endpoints approximately O(1); middle indexing O(n); supports setting maxlen
Java 17	Deque<E> / ArrayDeque<E>	offerFirst / pollFirst	offerLast / pollLast	ArrayDeque prohibits null; not thread-safe; most operations provide amortized constant time
C++	std::deque<T>	push_front / pop_front	push_back / pop_back	Supports random access; single-element endpoint insertion and deletion take constant time; internal layout is managed by implementation

In Java, Deque provides two forms for each operation: one that throws an exception on failure, and another that returns a special value. When used as a stack, push/pop/peek corresponds to the top end; when used as a FIFO queue, offer/poll/peek adds elements to the tail and removes them from the front.

Python documents individual endpoint appends and pops as thread-safe, but if d: d.popleft() remains two operations, not an atomic protocol. C++ std::deque preserves existing element references on endpoint insertion but invalidates iterators. Similar method names do not imply the same layout, handle stability, or concurrency guarantees.

Reference contracts:

• Python collections.deque
• Java Deque
• Java ArrayDeque
• C++ deque modifiers

How to Diagnose Common Errors

Symptom	First Check
Reversed head and tail in the queue	Clearly label each direction's business meaning next to the interface
Bounded deque silently drops tasks	Does eviction under maxlen fit the task’s delivery requirements?
extendleft Result is reversed	Is a reversed(items) needed?
Maximum value in window uses stale elements	Does the new round first verify dq[0] <= i-k?
Incorrect answer after duplicate maximums leave	Does the deque store indices? What deletion strategy is used for equal values?
Performance degrades due to mid-deque indexing	Did you mistakenly assign random-access workloads to the deque?

Hands-on Maintaining Monotonic Candidates

1. Start with an empty deque and sequentially apply append(1), appendleft(2), pop(), and popleft(). What is the state after each step?
2. After appendleft(0) on deque([1, 2, 3], maxlen=3), what does the container hold, and what does the method itself return?
3. Draw the order of elements after each insertion for extendleft(["a", "b"]).
4. Manually compute the candidate indices and final answers for arrays [4, 2, 2, 5] and k=2.
5. Modify the sliding window algorithm to retain only the most recent indices for equal values. Should < be changed? If so, how? Will the result change?

Compare the Three Linear Containers

A deque’s core is efficient access at both ends; the algorithm gives those ends their roles. A stack pushes and pops at the same end, while FIFO uses opposite ends. A monotonic queue also preserves unexpired indices and non-increasing values. Silent maxlen eviction fits only workloads that allow old data to be discarded.

Stacks, queues, and deques can now be compared by interface and cost. The next chapter moves into Hash Tables, where a key narrows the candidate locations.