Deque Visualizer

How it works

1. Store the elements in a circular array of capacity slots with front (index of the first element) and size. The last element lives at (front + size - 1) % capacity.
2. push_front(x): step front back with front = (front - 1 + capacity) % capacity, write A[front] = x and increase size.
3. push_back(x): write to the first free slot after the last element, A[(front + size) % capacity] = x, and increase size.
4. pop_front(): read A[front], move front = (front + 1) % capacity and decrease size.
5. pop_back(): read A[(front + size - 1) % capacity] and decrease size; front does not move.

Worked example: pushing past the start of the array

Capacity 7, holding 8, 3 and 5 at indices 0–2 (front = 0, size = 3):

• push_front(1): front = (0 − 1 + 7) % 7 = 6 — it wraps to the last slot. A[6] = 1. Deque: [1, 8, 3, 5].
• push_front(2): front = 5 and A[5] = 2. Deque: [2, 1, 8, 3, 5].
• push_back(9): writes A[(5 + 5) % 7] = A[3] = 9. Deque: [2, 1, 8, 3, 5, 9].
• pop_back(): reads A[(5 + 6 - 1) % 7] = A[3] and returns 9; size 5.
• pop_front(): returns 2 from index 5; front becomes 6.

Nothing ever shifts. Each operation moves one index and touches one slot, so all four are O(1).

One structure, three behaviours

• As a stack: push_back with pop_back (or the two front operations) — last in, first out.
• As a queue: push_back with pop_front — first in, first out.
• As both at once: problems such as the sliding-window maximum add at the back and remove from both ends.

Restricted forms appear in textbooks too: an input-restricted deque allows insertion at only one end, and an output-restricted deque allows deletion at only one end.

How real deques are implemented

• Circular array — this page, Java's ArrayDeque, Rust's VecDeque: compact and cache-friendly. When full it moves the elements, in order, into a larger array, so pushes are amortized O(1).
• Blocks of fixed-size arrays — C++'s std::deque and Python's collections.deque: pushing at either end never moves existing elements. C++ also gives O(1) indexing, while indexing a Python deque is O(n) towards the middle.
• Doubly linked list: O(1) at both ends with no resizing, but one node allocation per element.

Classic deque problem: sliding window maximum

To report the maximum of every window of k consecutive values in O(n), keep a deque of indices whose values decrease from front to back. For each new index:

• Pop from the back while the value there is smaller than the incoming value — it can never be a window maximum again.
• Push the new index at the back.
• Pop from the front if that index has slid out of the window.
• The front now holds the index of the current window's maximum.

For [1, 3, −1, −3, 5, 3, 6, 7] with k = 3 the maxima are [3, 3, 5, 5, 6, 7]. Each index enters and leaves the deque at most once — the same amortized argument as the monotonic stack behind the next greater element. Deques also drive 0-1 BFS (0-weight edges go to the front, 1-weight edges to the back) and work-stealing thread schedulers.

Common mistakes

• Writing (front - 1) % capacity in C, C++ or Java: when front is 0 the result is −1, not capacity - 1. Add capacity before taking the modulo.
• Moving front on pop_back — only size changes.
• Forgetting that pushing several values at the front reverses them: push_front 1, then 2, gives [2, 1, …].
• Indexing into the middle of Python's collections.deque inside a loop — each access is O(n); use a list when you need random access.
• Storing null in Java's ArrayDeque, which throws a NullPointerException.

Time and space complexity

Deque in Python

class Deque:
    """Double-ended queue on a circular array: O(1) at both ends."""

    def __init__(self, capacity):
        self.A = [None] * capacity
        self.capacity = capacity
        self.front = 0   # first element
        self.size = 0    # last element: (front + size - 1) % capacity

    def push_front(self, x):
        if self.size == self.capacity:
            raise IndexError("Deque full")
        self.front = (self.front - 1 + self.capacity) % self.capacity  # step back
        self.A[self.front] = x
        self.size = self.size + 1

    def push_back(self, x):
        if self.size == self.capacity:
            raise IndexError("Deque full")
        rear = (self.front + self.size) % self.capacity  # first free slot after the last
        self.A[rear] = x
        self.size = self.size + 1

    def pop_front(self):
        if self.size == 0:
            raise IndexError("Deque empty")
        x = self.A[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size = self.size - 1
        return x

    def pop_back(self):
        if self.size == 0:
            raise IndexError("Deque empty")
        rear = (self.front + self.size - 1) % self.capacity
        x = self.A[rear]
        self.size = self.size - 1  # front stays where it is
        return x

    def peek_front(self):
        if self.size == 0:
            raise IndexError("Deque empty")
        return self.A[self.front]

    def peek_back(self):
        if self.size == 0:
            raise IndexError("Deque empty")
        return self.A[(self.front + self.size - 1) % self.capacity]

    def clear(self):
        self.front = 0
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity


# d = Deque(7); d.push_back(8); d.push_front(1); d.pop_back()  -> 8

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Circular Queue VisualizerCircular queue visualizer: watch front and rear wrap around a ring buffer with (i + 1) % capacity, and learn how to tell a full queue from an empty one.
• Queue VisualizerInteractive queue visualizer: watch enqueue and dequeue move the front and rear of an array queue, and see the wasted-space problem that circular queues fix.
• Stack VisualizerInteractive stack visualizer: watch push, pop and peek move the top pointer of an array stack, see overflow and underflow happen, and learn why each is O(1).
• Next Greater Element VisualizerFind the next greater element of every array value with a monotonic stack in O(n). Watch each index wait on the stack until a larger value resolves it.
• Linked List VisualizerInteractive linked list visualizer: watch every pointer change as you insert, delete, search and reverse singly, doubly and circular lists, with code and costs.