Introduction to Queues

EditorialUpdated Oct 31, 2026

First come, first served

At a ticket counter, whoever arrived first is served first, and newcomers join the back of the line. Print jobs, messages waiting for a server, and callers on hold at a call center all work the same way. A queue is that line as a data structure: you add at the back (enqueue) and remove at the front (dequeue), so the first thing in is the first thing out.

Four operations, each O(1) when the queue is built right: enqueue adds a value at the back, dequeue removes the front value and returns it, peek reads the front without removing it, and is-empty says whether anything is waiting. "Built right" is most of this lesson: the obvious way to build one is slow, and the fix is a small idea worth knowing well.

Enqueue at the back, dequeue at the front — A queue on an array: head marks the front, tail the next free slot.

A line of people at a counter drawn as a queue: values 1, 2, 3, 4 in a row, enqueue arrow joining at the back on the right, dequeue arrow leaving from the front on the left, and the order out 1, 2, 3, 4 matching the order in. A focal line reads: oldest out first, every operation O(1).

The obvious queue, and what it costs

The queue most people write first is a growing list: append at the back, remove at index 0. Python's list.pop(0) and JavaScript's array.shift() do exactly that. It reads fine, but removing the front of an array leaves a hole, and the array closes it by moving every remaining item one slot left. Draining a queue of n items does that n times.

On our judge, draining n items:

n	Python `list.pop(0)`	`collections.deque.popleft()`
10,000	8.3 ms	0.7 ms
100,000	823.1 ms	6.9 ms
200,000	4429.3 ms	13.7 ms

Ten times the items made pop(0) about 99 times slower, close to the 100 a quadratic cost predicts. The deque's time grew about 10 times, in step with n.

JavaScript is subtler. Its engine, V8, can usually skip the move: while an array's storage is small, it trims the front off in place, so shift() stays cheap. Past a size it can't, and every shift() copies the array. On our judge's Node 18, one shift() at the front of an array took:

Items in the array	One `shift()`
16,300	289 ns
16,400	2,930 ns
32,000	5,285 ns
128,000	30,149 ns

Under half a microsecond with 16,300 items, then about 10 times that with 16,400, and growing with the length after that. The jump sits at about 16,384 items: 128 KB of storage, the most V8 keeps in a regular heap object. A bigger array is stored where it can't be trimmed. So a small queue is fine, and a big one isn't: a queue kept at 10,000 items did 100,000 enqueue-and-dequeue pairs with shift() in 16.8 ms, and at 20,000 and 50,000 items it took 319.9 ms and 721.5 ms. Moving a head index instead took 8.2, 3.9 and 3.3 ms. A breadth-first search over a big graph holds a queue that size.

Move the index, not the items

The fix is to stop moving the items. Keep the queue in an array and an index, head, at the front. Dequeue reads data[head] and steps head forward; nothing else moves. In the step-through above, the served slots on the left simply went dead.

Dead slots are the catch: the array only grows to the right. So let the indexes wrap around. With room for capacity items, the slot after the last one is slot 0 again: (i + 1) % capacity. Now the slots a dequeue frees are reused by later enqueues, and the array is a ring buffer (a circular queue).

A ring buffer of five slots drawn as a circle: slots 2, 3, 4 and 0 hold values, slot 1 is free. A head arrow points at slot 2, the front; a tail arrow points at slot 1, the next free slot, after wrapping from slot 4 round to 0. A focal line reads: tail = (head + count) % capacity.

A ring of five slots — The tail wraps from the last slot back to 0, into a slot a dequeue freed.

There's one more catch. When the queue is empty, head and tail sit on the same slot. When it's full, the tail has gone all the way round, and head and tail sit on the same slot again. The two indexes alone can't tell empty from full. The usual cure is to keep a count of the items, which also means you don't need to store the tail at all: it's (head + count) % capacity. (The other cure leaves one slot always unused, so a full ring has tail just behind head.)

Two identical rings of four slots, both with head and tail on slot 1. The left ring is empty, every slot hollow; the right ring is full, every slot holding a value. Under each, a count badge: 0 and 4. A focal line reads: head == tail in both, so keep a count.

