Deque

Double-Ended Queue

Pronunciation: DEK

Updated September 30, 20263 min read

In short

A deque is a double-ended queue that lets you add and remove items at both the front and the back in constant time, so it can act as both a stack and a queue.

What is a deque?

A deque, short for double-ended queue and pronounced like deck, is a sequence that supports adding and removing items at both ends. Its four core operations are push and pop at the front and push and pop at the back, and each takes O(1) time. Because it can do everything a stack and a queue can, a deque is often the most flexible choice when you need fast access to both ends.

Deques are usually built in one of two ways. A doubly linked list, or a linked chain of fixed-size blocks as in Python's collections.deque, lets either end grow without moving anything. A circular buffer, an array whose start and end wrap around, keeps items together in memory and grows by copying into a larger array when it fills up, as Java's ArrayDeque and Rust's VecDeque do. Reaching items in the middle is slower than at the ends in linked designs, O(n), although circular buffers can still index in O(1).

Picture a deck of cards on a table where you may take or add cards at the top or the bottom, but never in the middle. Deques are used for sliding window algorithms, which keep the last k items or track a running maximum, for undo histories with a size limit, and for work-stealing schedulers, where each thread takes tasks from one end of its own deque while idle threads steal from the other end. In Python, collections.deque is also the recommended way to build an ordinary queue.

A deque is easy to confuse with the word dequeue, which is the name of the operation that removes an item from a queue. It is also different from a plain dynamic array, such as a Python list or a JavaScript array: those are fast at the back but slow at the front, because inserting or removing at index 0 shifts every other item, which is O(n). Compared with a queue, which only adds at the back and removes at the front, a deque simply removes that restriction.

Key takeaways

A deque supports adding and removing at both the front and the back in O(1) time.
It can act as a stack, a queue, or both at once.
It is typically built on a doubly linked list or a circular buffer.
In Python, collections.deque with appendleft() and popleft() avoids the O(n) cost of list.pop(0).
Deque is the data structure; dequeue is the operation of removing an item from a queue.

Example

Using both ends of a deque in Pythonpython

from collections import deque

d = deque([2, 3])
d.appendleft(1)     # add at the front: O(1)
d.append(4)         # add at the back: O(1)
print(d)            # deque([1, 2, 3, 4])
print(d.popleft())  # remove from the front: 1
print(d.pop())      # remove from the back: 4

# With maxlen, the deque keeps only the most recent items
recent = deque(maxlen=3)
for page in ["home", "docs", "pricing", "blog"]:
    recent.append(page)  # the oldest item falls off the other end
print(list(recent))  # ['docs', 'pricing', 'blog']

Readers ask

What is the difference between a deque and a queue?

A queue adds items at the back and removes them only from the front. A deque allows both operations at both ends, so it can behave as a queue, a stack, or a mix of the two.

How do you pronounce deque?

It is usually pronounced like deck. That avoids confusion with dequeue, pronounced dee-cue, which is the operation of removing an item from a queue.

When should I use a deque instead of a list?

Use a deque when you add or remove items at the front, as in a queue or a sliding window. A list or array is better when you mostly work at the end and need fast access by index into the middle.