Data structure 7 of 12

Queues and deques

A queue is a line: join at the back, leave from the front. The first one in is the first one out. A deque (double-ended queue) lets you add and remove at both ends, all in O(1).

A 2-minute conversation: Sam asks, Priya explains

0:00 / 2:11

Follow along on the page Pause on “your turn” questions

Sam Queues. The opposite of a stack?
Priya In order of service, yes. A queue is a line: join at the back, leave from the front. First in, first out. And a deque lets you add and remove at both ends, all in constant time.
Priya The queue at a bakery. New customers join at the back, the front is served next, and nobody pushes in.
Sam And deque is pronounced deck?
Priya Deck. Double-ended queue. It can act as a queue, a stack, or both.
Sam Why not just use a list?
Priya Removing from the front of a list shifts every other item. So list dot pop zero is linear, and in a breadth-first search over a big graph that becomes quadratic. A real queue moves the front instead of the items: a ring buffer with a head index that wraps around the end of its array.
Sam Costs with a deque?
Priya Add or remove at either end: constant. Peek at either end: constant. Reading the middle: linear, so if you need positions, you need a list.
Priya Your turn. Why is pop zero on a Python list slow?
Priya It shifts every remaining element left. A deque's popleft is constant.
Sam Language notes?
Priya Python's collections dot deque, Java's ArrayDeque. JavaScript has no deque, so keep a head index instead of calling shift.
Sam The players?
Priya A queue built by hand as a ring buffer, with three slots, where the back wraps round to slot zero. Processing jobs in arrival order, where a retried job waits behind everything already queued. And keeping only recent events: new ones join the back and old ones leave from the front.
Sam Memory hook?
Priya The bakery queue. Append at the back, popleft at the front, never pop zero.
Sam Problems?
Priya Number of recent calls, counting pings in the last three seconds. And the lunch queue, where students who don't want the top sandwich go to the back, until nobody in the line wants it.
Sam Mistakes?
Priya Pop zero and shift. Popping the wrong end, which turns your queue into a stack. Reading an empty queue. And indexing the middle of a deque.
Sam Next?
Priya Lesson eight, heaps: a queue where the most important item always goes first.

1. What it is

The queue at a bakery. New customers join at the back; the person at the front is served next. Nobody pushes in and nobody leaves from the middle. Whoever has waited longest goes first.

A queue follows FIFO: first in, first out. Its operations, all O(1):

enqueue(x) (also called offer or push back): add x at the back.
dequeue() (poll, pop front): remove and return the front.
peek(): look at the front.

A deque (say "deck") adds the mirror operations: push at the front and pop from the back. It can act as a queue, a stack, or both at once.

2. How it sits in memory

A plain list makes a poor queue: removing from the front shifts every other item left, so each pop(0) is O(n). A real queue avoids shifting by moving the front instead of the items: a ring buffer keeps two indices and wraps around the end of its array.

Python's collections.deque, Java's ArrayDeque and similar classes do this for you, so both ends are O(1).

3. Operations and what they cost

Operation	Python `deque`	Cost	With a plain list
Add at the back	`q.append(x)`	`O(1)`	`O(1)`
Remove from the front	`q.popleft()`	`O(1)`	`O(n)` with `pop(0)`
Add at the front	`q.appendleft(x)`	`O(1)`	`O(n)`
Remove from the back	`q.pop()`	`O(1)`	`O(1)`
Peek front, back	`q[0]`, `q[-1]`	`O(1)`	`O(1)`
Read the middle	`q[i]`	`O(n)`	`O(1)`

When it mattersBreadth-first search pops from the front once per node. With list.pop(0) a big search becomes O(n²); with a deque it stays O(n).

4. In Python, TypeScript and Java

Use the language's deque; never shift a plain array from the front in a loop.