class RingQueue {
    vector<int> data;                    // the slots, reused in a circle
    int head = 0;                        // index of the front item
    int count = 0;                       // how many items are queued
public:
    explicit RingQueue(int capacity) : data(capacity) {}
    bool enqueue(int x) {
        if (count == (int)data.size()) return false;            // full
        data[(head + count) % data.size()] = x;                 // the tail slot
        count++;
        return true;
    }
    int dequeue() {
        if (count == 0) throw underflow_error("dequeue from an empty queue");
        int x = data[head];
        head = (head + 1) % data.size();                        // the head moves on, wrapping
        count--;
        return x;
    }
    int front() const {
        if (count == 0) throw underflow_error("front of an empty queue");
        return data[head];
    }
    int rear() const {
        if (count == 0) throw underflow_error("rear of an empty queue");
        return data[(head + count - 1) % data.size()];
    }
    bool isEmpty() const { return count == 0; }
    bool isFull() const { return count == (int)data.size(); }
};

class RingQueue:
    def __init__(self, capacity):
        self.data = [None] * capacity    # the slots, reused in a circle
        self.head = 0                    # index of the front item
        self.count = 0                   # how many items are queued

    def enqueue(self, x):
        if self.count == len(self.data):
            return False                 # full
        self.data[(self.head + self.count) % len(self.data)] = x   # the tail slot
        self.count += 1
        return True

    def dequeue(self):
        if self.count == 0:
            raise IndexError("dequeue from an empty queue")
        x = self.data[self.head]
        self.data[self.head] = None
        self.head = (self.head + 1) % len(self.data)   # the head moves on, wrapping
        self.count -= 1
        return x

    def front(self):
        if self.count == 0:
            raise IndexError("front of an empty queue")
        return self.data[self.head]

    def rear(self):
        if self.count == 0:
            raise IndexError("rear of an empty queue")
        return self.data[(self.head + self.count - 1) % len(self.data)]

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

    def is_full(self):
        return self.count == len(self.data)

static class RingQueue {
    private final int[] data;            // the slots, reused in a circle
    private int head = 0;                // index of the front item
    private int count = 0;               // how many items are queued
    RingQueue(int capacity) { data = new int[capacity]; }
    boolean enqueue(int x) {
        if (count == data.length) return false;                 // full
        data[(head + count) % data.length] = x;                 // the tail slot
        count++;
        return true;
    }
    int dequeue() {
        if (count == 0) throw new IllegalStateException("dequeue from an empty queue");
        int x = data[head];
        head = (head + 1) % data.length;                        // the head moves on, wrapping
        count--;
        return x;
    }
    int front() {
        if (count == 0) throw new IllegalStateException("front of an empty queue");
        return data[head];
    }
    int rear() {
        if (count == 0) throw new IllegalStateException("rear of an empty queue");
        return data[(head + count - 1) % data.length];
    }
    boolean isEmpty() { return count == 0; }
    boolean isFull() { return count == data.length; }
}

class RingQueue {
    constructor(capacity) {
        this.data = new Array(capacity); // the slots, reused in a circle
        this.head = 0;                   // index of the front item
        this.count = 0;                  // how many items are queued
    }
    enqueue(x) {
        if (this.count === this.data.length) return false;               // full
        this.data[(this.head + this.count) % this.data.length] = x;      // the tail slot
        this.count++;
        return true;
    }
    dequeue() {
        if (this.count === 0) throw new Error("dequeue from an empty queue");
        const x = this.data[this.head];
        this.data[this.head] = undefined;
        this.head = (this.head + 1) % this.data.length;                 // the head moves on, wrapping
        this.count--;
        return x;
    }
    front() {
        if (this.count === 0) throw new Error("front of an empty queue");
        return this.data[this.head];
    }
    rear() {
        if (this.count === 0) throw new Error("rear of an empty queue");
        return this.data[(this.head + this.count - 1) % this.data.length];
    }
    isEmpty() { return this.count === 0; }
    isFull() { return this.count === this.data.length; }
}

Each printed full 1 2 4 2 3 4 empty: the fourth enqueue into room for three was refused, the dequeue gave 1, and 4 went round into slot 0, which the 1 had just left. Front and rear were 2 and 4, then the queue drained in order and ended empty.

Growing a full ring

A fixed ring refuses an enqueue when it's full, which is what a bounded buffer should do. To grow instead, allocate twice the room and copy the items out in queue order: front first, following the wrap, into slots 0, 1, 2 and on. The front is at slot 0 again and nothing has wrapped:

