Queue Data Structure: FIFO, Circular Buffer and Deque

A queue is a line at a counter: people join at the back and are served from the front, so whoever arrived first leaves first. That rule is first in, first out, or FIFO, the mirror image of the stack's last in, first out. Whenever work must be handled in the order it arrived — print jobs, network packets, requests to a server, the nodes of a graph discovered one layer at a time — a queue is doing it.

Why a plain array is the wrong queue

The obvious queue is an array: append at the back, remove from index 0. But removing index 0 shifts every remaining element one place left, so serving n items costs about n²/2 moves — around 5 × 10⁹ for a breadth-first search over 100,000 nodes. Python's list.pop(0) and JavaScript's array.shift() look innocent and do exactly this. The fix is not to move the elements at all, but to move the front.

1. Both hold the queue 1, 2, 3, 4, 5, 6 with the front at index 0. The top one dequeues the way list.pop(0) and array.shift() do; the bottom one keeps a head index instead.
2. Dequeue 1. Removing index 0 leaves a hole, so every remaining element moves one place left: 5 moves. The head index version moves nothing — it reads slots[0] and sets head = 1.
3. Dequeue 2: 4 more moves, 9 so far, while head just steps to 2. The array's work grows with every element still waiting.
4. Dequeue 3: 12 moves so far against 3 head steps. Serving all n items costs n(n − 1)/2 moves the first way — 5 × 10⁹ for 100,000 — and n steps the second.

The idea: first in, first out

A queue offers enqueue (put an item at the back), dequeue (remove and return the front), peek (read the front) and a size check. Because nobody can jump the line, items come out in exactly the order they went in.

Round-robin scheduling shows why that order is useful. Each task runs for a short slice of time, a quantum; if it is not finished, it rejoins at the back. Every task waits at most one round before running again, so none is starved.

1. Round robin shares one processor fairly: each task runs for at most 2 time units, then goes to the back of the line. A queue is that line (take from the front, add at the back), so the order of turns falls straight out of first in, first out.
2. A runs from t=0 to t=2 and still needs 1, so it goes to the back of the queue behind B, C and D. It will not run again until each of them has had a turn.
3. B runs from t=2 to t=4 and still needs 3, so it goes to the back of the queue behind C, D and A. It will not run again until each of them has had a turn.
4. C runs from t=4 to t=6 and is finished, so it leaves the queue for good. D is now at the front and runs next.
5. D runs from t=6 to t=8 and still needs 2, so it goes to the back of the queue behind A and B. It will not run again until each of them has had a turn.
6. A runs from t=8 to t=9, needing only 1 of its 2, and is finished, so it leaves the queue for good. B is now at the front and runs next.
7. B runs from t=9 to t=11 and still needs 1, so it goes to the back of the queue behind D. It will not run again until D has had a turn.
8. D runs from t=11 to t=13 and is finished, so it leaves the queue for good. B is now at the front and runs next.
9. B runs its last unit, t=13 to t=14, and the queue is empty: C finished at 6, A finished at 9, D finished at 13 and B finished at 14. Each turn is one O(1) dequeue plus at most one enqueue, so the schedule costs O(turns), 8 here.

How a queue is stored: the circular buffer

The fast array-based queue keeps its elements still and stores two numbers: head, the index of the front, and size. Taking every index modulo the capacity turns the array into a ring, so the slots head leaves behind are reused.

1. The queue keeps its elements still and moves its front instead. It stores head, the index of the front element, and size; the next free slot is (head + size) mod 5, so the array behaves like a ring.
2. enqueue 1: write slots[(0 + 0) mod 5] = slots[0], then size = 1.
3. enqueue 2: write slots[(0 + 1) mod 5] = slots[1], then size = 2.
4. enqueue 3: write slots[(0 + 2) mod 5] = slots[2], then size = 3.
5. dequeue reads slots[0] = 1, moves head to 1 and takes one from size. Nothing moves; the old 1 stays in memory, outside the queue, until a later enqueue writes over it.
6. dequeue returns 2 and head steps to 2. Two slots at the front are now free — the space a plain array would have wasted.
7. enqueue 4: write slots[(2 + 1) mod 5] = slots[3], then size = 2.
8. enqueue 5: write slots[(2 + 2) mod 5] = slots[4], then size = 3.
9. enqueue 6: (2 + 3) mod 5 = 0. The index runs past the end and wraps round to slot 0, freed by a dequeue — nothing shifts, so the queue now occupies slots 2, 3, 4, 0, in that order.
10. enqueue 7: write slots[(2 + 4) mod 5] = slots[1], then size = 5.
11. enqueue 8: size = 5 = capacity, so the queue is full and refuses it (a growing queue would copy into a bigger array, starting at head). Keeping a count is what makes full easy to tell from empty.