from collections import deque
    q = deque()
    q.append("ana")        # join at the back
    q.append("ben")
    front = q[0]           # peek: "ana"
    first = q.popleft()    # "ana" leaves from the front
    q.appendleft("vip")    # a deque can add at the front too
    last = q.pop()         # and remove from the back

// JavaScript has no built-in deque. For interview-sized inputs, keep a
    // "head" index instead of calling shift(), which moves every element.
    const q: string[] = [];
    let head = 0;
    q.push("ana"); q.push("ben");        // join at the back
    const first = q[head++];             // "ana" leaves in O(1)
    const size = q.length - head;        // 1

Deque<String> q = new ArrayDeque<>();
    q.offerLast("ana");               // join at the back
    q.offerLast("ben");
    String front = q.peekFirst();     // "ana"
    String first = q.pollFirst();     // "ana" leaves
    q.offerFirst("vip");              // add at the front
    String last = q.pollLast();       // remove from the back

5. Core operations, step by step

A queue by hand first, then the two ways queues are used most.

A · A queue by hand (a ring buffer)

What it doesKeeps the items in a fixed array with a head index and a size; the back wraps around to the start.

Picture itA round table with numbered seats: the 'front' badge moves round the table instead of everyone changing chairs.

CostO(1) per enqueue and dequeue: nothing ever shifts.

The code. The modulo (%) makes the index wrap from the last slot back to 0.

class RingQueue:
    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.head = 0
        self.size = 0

    def enqueue(self, x):
        tail = (self.head + self.size) % len(self.slots)
        self.slots[tail] = x
        self.size += 1

    def dequeue(self):
        x = self.slots[self.head]
        self.head = (self.head + 1) % len(self.slots)
        self.size -= 1
        return x

class RingQueue {
  slots: (number | null)[];
  head = 0;
  size = 0;
  constructor(capacity: number) { this.slots = new Array(capacity).fill(null); }

  enqueue(x: number): void {
    const tail = (this.head + this.size) % this.slots.length;
    this.slots[tail] = x;
    this.size += 1;
  }

  dequeue(): number {
    const x = this.slots[this.head]!;
    this.head = (this.head + 1) % this.slots.length;
    this.size -= 1;
    return x;
  }
}

static class RingQueue {
    int[] slots; int head = 0, size = 0;
    RingQueue(int capacity) { slots = new int[capacity]; }

    void enqueue(int x) {
        int tail = (head + size) % slots.length;
        slots[tail] = x;
        size += 1;
    }

    int dequeue() {
        int x = slots[head];
        head = (head + 1) % slots.length;
        size -= 1;
        return x;
    }
}

Line by line.

Line	What it does	Why
`tail = (self.head + self.size) % len(self.slots)`	The first free slot after the last item.	% wraps past the end back to slot 0.
`self.head = (self.head + 1) % len(self.slots)`	The front moves one seat on.	Moving an index is O(1); shifting items would be O(n).

Watch it run. A 3-slot queue: enqueue 1, 2; dequeue; enqueue 3, 4 (4 wraps round to slot 0); dequeue three times.

Watch out for:

Forgetting the modulo. The index runs past the end of the array instead of wrapping.

B · Process in arrival order

What it doesServes whoever has waited longest; new arrivals join the back while serving goes on.

Picture itThe bakery: serve the front customer; anyone who walks in joins the back.

CostO(n) for n items.

The code. Each job may create follow-up jobs; they wait their turn behind everything already queued.

from collections import deque

def run_jobs(jobs):
    q = deque(jobs)
    done = []
    while q:
        job = q.popleft()
        done.append(job)
        if job.endswith("!"):
            q.append(job[:-1] + "-retry")
    return done

function runJobs(jobs: string[]): string[] {
  const q = [...jobs];
  let head = 0;
  const done: string[] = [];
  while (head < q.length) {
    const job = q[head++];
    done.push(job);
    if (job.endsWith("!")) {
      q.push(job.slice(0, -1) + "-retry");
    }
  }
  return done;
}