class GrowingRing:
    def __init__(self):
        self.data = [None]               # start with one slot
        self.head = 0
        self.count = 0
        self.copies = 0                  # items copied by every grow, in total

    def enqueue(self, x):
        if self.count == len(self.data):
            self.grow()
        self.data[(self.head + self.count) % len(self.data)] = x
        self.count += 1

    def grow(self):
        bigger = [None] * (2 * len(self.data))
        for i in range(self.count):      # copy out in queue order: front first
            bigger[i] = self.data[(self.head + i) % len(self.data)]
        self.copies += self.count
        self.data, self.head = bigger, 0

    def dequeue(self):
        x = self.data[self.head]
        self.data[self.head] = None
        self.head = (self.head + 1) % len(self.data)
        self.count -= 1
        return x

We ran a million random enqueues and dequeues starting from a single slot. 600,190 enqueues caused 262,143 copies in all, 0.44 per item, and every dequeue matched a reference queue. The ring ended with 262,144 slots. A doubling copies each item in the queue once, and doublings get rarer as the ring grows, so an enqueue is O(1) amortized, the same argument as a growing array's push.

Now you run the ring buffer

Below, you are the ring buffer. Choose an operation, then click the slot it uses: the slot where an enqueue writes, or the slot a dequeue reads. A wrong slot is refused with the arithmetic that names the right one. Fill the ring and an enqueue is refused, so dequeue first, or grow it: you copy each item into the new ring yourself, in queue order.

Ring Buffer: choose the slot, wrap around, and grow it when full

On a linked list

A linked list makes a queue without any wrapping: keep a head pointer for the front and a tail pointer for the back. Enqueue links a new node after the tail; dequeue unlinks the head. Both are O(1), and there's no capacity to run out of, at the price of a node per item:

struct Node {
    int val;
    Node* next = nullptr;
    explicit Node(int v) : val(v) {}
};

class LinkedQueue {
    Node* head = nullptr;                // the front: dequeue unlinks it
    Node* tail = nullptr;                // the back: enqueue links after it
public:
    void enqueue(int x) {
        Node* node = new Node(x);
        if (tail) tail->next = node;
        else head = node;                // the queue was empty
        tail = node;
    }
    int dequeue() {
        if (!head) throw underflow_error("dequeue from an empty queue");
        Node* node = head;
        int x = node->val;
        head = head->next;
        if (!head) tail = nullptr;       // empty again: forget the old tail too
        delete node;
        return x;
    }
    int front() const {
        if (!head) throw underflow_error("front of an empty queue");
        return head->val;
    }
    bool isEmpty() const { return head == nullptr; }
};

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


class LinkedQueue:
    def __init__(self):
        self.head = None                 # the front: dequeue unlinks it
        self.tail = None                 # the back: enqueue links after it

    def enqueue(self, x):
        node = Node(x)
        if self.tail:
            self.tail.next = node
        else:
            self.head = node             # the queue was empty
        self.tail = node

    def dequeue(self):
        if self.head is None:
            raise IndexError("dequeue from an empty queue")
        x = self.head.val
        self.head = self.head.next
        if self.head is None:
            self.tail = None             # empty again: forget the old tail too
        return x

    def front(self):
        if self.head is None:
            raise IndexError("front of an empty queue")
        return self.head.val

    def is_empty(self):
        return self.head is None

static class Node {
    int val;
    Node next;
    Node(int val) { this.val = val; }
}

static class LinkedQueue {
    private Node head;                   // the front: dequeue unlinks it
    private Node tail;                   // the back: enqueue links after it
    void enqueue(int x) {
        Node node = new Node(x);
        if (tail != null) tail.next = node;
        else head = node;                // the queue was empty
        tail = node;
    }
    int dequeue() {
        if (head == null) throw new IllegalStateException("dequeue from an empty queue");
        int x = head.val;
        head = head.next;
        if (head == null) tail = null;   // empty again: forget the old tail too
        return x;
    }
    int front() {
        if (head == null) throw new IllegalStateException("front of an empty queue");
        return head.val;
    }
    boolean isEmpty() { return head == null; }
}

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class LinkedQueue {
    constructor() {
        this.head = null;                // the front: dequeue unlinks it
        this.tail = null;                // the back: enqueue links after it
    }
    enqueue(x) {
        const node = new Node(x);
        if (this.tail) this.tail.next = node;
        else this.head = node;           // the queue was empty
        this.tail = node;
    }
    dequeue() {
        if (this.head === null) throw new Error("dequeue from an empty queue");
        const x = this.head.val;
        this.head = this.head.next;
        if (this.head === null) this.tail = null;   // empty again: forget the old tail too
        return x;
    }
    front() {
        if (this.head === null) throw new Error("front of an empty queue");
        return this.head.val;
    }
    isEmpty() { return this.head === null; }
}