Why it is correct: the queue is always the size slots starting at head, wrapping past the end. Enqueue adds a slot at the end of that run and dequeue removes one from its start, so the run stays contiguous and never overlaps itself while size is within the capacity. Nothing shifts: both are O(1). Keeping size rather than a tail index is deliberate.

A queue that must grow copies its elements into a larger array in queue order, starting at head, which keeps enqueue O(1) amortised. A linked list with pointers to both ends also works, at one allocation per item.

The code

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

// A fixed-capacity FIFO queue on a circular buffer.
class CircularQueue {
    vector<int> slots;
    int capacity;
    int head = 0;  // index of the front element
    int size = 0;  // how many elements are stored
public:
    explicit CircularQueue(int cap) : slots(cap), capacity(cap) {}
    bool isEmpty() const { return size == 0; }
    bool isFull() const { return size == capacity; }

    bool enqueue(int x) {
        if (isFull()) return false;
        slots[(head + size) % capacity] = x;  // first free slot, wrapping past the end
        size++;
        return true;
    }
    int dequeue() {  // the caller checks isEmpty() first
        int x = slots[head];
        head = (head + 1) % capacity;  // the front moves on; nothing is shifted
        size--;
        return x;
    }
    void print() const {
        cout << "slots:";
        for (int x : slots) cout << " " << x;
        cout << " (head at index " << head << ")\nqueue:";
        for (int i = 0; i < size; i++) cout << " " << slots[(head + i) % capacity];
        cout << "\n";
    }
};

int main() {
    CircularQueue q(3);
    for (int x : {1, 2, 3, 4}) cout << "enqueue " << x << ": " << (q.enqueue(x) ? "ok" : "full") << "\n";
    cout << "dequeue: " << q.dequeue() << "\n";
    cout << "enqueue 4: " << (q.enqueue(4) ? "ok" : "full") << "\n";
    q.print();
    while (!q.isEmpty()) cout << "dequeue: " << q.dequeue() << "\n";
    return 0;
}

public class Main {
    // A fixed-capacity FIFO queue on a circular buffer.
    static class CircularQueue {
        private final int[] slots;
        private final int capacity;
        private int head = 0;  // index of the front element
        private int size = 0;  // how many elements are stored

        CircularQueue(int cap) { slots = new int[cap]; capacity = cap; }
        boolean isEmpty() { return size == 0; }
        boolean isFull() { return size == capacity; }

        boolean enqueue(int x) {
            if (isFull()) return false;
            slots[(head + size) % capacity] = x;  // first free slot, wrapping past the end
            size++;
            return true;
        }
        int dequeue() {  // the caller checks isEmpty() first
            int x = slots[head];
            head = (head + 1) % capacity;  // the front moves on; nothing is shifted
            size--;
            return x;
        }
        void print() {
            StringBuilder line = new StringBuilder("slots:");
            for (int x : slots) line.append(" ").append(x);
            line.append(" (head at index ").append(head).append(")\nqueue:");
            for (int i = 0; i < size; i++) line.append(" ").append(slots[(head + i) % capacity]);
            System.out.println(line);
        }
    }

    public static void main(String[] args) {
        CircularQueue q = new CircularQueue(3);
        for (int x : new int[] {1, 2, 3, 4}) System.out.println("enqueue " + x + ": " + (q.enqueue(x) ? "ok" : "full"));
        System.out.println("dequeue: " + q.dequeue());
        System.out.println("enqueue 4: " + (q.enqueue(4) ? "ok" : "full"));
        q.print();
        while (!q.isEmpty()) System.out.println("dequeue: " + q.dequeue());
    }
}

