Deque

A double-ended queue with O(1) adds and removes at both the front and the back.

Worth knowing first

#How does it work?

A deque (double-ended queue) lets you add and remove elements at both the front and the back. Think of it as a stack and a queue in one.

Add only at the back and remove at the front and it is a queue; use only one end and it is a stack. That flexibility makes it a building block of many algorithms.

It is usually implemented with a circular buffer or a doubly linked list, so all four operations take O(1).

#Try it yourself

$ deque --interactive

A deque is a double-ended queue: you can add and remove at both the front and the back.

Elements: 3/8VisitingNewRemovingFound / read

#Basic operations

pushFront(x)
Adds x at the front.
pushBack(x)
Adds x at the back.
popFront()
Removes and returns the front element.
popBack()
Removes and returns the back element.
peekFront() / peekBack()
Reads an end element without removing it.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

class Deque:
    """Circular buffer: both ends wrap around, so nothing is ever shifted.

    (The standard library already has one: collections.deque.)
    """

    def __init__(self, capacity: int) -> None:
        self._items = [0] * capacity
        self._front = 0
        self._size = 0

    def push_front(self, value: int) -> None:
        if self._size == len(self._items):
            raise OverflowError("deque is full")
        self._front = (self._front - 1) % len(self._items)
        self._items[self._front] = value
        self._size += 1

    def push_back(self, value: int) -> None:
        if self._size == len(self._items):
            raise OverflowError("deque is full")
        self._items[(self._front + self._size) % len(self._items)] = value
        self._size += 1

    def pop_front(self) -> int:
        if self._size == 0:
            raise IndexError("deque is empty")
        value = self._items[self._front]
        self._front = (self._front + 1) % len(self._items)
        self._size -= 1
        return value

    def pop_back(self) -> int:
        if self._size == 0:
            raise IndexError("deque is empty")
        self._size -= 1
        return self._items[(self._front + self._size) % len(self._items)]

    def __len__(self) -> int:
        return self._size


d = Deque(8)
d.push_back(1)
d.push_back(2)
d.push_front(0)       # [0, 1, 2]
print(d.pop_back())   # 2
print(d.pop_front())  # 0
print(len(d))         # 1

#Complexity

OperationTime
pushFront / pushBackO(1)
popFront / popBackO(1)
Access an element in the middleO(1) array / O(n) list
MemoryO(n)

In a circular buffer the front index moves backwards and the back index forwards; no element is shifted. When the array fills up its capacity is doubled, so adding is amortized O(1).

#When to use it?

Sliding-window maximum, 0-1 BFS, palindrome checks, undo/redo history and work-stealing schedulers use a deque. Python's collections.deque, C++'s std::deque and Java's ArrayDeque are ready-made implementations.

#Practice

Log in to answer questions and save your progress.

Easy

1/3

At which ends can a deque add and remove elements?

  • 1Both the front and the back
  • 2Only the back
  • 3Only the front
  • 4Only the middle

Medium

1/1

Empty deque: pushBack(1), pushBack(2), pushFront(0), popBack(). Which value comes out?

  • 12
  • 20
  • 31
  • 4None

Hard

1/1

Why is a deque used for the sliding window maximum problem?

  • 1Expired items leave from the front and useless smaller ones from the back, both in O(1)
  • 2It sorts its elements automatically
  • 3Lookup is O(1)
  • 4It uses less memory