Skip to content

level 4 · Linear structures

Deque

A queue open at both ends — a stack and a queue in one structure.

8 min 60 XP

what is it

Start here

A deque — pronounced 'deck' — is a double-ended queue. You can add to the front or the back, and remove from the front or the back. Four operations, all instant.

That makes it a superset of everything you've learned so far. Use only pushBack and popBack, and you've built a stack. Use pushBack and popFront, and you've built a queue. A deque is what a stack and a queue both are underneath.

The reason it's fast is the same reason a stack is fast: it only ever touches an end, so nothing ever has to shuffle. All four operations are O(1), no matter how much it holds.

Its most famous use is the sliding-window maximum — one of the hardest common interview problems. A deque solves it in O(n) by keeping the window's candidates in decreasing order, dropping stale ones off the front and beaten ones off the back. That's only possible because both ends are open.

real-life analogy

Picture it

A queue where VIPs can jump in at the front

It's the line at a counter, but people can also join at the front (if they're important enough) and leave from the back (if they give up). It's still not a free-for-all — you can only ever touch the two ends. Nobody reaches into the middle.

interactive visualization

Watch it run

These get added alternately at the front and back. Then both ends are popped.

front · served firstback · joins here
    nobody waiting

A deque — 'deck' — is a queue that opens at both ends. You can add or remove at the front or the back, whichever suits you.

step 01/9

  • moving
1class Deque {
2 constructor() { this.items = []; }
3 pushFront(v) { this.items.unshift(v); }
4 pushBack(v) { this.items.push(v); }
5 popFront() { return this.items.shift(); }
6 popBack() { return this.items.pop(); }
7 peekFront() { return this.items[0]; }
8 peekBack() { return this.items[this.items.length - 1]; }
9 isEmpty() { return this.items.length === 0; }
10}

variables right now

size
0
comparisons 0moves 0

the dry run · every step, in words

9 steps

complexity

What it costs

best case
O(1)
average
O(1)
worst case
O(1)
extra memory
O(n)

All four operations — push and pop at either end — are O(1), because nothing ever shuffles. Built on a doubly linked list or a circular buffer; never on a plain array, where pushFront would be O(n).

  • O(1) · this one
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Building a deque on a plain array and using unshift() for pushFront.

    unshift shifts every element right — O(n). Use a real deque (a circular buffer or doubly linked list) where both ends are just pointers.

  • Reaching into the middle of a deque.

    You can't, and that's deliberate. If you need the middle, you want an array. The restriction is what buys the O(1).

  • Not realising you already have one.

    Python's collections.deque, Java's ArrayDeque, C++'s std::deque. Don't hand-roll it — and note that Java's ArrayDeque is the recommended stack *and* queue implementation.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+60 XP

01What makes a deque different from a queue?

02Use only pushBack and popBack on a deque. What have you built?

03Why is pushFront on a plain JavaScript array slow?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.