class CircularQueue:
    """A fixed-capacity FIFO queue on a circular buffer."""

    def __init__(self, capacity):
        self.slots = [0] * capacity
        self.capacity = capacity
        self.head = 0  # index of the front element
        self.size = 0  # how many elements are stored

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

    def is_full(self):
        return self.size == self.capacity

    def enqueue(self, x):
        if self.is_full():
            return False
        self.slots[(self.head + self.size) % self.capacity] = x  # first free slot, wrapping
        self.size += 1
        return True

    def dequeue(self):  # the caller checks is_empty() first
        x = self.slots[self.head]
        self.head = (self.head + 1) % self.capacity  # the front moves on; nothing is shifted
        self.size -= 1
        return x

    def print(self):
        print("slots:", *self.slots, f"(head at index {self.head})")
        print("queue:", *(self.slots[(self.head + i) % self.capacity] for i in range(self.size)))


q = CircularQueue(3)
for x in [1, 2, 3, 4]:
    print(f"enqueue {x}: {'ok' if q.enqueue(x) else 'full'}")
print("dequeue:", q.dequeue())
print(f"enqueue 4: {'ok' if q.enqueue(4) else 'full'}")
q.print()
while not q.is_empty():
    print("dequeue:", q.dequeue())

// A fixed-capacity FIFO queue on a circular buffer.
class CircularQueue {
  constructor(capacity) {
    this.slots = new Array(capacity).fill(0);
    this.capacity = capacity;
    this.head = 0; // index of the front element
    this.size = 0; // how many elements are stored
  }
  isEmpty() {
    return this.size === 0;
  }
  isFull() {
    return this.size === this.capacity;
  }
  enqueue(x) {
    if (this.isFull()) return false;
    this.slots[(this.head + this.size) % this.capacity] = x; // first free slot, wrapping
    this.size++;
    return true;
  }
  dequeue() {
    // the caller checks isEmpty() first
    const x = this.slots[this.head];
    this.head = (this.head + 1) % this.capacity; // the front moves on; nothing is shifted
    this.size--;
    return x;
  }
  print() {
    console.log(`slots: ${this.slots.join(" ")} (head at index ${this.head})`);
    const order = [];
    for (let i = 0; i < this.size; i++) order.push(this.slots[(this.head + i) % this.capacity]);
    console.log(`queue: ${order.join(" ")}`);
  }
}

const q = new CircularQueue(3);
for (const x of [1, 2, 3, 4]) console.log(`enqueue ${x}: ${q.enqueue(x) ? "ok" : "full"}`);
console.log(`dequeue: ${q.dequeue()}`);
console.log(`enqueue 4: ${q.enqueue(4) ? "ok" : "full"}`);
q.print();
while (!q.isEmpty()) console.log(`dequeue: ${q.dequeue()}`);

enqueue 1: ok
enqueue 2: ok
enqueue 3: ok
enqueue 4: full
dequeue: 1
enqueue 4: ok
slots: 4 2 3 (head at index 1)
queue: 2 3 4
dequeue: 2
dequeue: 3
dequeue: 4

The operations and their cost

The last column is the trap: everything looks fine except the one operation a queue does all the time.

Deques: both ends at once

A deque (double-ended queue, pronounced "deck") adds and removes at both the front and the back in O(1). A circular buffer gives you one almost for free: adding at the front steps head back one place.

1. A deque is the same ring with work at both ends. It keeps head and size like the queue; the back is (head + size − 1) mod 6.
2. push_back 1 is an ordinary enqueue: write slot 0, add one to size.
3. push_back 2 is an ordinary enqueue: write slot 1, add one to size.
4. push_front 0 steps head back one place. From 0 that would be −1, and % keeps the sign in C++, Java and JavaScript, so add the capacity first: (0 − 1 + 6) % 6 = 5. The front wraps to the far end.
5. push_front 9: head steps back again, to (5 − 1 + 6) % 6 = 4, and 9 becomes the new front.
6. pop_back returns 2 from slot 1 and only takes one from size: the back is computed from head and size, so nothing else changes.
7. pop_front returns 9 and moves head on, wrapping from 4 to 5. All four operations are O(1), so a deque is a stack and a queue at once.

Because it works at both ends, a deque is a stack and a queue at once, and some problems need exactly that:

• Sliding window maximum: the monotonic deque of the Monotonic Stack lesson solves Sliding Window Maximum in O(n) — see also Sliding Window.
• 0-1 BFS: on edges weighing 0 or 1, push a node reached by a 0-edge to the front and by a 1-edge to the back, and nodes come out in order of distance without a heap.

Queues and deques in each language

In C++, read front() before pop(), and check empty() first. In Java, prefer ArrayDeque; PriorityQueue is not FIFO at all but a heap. In Python, deque makes both ends O(1), while queue.Queue is a locked queue for threads, not for algorithms. JavaScript has no queue type, and shift() is O(n), so keep a head index:

