Stacks & Queues4 min read

Deque

A line you can join or leave from either end — front or back, your choice

push_front: \(O(1)\)push_back: \(O(1)\)pop_front: \(O(1)\)pop_back: \(O(1)\)search: \(O(n)\)space: \(O(n)\)

A deque (pronounced "deck") stands for Double-Ended Queue. It's like a regular queue, but with a superpower: you can add or remove items from both ends — the front and the back.

Imagine a train car with doors on both ends. Passengers can board from the front or the back, and they can exit from either end too. That's a deque.

Four operations — all instant

push_front — add to the front
push_back — add to the back
pop_front — remove from the front
pop_back — remove from the back

All four are \(O(1)\). Because a deque tracks both ends with pointers, there's no shifting needed.

◈ Explore the deque

← → arrow keys to step · click elements to interact

Stack and Queue in one

A deque is a generalization of both a stack and a queue:

Use only push_back + pop_back → behaves like a stack (LIFO)
Use only push_back + pop_front → behaves like a queue (FIFO)

This flexibility makes deques incredibly useful.

Sliding Window Maximum

One of the most famous uses of a deque is the sliding window maximum problem. As a window slides across an array, you need the maximum in the current window at all times. A deque tracks candidates efficiently — adding new elements at the back and removing stale ones from the front — keeping the solution to \(O(n)\) instead of \(O(n×k)\).

Palindrome checking

Deques make palindrome checking elegant. Push all characters in. Then compare pop_front with pop_back, one pair at a time. If they always match, it's a palindrome!

Note: A deque is the Swiss Army knife of linear data structures — it combines stack and queue behavior in a single, efficient package.

Complexity

Push FrontAdd to front with pointer update

Instant\(O(1)\)

Push BackAdd to back with pointer update

Instant\(O(1)\)

Pop FrontRemove from front

Instant\(O(1)\)

Pop BackRemove from back

Instant\(O(1)\)

SearchNo direct access by value

Slow\(O(n)\)

SpaceOne slot per item

Grows with n\(O(n)\)

Deque Operations

from collections import deque

dq = deque()
dq.append(10)        # push back
dq.appendleft(20)    # push front
dq.append(30)        # push back
print(list(dq))      # [20, 10, 30]
print(dq.popleft())  # pop front: 20
print(dq.pop())      # pop back:  30
print(list(dq))      # [10]

Output

[20, 10, 30]
20
30
[10]

Sliding Window Maximum

from collections import deque

def sliding_max(arr, k):
    dq, res = deque(), []
    for i, x in enumerate(arr):
        while dq and arr[dq[-1]] < x:
            dq.pop()            # remove smaller from back
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()        # remove out-of-window from front
        if i >= k - 1:
            res.append(arr[dq[0]])
    return res

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

Output

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

Challenge

Quick check

What makes a deque different from a regular queue?

Stack

A pile of plates — the last one you put on is the first one you take off

→

Queue

A line of people waiting — the first one in is the first one served

→

Sliding Window

A picture frame scanning over an array to solve sub-array problems in \(O(n)\) time

→