Deques

Sometimes you need to add and remove from both ends — a double-ended queue is the best of both worlds.

The problem

You are building the "undo/redo" bar for an editor, and next to it a live feed of the last five actions the user took. New actions arrive at the front of that feed. When the feed grows past five, the oldest one drops off the back. So you are constantly adding to one end and removing from the other — and sometimes doing the reverse when the user hits undo.

A stack only lets you touch one end. A queue lets you push at the back and pop at the front, but never the other way. Your feed needs both ends open at once, and it needs every one of those pokes to be fast. Reach for the wrong structure and each update quietly slides the whole list over in memory.

A first attempt

The obvious move is a plain array (a Python list, a JS Array). Appending to the back is cheap. But your feed adds to the front:

feed = []
feed.insert(0, action)   # add to front
feed.pop()               # remove from back

insert(0, x) looks innocent. Under the hood it shifts every existing element one slot to the right to make room. With n items that is O(n) work — every single time. Do it for n actions and you have spent O(n²) just maintaining a five-item feed. The list is fighting you, and it only gets worse as the app runs longer.

The insight

The pain comes from one place: an array stores elements in one contiguous block, so making room at the front means moving everything. What if the two ends didn't have to know about each other?

A deque ("deck", short for double-ended queue) is built exactly for this. It keeps the front and the back as independent access points, so pushing or popping at either end is O(1). Internally it is usually a doubly linked list or a ring of fixed-size blocks — never a single array you have to shuffle. Once you stop forcing a one-ended tool to work on both ends, the cost collapses to constant time.

How it works

A deque exposes four core operations. Picture a row of blocks with a pointer at each end.

        push_front            push_back
           │                      │
           ▼                      ▼
        ┌─────┬─────┬─────┬─────┬─────┐
 front ◀│  A  │  B  │  C  │  D  │  E  │▶ back
        └─────┴─────┴─────┴─────┴─────┘
           ▲                      ▲
        pop_front             pop_back

Start empty

Both the front and back pointers refer to nothing. Size is 0.

push_front / push_back

To add at an end, you attach a new node just outside the matching pointer and move that pointer onto it. The other end never moves, so it stays valid. Both are O(1).

pop_front / pop_back

To remove from an end, you read the pointer's node, step the pointer inward to its neighbour, and detach the old node. Again the far end is untouched, so this is O(1).

Model the feed

Your live feed becomes: push_front(action) on every new event, and when len(feed) > 5, call pop_back() to drop the stale one. Both ends fast, no shifting.

The code

Most languages ship a deque so you rarely build one by hand. Here is the standard type in each, driving the five-item feed.

from collections import deque

feed = deque(maxlen=5)  # auto-drops from the far end when full

def record(action: str) -> None:
    feed.appendleft(action)  # add to front, O(1)

record("open")
record("type")
record("bold")
print(list(feed))       # ['bold', 'type', 'open']
print(feed.popleft())   # 'bold'  (most recent)
print(feed.pop())       # 'open'  (oldest)

// A minimal deque backed by a doubly linked list.
class Deque<T> {
  private head?: { value: T; prev?: any; next?: any };
  private tail?: typeof this.head;
  size = 0;

  pushFront(value: T): void {
    const node = { value, next: this.head };
    if (this.head) this.head.prev = node;
    this.head = node;
    this.tail ??= node;
    this.size++;
  }

  popBack(): T | undefined {
    if (!this.tail) return undefined;
    const value = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) this.tail.next = undefined;
    else this.head = undefined;
    this.size--;
    return value;
  }
}

const feed = new Deque<string>();
feed.pushFront("open");
feed.pushFront("type");
if (feed.size > 1) feed.popBack(); // drop oldest

import java.util.ArrayDeque;
import java.util.Deque;

public class Feed {
    public static void main(String[] args) {
        Deque<String> feed = new ArrayDeque<>();
        feed.addFirst("open");   // push front, O(1)
        feed.addFirst("type");
        feed.addFirst("bold");

        if (feed.size() > 2) {
            feed.removeLast();   // drop oldest, O(1)
        }
        System.out.println(feed.peekFirst()); // bold
        System.out.println(feed.peekLast());  // type
    }
}

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    char *value;
    struct Node *prev, *next;
} Node;

typedef struct {
    Node *head, *tail;
    int size;
} Deque;

void push_front(Deque *d, char *value) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->prev = NULL;
    n->next = d->head;
    if (d->head) d->head->prev = n;
    d->head = n;
    if (!d->tail) d->tail = n;
    d->size++;
}

char *pop_back(Deque *d) {
    if (!d->tail) return NULL;
    Node *t = d->tail;
    char *value = t->value;
    d->tail = t->prev;
    if (d->tail) d->tail->next = NULL;
    else d->head = NULL;
    free(t);
    d->size--;
    return value;
}

int main(void) {
    Deque d = {NULL, NULL, 0};
    push_front(&d, "open");
    push_front(&d, "type");
    if (d.size > 1) printf("%s\n", pop_back(&d)); // open
    return 0;
}

#include <deque>
#include <iostream>
#include <string>

int main() {
    std::deque<std::string> feed;
    feed.push_front("open");   // O(1)
    feed.push_front("type");
    feed.push_front("bold");

    if (feed.size() > 2) {
        feed.pop_back();       // drop oldest, O(1)
    }
    std::cout << feed.front() << '\n'; // bold
    std::cout << feed.back()  << '\n'; // type
    return 0;
}

Complexity

Operation	Time	Space
push_front / push_back	O(1)	O(1)
pop_front / pop_back	O(1)	O(1)
peek_front / peek_back	O(1)	O(1)
random access by index	O(n)	O(1)
Whole structure holding n items	—	O(n)

When to use it

Reach for a deque when both ends are hot

A deque is a superset of both stack and queue — it can do everything they do. Use it for sliding windows, undo/redo history, work-stealing schedulers, and palindrome checks. The catch: indexing into the middle is O(n), so if you need fast deque[i] in the middle, a plain array is the better tool.

Practice

Recap

A deque is a double-ended queue: O(1) push and pop at both the front and the back.
It beats a plain array whenever you mutate the front, where insert(0, x) is a hidden O(n).
It generalizes stacks and queues; the trade-off is O(n) access to the middle.

Deques

The problem

A first attempt

The insight

How it works

Start empty

push_front / push_back

pop_front / pop_back

Model the feed

The code

Complexity

When to use it

Practice

Recap

Sliding Window Maximum

Queues

Stacks

On this page

Deques

How would you build a queue and a stack using only a deque?

Why does Python's list.insert(0, x) turn a loop into O(n²)?

Is a deque a good fit for checking whether a word is a palindrome?

Sliding Window Maximum

Queues

Stacks

On this page