Each printed 1 2 3 4 empty 5. The last two calls test the subtle line: when the queue empties, tail has to be cleared too, or the next enqueue links onto a node that already left (it's in the bugs below).

Both ends, and the queues your language gives you

A deque (double-ended queue, said "deck") adds and removes at both ends. On a ring buffer that's one more move: to add at the front, step head back one slot. Stepping back has to wrap too, and (head - 1 + capacity) % capacity does it in every language. Without the + capacity it goes wrong in three of the four, as the bugs show.

Each language's library has a queue built in, except JavaScript. Enqueue 1, 2, 3 and dequeue once:

queue<int> q;                        // push at the back, pop at the front
for (int x : {1, 2, 3}) q.push(x);
int first = q.front();               // read the front first: pop() returns nothing
q.pop();
cout << first << " " << q.front() << " " << q.size() << "\n";

from collections import deque

q = deque()                          # append at the back, popleft at the front
for x in (1, 2, 3):
    q.append(x)
first = q.popleft()
print(first, q[0], len(q))

Queue<Integer> q = new ArrayDeque<>(); // offer at the back, poll at the front
for (int x : new int[]{1, 2, 3}) q.offer(x);
int first = q.poll();
System.out.println(first + " " + q.peek() + " " + q.size());

const q = [];                        // no queue type: an array and a head index
let head = 0;
for (const x of [1, 2, 3]) q.push(x);
const first = q[head++];             // dequeue by moving the index, not shift()
console.log(first, q[head], q.length - head);

Each printed 1 2 2: 1 came out, 2 is the new front, and two items are left. What each one does when you dequeue an empty queue, on our judge:

Language	Queue / deque	Dequeue when empty
C++	`std::queue` / `std::deque`	`front()` and `pop()` are undefined behaviour: check `empty()`
Python	`collections.deque`	`popleft()` raises `IndexError: pop from an empty deque`
Java	`ArrayDeque` as `Queue` / `Deque`	`poll()` and `peek()` return `null`; `remove()` throws `NoSuchElementException`
JavaScript	none: an array with a head index, or a ring	reading past the end gives `undefined`

Two traps are hiding in that table.

In Python, queue.Queue sounds right but is built for threads: it takes a lock on every call. 100,000 items in and out took 417.8 ms against 15.8 ms for a deque.

In Java, poll() returns null on an empty queue, and storing that in an int unboxes it: int x = q.poll(); threw NullPointerException. And prefer ArrayDeque to LinkedList: holding two million items, ArrayDeque's array took 5.6 bytes per item, a slot each plus room to grow, and LinkedList took 24.0, because every item gets a node object of its own.

Three simulations a queue runs

A time window. Number of Recent Calls counts the pings in the last 3,000 milliseconds. Pings arrive in time order, so the oldest is always at the front, and once it's too old it can never count again:

from collections import deque


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

    def ping(self, t):
        self.pings.append(t)
        while self.pings[0] < t - 3000:  # older than the window: it can never count again
            self.pings.popleft()
        return len(self.pings)

For pings at 1, 100, 3001 and 3002 it returned 1, 2, 3, 3: at 3002, the ping at 1 had left the window. Moving Average from Data Stream is the same window counted by size, with a running total:

from collections import deque


class MovingAverage:
    def __init__(self, size):
        self.size = size
        self.window = deque()
        self.total = 0

    def next(self, val):
        self.window.append(val)
        self.total += val
        if len(self.window) > self.size:
            self.total -= self.window.popleft()   # the oldest value leaves the window
        return self.total / len(self.window)

With a window of 3, the values 1, 10, 3, 5 gave averages 1.0, 5.5, 4.66667, 6.0.

Dealing cards. Reveal Cards In Increasing Order: a dealer turns up the top card, moves the next one to the bottom, and repeats. Arrange the deck so the cards come up in increasing order. Run the dealer on the positions instead of the cards, with a queue, and give the smallest card to the first position revealed:

from collections import deque


def deck_revealed_increasing(deck):
    positions = deque(range(len(deck)))  # the order the dealer will turn the cards up
    answer = [0] * len(deck)
    for card in sorted(deck):
        answer[positions.popleft()] = card               # this position is revealed next
        if positions:
            positions.append(positions.popleft())        # the next card goes to the bottom
    return answer

For 17, 13, 11, 2, 3, 5, 7 it returned [2, 13, 3, 11, 5, 17, 7], which the dealer turns up as 2, 3, 5, 7, 11, 13, 17.

The Josephus circle. Find the Winner of the Circular Game: n friends sit in a circle; count k of them, and the k-th leaves; repeat from the next one. A queue is the circle: counting a friend moves them from the front to the back.

from collections import deque


def find_the_winner(n, k):
    circle = deque(range(1, n + 1))
    while len(circle) > 1:
        for _ in range(k - 1):
            circle.append(circle.popleft())  # count past k - 1 friends: they go round to the back
        circle.popleft()                     # the k-th leaves the circle
    return circle[0]

Five friends, every 2nd leaves — The circle as a queue, front first. Counting a friend moves them to the back.

It returned 3 for 5 friends counting 2, after 2, 4, 1, 5 went out in that order, and 1 for 6 counting 5. The queue does about n × k moves. That's fine for the problem's limits; for a huge n there's a formula with no queue at all.

Spotting it, and when it breaks

The clues. "In the order they arrived", "first come, first served", "process level by level" or "nearest first" (breadth-first search, in Graphs). A window of the last N items or N seconds. Going round a circle, or moving something to the back. Whenever the oldest waiting item is the next one you need, a queue holds the rest.

The near-misses. The most recent first is a stack (Introduction to Stacks). The smallest or most urgent first is a heap: a priority queue isn't first in, first out, despite the name. The maximum of a sliding window is a deque used a special way, which is the next lesson, Monotonic Deque: the Window's Maximum.

When it breaks. A fixed ring fills up: refuse, or grow. list.pop(0) and a big shift() turn a queue quadratic, as the runs above show. And a Java poll() can hand you null.

Bugs that cost a submission

One test for empty and full. This ring has no count, and tests head == tail for empty:

class Ring:
    def __init__(self, capacity):
        self.data = [None] * capacity
        self.head = self.tail = 0

    def is_empty(self):
        return self.head == self.tail    # also true when the ring is full

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

Three enqueues into room for three, then is_empty(): it returned True. The full ring looks empty, so the next dequeue says there's nothing there, or the next enqueue overwrites the front. Keep a count.

A negative index when stepping back. Adding at a deque's front steps head back with (head - 1) % capacity. With head at 0 and room for 4, on our judge:

Language	`(0 - 1) % 4`
C++	`-1`: an out-of-bounds index, undefined behaviour
Python	`3`: right, because Python's `%` takes the divisor's sign
Java	`-1`: `ArrayIndexOutOfBoundsException` on the next access
JavaScript	`-1`: `data[-1]` is a property, not a slot, so the queue never sees the value

Write (head - 1 + capacity) % capacity in every language.

A tail that outlives its node. This linked-list queue forgets to clear tail when the last node leaves:

class LinkedQueue:
    def __init__(self):
        self.head = self.tail = None

    def enqueue(self, x):
        node = Node(x)
        if self.tail:
            self.tail.next = node        # the old tail may be a node that already left
        else:
            self.head = node
        self.tail = node

    def dequeue(self):
        x = self.head.val
        self.head = self.head.next       # tail still points at the node that left
        return x

    def is_empty(self):
        return self.head is None

Enqueue 1, dequeue it, enqueue 2, then ask if it's empty: True. The 2 was linked onto the departed node, so head never saw it.

shift() or pop(0) in a big loop. Fine at a few thousand items and quadratic at a hundred thousand, as the tables above show. Use a deque, or a head index.

int x = q.poll() in Java. On an empty queue that's a NullPointerException. Check isEmpty() first.

Check yourself

Quiz

1 / 6

Multiple choice

A ring buffer with room for 5 has head = 3 and count = 4. Which slot does the next enqueue write?

Practice problems

From easier to harder:

Queue using Array: a head index.
Queue using Linked List: head and tail pointers.
Implement Stack using Queues: the opposite trick to two stacks making a queue.
Number of Recent Calls: a time window.
Moving Average from Data Stream: a window counted by size.
Design Circular Queue: the ring buffer.
Design Circular Deque: the ring buffer at both ends.
Reveal Cards In Increasing Order: run the dealer on positions.
Find the Winner of the Circular Game: the Josephus circle.

Next, Monotonic Deque: the Window's Maximum: a deque that keeps only the values that can still win.