let queue = [];
let head = 0;
queue.push(x);                   // enqueue at the back
const front = queue[head++];     // dequeue: read and move the front on, nothing shifts
const size = queue.length - head;

A queue from two stacks

A favourite interview question builds a FIFO queue from LIFO stacks. One stack reverses order; two reversals restore it. An inbox receives every new item and an outbox serves dequeues, refilled from the inbox only when it is empty.

1. enqueue 1, 2, 3: each is pushed onto the inbox, so the newest, 3, is on top — the wrong end for a queue, which must serve 1 first.
2. dequeue finds the outbox empty, so it pops every item off the inbox and pushes it onto the outbox: 3 moves. Reversing the pile puts the oldest item, 1, on top.
3. Now the outbox pops 1, the first item enqueued: two reversals make first in, first out.
4. enqueue 4, 5 onto the inbox. The outbox still holds older items, and they must leave first, so it is left alone.
5. The outbox is not empty, so 2 is popped straight off it with no moves, even though 4 and 5 wait in the inbox. Refilling only when the outbox is empty is what stops newer items jumping the line.
6. 3 comes straight off the outbox too: 3 items out, in arrival order, for 3 moves so far.
7. dequeue finds the outbox empty, so it pops every item off the inbox and pushes it onto the outbox: 2 moves. Reversing the pile puts the oldest item, 4, on top.
8. 4 comes straight off the outbox too: 4 items out, in arrival order, for 5 moves so far.
9. 5 leaves and both stacks are empty: 5 items out in the order they went in, and 5 moves in all. Each item is pushed and popped at most twice, so any n operations cost O(n): O(1) amortised each.

The refill rule is what keeps the order right: pouring new items on top of older ones still in the outbox would let the newcomers jump the line. And although one dequeue can move k items, follow a single item instead: it is pushed and popped once on each stack and never moved back. Four O(1) steps per item, so n operations cost O(n) in total — O(1) amortised each.

The code

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

// FIFO from two LIFO stacks: new items go into inbox; outbox holds the oldest on top.
class TwoStackQueue {
    stack<int> inbox, outbox;
    void refill() {
        if (!outbox.empty()) return;  // refill only when empty, or newer items jump the line
        while (!inbox.empty()) {
            outbox.push(inbox.top());  // reversing the inbox puts its oldest item on top
            inbox.pop();
            moves++;
        }
    }
public:
    int moves = 0;  // items moved from inbox to outbox, to show each moves once
    void enqueue(int x) { inbox.push(x); }
    int dequeue() {
        refill();
        int x = outbox.top();
        outbox.pop();
        return x;
    }
    bool isEmpty() const { return inbox.empty() && outbox.empty(); }
};

int main() {
    TwoStackQueue q;
    for (int x : {1, 2, 3}) q.enqueue(x);
    cout << "dequeue: " << q.dequeue() << "\n";
    for (int x : {4, 5}) q.enqueue(x);
    while (!q.isEmpty()) cout << "dequeue: " << q.dequeue() << "\n";
    cout << "items moved from inbox to outbox: " << q.moves << "\n";
    return 0;
}

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

public class Main {
    // FIFO from two LIFO stacks: new items go into inbox; outbox holds the oldest on top.
    static class TwoStackQueue {
        private final Deque<Integer> inbox = new ArrayDeque<>();
        private final Deque<Integer> outbox = new ArrayDeque<>();
        int moves = 0;  // items moved from inbox to outbox, to show each moves once

        private void refill() {
            if (!outbox.isEmpty()) return;  // refill only when empty, or newer items jump the line
            while (!inbox.isEmpty()) {
                outbox.push(inbox.pop());  // reversing the inbox puts its oldest item on top
                moves++;
            }
        }
        void enqueue(int x) { inbox.push(x); }
        int dequeue() {
            refill();
            return outbox.pop();
        }
        boolean isEmpty() { return inbox.isEmpty() && outbox.isEmpty(); }
    }

    public static void main(String[] args) {
        TwoStackQueue q = new TwoStackQueue();
        for (int x : new int[] {1, 2, 3}) q.enqueue(x);
        System.out.println("dequeue: " + q.dequeue());
        for (int x : new int[] {4, 5}) q.enqueue(x);
        while (!q.isEmpty()) System.out.println("dequeue: " + q.dequeue());
        System.out.println("items moved from inbox to outbox: " + q.moves);
    }
}

