A deque (pronounced "deck", short for double-ended queue) is a sequence that supports fast insertion and removal from both ends — the front and the back. It's a strict generalization of both a stack and a queue: restrict a deque to only push/pop one end and it behaves like a stack; restrict it to enqueue at one end and dequeue from the other and it behaves like a queue.

Most languages provide a deque as a standard, ready-to-use data structure (Python's collections.deque, for example) implemented internally as a doubly linked list of fixed-size blocks, which is why all four core operations run in O(1) time.

Core Operations

A deque supports four main operations, all O(1): append (add to the back), appendleft (add to the front), pop (remove from the back), and popleft (remove from the front).

from collections import deque

dq = deque()

dq.append(10)       # back:    [10]
dq.append(20)       # back:    [10, 20]
dq.appendleft(5)     # front:   [5, 10, 20]

print(dq)
print("Removed from front:", dq.popleft())
print("Removed from back:", dq.pop())
print(dq)

Output:

deque([5, 10, 20])
Removed from front: 5
Removed from back: 20
deque([10])

Why Not Just Use a Plain Array?

A plain array (or Python list) is fast at adding/removing from the back — O(1) — but adding or removing from the front is O(n), because every other element has to shift over by one position. A deque is specifically built so both ends are equally fast, which a plain array fundamentally can't offer without that internal block-based structure.

A Real Use Case: Sliding Window Problems

Deques show up constantly in "sliding window" problems — for example, finding the maximum value in every contiguous window of size k across an array. The trick is to keep a deque of indices, always removing indices from the back whose values are smaller than the one just added (they can never be the window's maximum once a bigger number has joined), and removing from the front once an index falls outside the current window:

def max_sliding_window(nums, k):
    dq = deque()  # stores indices, values stay decreasing
    result = []

    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)

        if dq[0] <= i - k:
            dq.popleft()

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))

Output:

[3, 3, 5, 5, 6, 7]

This runs in O(n) overall — each index is added and removed from the deque at most once — versus the naive O(n·k) approach of rescanning every window. A good next read is arrays vs linked lists, which covers why the front-removal cost difference between the two matters so much here.