Deque (Double-Ended Queue)

You already know a normal queue. You add at the back. You remove from the front. That is it. One door in, one door out. But what if you need to add at the front too? Or remove from the back? A plain queue cannot do that. This is where a deque helps. It lets you add and remove from both ends.

📚 What Is a Deque?

A deque is a double-ended queue. That means you can add and remove from both ends, the front and the back.

So you get four moves instead of two:

• pushFront — add an item at the front.
• pushBack — add an item at the back.
• popFront — remove an item from the front.
• popBack — remove an item from the back.

The name is said like “deck”, the same as a deck of cards. Keep that in your head. It helps.

Think of a normal queue as a one-way street. Cars enter from one end. They leave from the other end. A deque is a two-way street. A car can enter or leave from either end. Both ends are fully open.

🎯 Why Do We Need It?

Here is the real pain. Say you are tracking the recent items a user touched. The newest one must sit at the front. With a plain queue you can only add at the back. So you are stuck. A deque fixes this. The front is open too.

Let me show you a picture of the two ends:

Both sides can grow. Both sides can shrink. That is the whole idea.

A few common places where a deque is the right tool:

• Sliding window problems — you keep a window of items moving across an array. Old items leave from one end. New items enter from the other end. A deque does both cheaply.
• Undo history — you keep the most recent actions. New actions go in at one end. When the history gets too long, you drop the oldest from the other end.
• A web browser’s back and forward — pages stack on both sides as you move around.

⚙️ How the Four Operations Work

Picture the deque as a row of boxes. Let me walk through each move with a tiny example. We start empty.

• pushBack(10) → row is 10
• pushBack(20) → row is 10 20
• pushFront(5) → row is 5 10 20
• popFront() → removes 5, row is 10 20
• popBack() → removes 20, row is 10

See how the front and the back both stay open the whole time? You never have to shift anything around in your head. You just pick the end you want.

💻 Deque in Five Languages

Good news. You almost never build a deque by hand. Every language ships one ready to use. Here is the same demo in each. It does the four moves and prints the result.

A quick note on C first. The C standard library has no built-in deque. So in C you build your own. You usually use an array (with a front and a rear index) or a doubly linked list. The code below shows a small array-based version so you can see the idea.

#include <stdio.h>

#define MAX 100

// A simple array-based deque using two indices.
typedef struct {
    int data[MAX];
    int front;
    int back; // points one past the last item
} Deque;

void initDeque(Deque *d) {
    // Start in the middle so both ends have room to grow.
    d->front = MAX / 2;
    d->back = MAX / 2;
}

void pushBack(Deque *d, int value) {
    d->data[d->back] = value;
    d->back++;
}

void pushFront(Deque *d, int value) {
    d->front--;
    d->data[d->front] = value;
}

void popFront(Deque *d) {
    d->front++;
}

void popBack(Deque *d) {
    d->back--;
}

void printDeque(Deque *d) {
    printf("Deque: ");
    for (int i = d->front; i < d->back; i++) {
        printf("%d ", d->data[i]);
    }
    printf("\n");
}

int main(void) {
    Deque d;
    initDeque(&d);

    pushBack(&d, 10);
    pushBack(&d, 20);
    pushFront(&d, 5);
    printDeque(&d);   // 5 10 20

    popFront(&d);
    popBack(&d);
    printDeque(&d);   // 10
    return 0;
}

Deque: 5 10 20
Deque: 10

#include <iostream>
#include <deque>
using namespace std;

void printDeque(const deque<int> &d) {
    cout << "Deque: ";
    for (int x : d) cout << x << " ";
    cout << "\n";
}

int main() {
    deque<int> d;

    d.push_back(10);   // back: 10
    d.push_back(20);   // back: 10 20
    d.push_front(5);   // front: 5 10 20
    printDeque(d);

    d.pop_front();     // removes 5
    d.pop_back();      // removes 20
    printDeque(d);
    return 0;
}

Deque: 5 10 20
Deque: 10

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

public class DequeDemo {
    public static void main(String[] args) {
        Deque<Integer> d = new ArrayDeque<>();

        d.addLast(10);    // back: 10
        d.addLast(20);    // back: 10 20
        d.addFirst(5);    // front: 5 10 20
        System.out.println("Deque: " + d);

        d.pollFirst();    // removes 5
        d.pollLast();     // removes 20
        System.out.println("Deque: " + d);
    }
}

Deque: [5, 10, 20]
Deque: [10]

from collections import deque

d = deque()

d.append(10)       # back: 10
d.append(20)       # back: 10 20
d.appendleft(5)    # front: 5 10 20
print("Deque:", list(d))

d.popleft()        # removes 5
d.pop()            # removes 20
print("Deque:", list(d))

Deque: [5, 10, 20]
Deque: [10]

const d = [];

d.push(10);       // back: 10
d.push(20);       // back: 10 20
d.unshift(5);     // front: 5 10 20
console.log("Deque:", d);

d.shift();        // removes 5 from front
d.pop();          // removes 20 from back
console.log("Deque:", d);

Deque: [ 5, 10, 20 ]
Deque: [ 10 ]

⏱️ How Fast Is It?

This is the best part. A real deque does push and pop at O(1) on both ends. O(1) means the time stays the same no matter how many items are inside. You touch one end. You are done.

Here is the cost of each move:

⚠️ Common Mistakes

A few slips that trip up beginners. Watch for these.

• Popping an empty deque. Always check it is not empty first, or you get a crash or junk value.
• Mixing up the ends. addFirst vs addLast, popleft vs pop. Read the method name slowly. Match it to the end you actually want.
• Using a JS array and expecting O(1) at the front. shift and unshift are O(n). Know this before you build something big.
• Reaching for a deque when a plain queue is enough. If you only ever add at one end and remove from the other, a normal queue is simpler. Use a deque when you truly need both ends.

🧩 What You’ve Learned

✅ A deque is a double-ended queue. You can add and remove from both the front and the back.

✅ The four moves are pushFront, pushBack, popFront, and popBack.

✅ It shines in sliding window problems and undo history, anywhere you need both ends open.

✅ Every language ships one: std::deque, ArrayDeque, collections.deque, and a plain array in JS. In C you build your own.

✅ A real deque does push and pop in O(1) at both ends, but a JS array’s front moves are O(n).

🚀 What’s Next?

• Circular Queue
• Priority Queue