class TwoStackQueue:
    """FIFO from two LIFO stacks: new items go into inbox; outbox holds the oldest on top."""

    def __init__(self):
        self.inbox = []
        self.outbox = []
        self.moves = 0  # items moved from inbox to outbox, to show each moves once

    def _refill(self):
        if self.outbox:
            return  # refill only when empty, or newer items jump the line
        while self.inbox:
            self.outbox.append(self.inbox.pop())  # reversing the inbox puts its oldest on top
            self.moves += 1

    def enqueue(self, x):
        self.inbox.append(x)

    def dequeue(self):
        self._refill()
        return self.outbox.pop()

    def is_empty(self):
        return not self.inbox and not self.outbox


q = TwoStackQueue()
for x in [1, 2, 3]:
    q.enqueue(x)
print("dequeue:", q.dequeue())
for x in [4, 5]:
    q.enqueue(x)
while not q.is_empty():
    print("dequeue:", q.dequeue())
print("items moved from inbox to outbox:", q.moves)

// FIFO from two LIFO stacks: new items go into inbox; outbox holds the oldest on top.
class TwoStackQueue {
  constructor() {
    this.inbox = [];
    this.outbox = [];
    this.moves = 0; // items moved from inbox to outbox, to show each moves once
  }
  refill() {
    if (this.outbox.length > 0) return; // refill only when empty, or newer items jump the line
    while (this.inbox.length > 0) {
      this.outbox.push(this.inbox.pop()); // reversing the inbox puts its oldest item on top
      this.moves++;
    }
  }
  enqueue(x) {
    this.inbox.push(x);
  }
  dequeue() {
    this.refill();
    return this.outbox.pop();
  }
  isEmpty() {
    return this.inbox.length === 0 && this.outbox.length === 0;
  }
}

const q = new TwoStackQueue();
for (const x of [1, 2, 3]) q.enqueue(x);
console.log(`dequeue: ${q.dequeue()}`);
for (const x of [4, 5]) q.enqueue(x);
while (!q.isEmpty()) console.log(`dequeue: ${q.dequeue()}`);
console.log(`items moved from inbox to outbox: ${q.moves}`);

dequeue: 1
dequeue: 2
dequeue: 3
dequeue: 4
dequeue: 5
items moved from inbox to outbox: 5

The reverse question, a stack from queues, also has an answer — after each push, rotate the queue so the new item is at the front — but it makes one of the operations O(n).

Where queues appear

• Breadth-first search: nodes are processed in the order they were discovered, so every node at distance d comes before any at d + 1. That is why BFS finds shortest paths in unweighted graphs — see Breadth-First Search.
• Scheduling: round robin, a printer's job list, requests waiting for a worker.
• Streams and buffers: data arriving faster than it is used waits in a queue; "calls in the last 3,000 milliseconds" is a queue of timestamps that expire from the front.
• Simulations: when the statement says "goes to the back of the line", simulate it with a queue.

Time and space complexity

How to recognise a queue problem

• The statement describes a line: "goes to the back", "the person at the front", "in the order they arrived".
• Things happen in rounds or turns, and whoever acted rejoins at the end.
• You need the fewest steps in an unweighted grid or graph: BFS.
• Data arrives as a stream, and old items expire.
• You need the maximum or minimum of a moving window: a deque.

Common mistakes

• Dequeuing with list.pop(0) or array.shift(): O(n) each, O(n²) in all.
• Telling full from empty with only head and tail: keep a count.
• A negative index when stepping back: (head - 1) % capacity is −1 in C++, Java and JavaScript; add the capacity first.
• Refilling the outbox too early in the two-stack queue.
• Mistaking a priority queue for a queue: it hands out the smallest item, not the oldest.

Practice in this order

1. Time Needed to Buy Tickets: round robin at a ticket counter.
2. Number of Students Unable to Eat Lunch: a queue against a stack.
3. First Unique Character in a String: candidates in arrival order.
4. Find the Winner of the Circular Game: a circle as a queue.
5. Reveal Cards In Increasing Order: replay the reveal on a queue of positions.
6. Dota2 Senate: two queues of turn numbers.
7. Number of People Aware of a Secret: people leave the front when they forget.

The queue problem list has every queue problem in the catalogue. Next in this stage is the monotonic stack, which also introduces the monotonic deque.