static List<String> runJobs(String[] jobs) {
    Deque<String> q = new ArrayDeque<>(List.of(jobs));
    List<String> done = new ArrayList<>();
    while (!q.isEmpty()) {
        String job = q.pollFirst();
        done.add(job);
        if (job.endsWith("!")) {
            q.offerLast(job.substring(0, job.length() - 1) + "-retry");
        }
    }
    return done;
}

Line by line.

Line	What it does	Why
`job = q.popleft()`	Serve the front.	O(1) on a deque.
`q.append(...)`	A follow-up job joins the back.	It waits behind c, which arrived earlier: fair, first come first served.

Watch it run. Jobs a, b! (needs a retry) and c.

Watch out for:

list.pop(0) in the loop. O(n) per pop. Use a deque (or a head index in TypeScript).

C · Keep only the recent ones (a sliding window of time)

What it doesAdds each new event at the back and drops events at the front that are too old.

Picture itA queue for a ride that closes its gate: people who've waited longer than 10 minutes give up and leave from the front.

CostO(1) amortised per event: each event is added once and removed once.

The code. Old items are always at the front, because they arrived first.

from collections import deque

def recent_counts(times, window):
    q = deque()
    out = []
    for t in times:
        q.append(t)
        while q[0] < t - window:
            q.popleft()
        out.append(len(q))
    return out

function recentCounts(times: number[], window: number): number[] {
  const q: number[] = [];
  let head = 0;
  const out: number[] = [];
  for (const t of times) {
    q.push(t);
    while (q[head] < t - window) {
      head++;
    }
    out.push(q.length - head);
  }
  return out;
}

static List<Integer> recentCounts(int[] times, int window) {
    Deque<Integer> q = new ArrayDeque<>();
    List<Integer> out = new ArrayList<>();
    for (int t : times) {
        q.offerLast(t);
        while (q.peekFirst() < t - window) {
            q.pollFirst();
        }
        out.add(q.size());
    }
    return out;
}

Line by line.

Line	What it does	Why
`q.append(t)`	The newest event joins the back.
`while q[0] < t - window`	Is the oldest event too old?	Times only grow, so the oldest is always at the front.
`q.popleft()`	It leaves from the front.	Each event leaves at most once: O(1) amortised.

Watch it run. Events at times 1, 100, 3001 and 3002, keeping the last 3000 ms.

Watch out for:

Re-counting every event each time. That's O(n) per call; the queue drops old events once.

6. How to remember it

Memory hook: "The bakery queue"Join at the back, leave from the front, nobody pushes in. A deque is a queue with a door at both ends.

Picture

A line of customers with a ticket machine at the back and the counter at the front.

Chant

"Append at the back, popleft at the front, never pop(0)."

Key rule

Oldest first? Queue. Newest first? Stack. Both ends? Deque.

7. Problems solved with it

Two easy problems that are queues in disguise.

LC 933 · Number of Recent Calls

The problemEach call to ping(t) (times strictly increasing) returns how many pings happened in [t − 3000, t].

What it doesOperation C, as a class.

CostO(1) amortised per ping.

The code. The deque holds exactly the pings still inside the window.

from collections import deque

class RecentCounter:
    def __init__(self):
        self.q = deque()

    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)

class RecentCounter {
  q: number[] = [];
  head = 0;

  ping(t: number): number {
    this.q.push(t);
    while (this.q[this.head] < t - 3000) {
      this.head++;
    }
    return this.q.length - this.head;
  }
}

static class RecentCounter {
    Deque<Integer> q = new ArrayDeque<>();

    int ping(int t) {
        q.offerLast(t);
        while (q.peekFirst() < t - 3000) {
            q.pollFirst();
        }
        return q.size();
    }
}

Line by line.

Line	What it does	Why
`while self.q[0] < t - 3000`	Drop pings older than the window.

Watch it run. Pings at 1, 100, 3001, 3002.

Watch out for:

Keeping every ping forever and counting. Memory and time grow without bound.

LC 1700 · Number of Students Unable to Eat Lunch

The problemStudents queue for sandwiches (0 or 1); the stack of sandwiches is served from the top. A student takes the top sandwich if it's their type, otherwise goes to the back of the queue. Return how many can't eat.

What it doesSimulates the queue until nobody in it wants the top sandwich.

CostO(n²) worst case for the simulation; fine for n ≤ 100.

The code. Stop when everyone has been sent to the back once in a row without eating.

from collections import deque

def count_students(students, sandwiches):
    q = deque(students)
    top = 0
    misses = 0
    while q and misses < len(q):
        s = q.popleft()
        if s == sandwiches[top]:
            top += 1
            misses = 0
        else:
            q.append(s)
            misses += 1
    return len(q)

function countStudents(students: number[], sandwiches: number[]): number {
  const q = [...students];
  let head = 0, top = 0, misses = 0;
  while (head < q.length && misses < q.length - head) {
    const s = q[head++];
    if (s === sandwiches[top]) {
      top += 1;
      misses = 0;
    } else {
      q.push(s);
      misses += 1;
    }
  }
  return q.length - head;
}

static int countStudents(int[] students, int[] sandwiches) {
    Deque<Integer> q = new ArrayDeque<>();
    for (int s : students) q.offerLast(s);
    int top = 0, misses = 0;
    while (!q.isEmpty() && misses < q.size()) {
        int s = q.pollFirst();
        if (s == sandwiches[top]) {
            top += 1;
            misses = 0;
        } else {
            q.offerLast(s);
            misses += 1;
        }
    }
    return q.size();
}

Line by line.

Line	What it does	Why
`s = q.popleft()`	The student at the front steps up.
`q.append(s)`	Wrong sandwich: back of the queue.	The queue rotates.
`misses < len(q)`	Stop after a full round with nobody eating.	Otherwise the loop would rotate forever.

Watch it run. Students [1, 1, 0, 0], sandwiches [0, 1, 0, 1] (top first).

Watch out for:

No stopping rule. When nobody wants the top sandwich, the queue rotates forever.

More practice, solved on the pattern pages

#	Problem	Level	Where
637	Average of Levels in Binary Tree	Easy	Solved step by step on 12 · Breadth-First Search (BFS)
102	Binary Tree Level Order Traversal	Medium	Solved step by step on 10 · Binary Tree Traversal
994	Rotting Oranges	Medium	Solved step by step on 12 · Breadth-First Search (BFS)
239	Sliding Window Maximum	Hard	Solved step by step on 03 · Sliding Window

8. Common mistakes

list.pop(0) and array.shift()Both shift every element: O(n) per call. Use collections.deque, Java's ArrayDeque, or a head index in TypeScript.

Popping the wrong endA queue takes from the front (popleft); pop() takes from the back and turns your queue into a stack.

Reading an empty queueq[0] or popleft() on an empty deque raises IndexError. Check while q:.

Indexing the middle of a dequeq[i] is O(n) for a deque. If you need random access, you need a list.

9. Self-check quiz

Enqueue 1, enqueue 2, enqueue 3, then dequeue. What comes out?

First in, first out.

Why is list.pop(0) slow?

Arrays keep items in consecutive slots, so removing the first moves all the rest.

Best way to build a queue in Python?

O(1) at both ends.

You need to add and remove at both ends quickly. Which structure?

A double-ended queue: O(1) at the front and the back.

10. Where it shows up next

12 · BFS: a queue explores a graph ring by ring, giving shortest paths in unweighted graphs.
10 · Binary Tree Traversal: level-order traversal is BFS on a tree.
03 · Sliding Window: a deque keeps the maximum of a moving window.

Next structure: 08 · Heaps and priority queues, a queue where the most important item always goes first.