Queues, Deques, and Circular Buffers

FIFO queues, double-ended queues and circular buffers — how to implement them with a fixed array, and where they appear: BFS, scheduling, sliding windows and producer–consumer pipelines.

What you will learn

FIFO queues, double-ended queues and circular buffers — how to implement them with a fixed array, and where they appear: BFS, scheduling, sliding windows and producer–consumer pipelines.

Prerequisites: Modules 5 and 8.

Concepts

FIFO, enqueue/dequeue, front/rear, circular-array implementation, deque, monotonic queue, priority queue distinction, bounded buffers, producer-consumer pattern.

A queue serves elements in arrival order; a priority queue (Module 14) serves the highest-priority element regardless of arrival order — the names are similar but the structures are not.

Syntax

queue<int> q;
q.push(5);
q.push(8);
int first = q.front();
q.pop();

deque<int> dq;
dq.push_front(3);
dq.push_back(9);

Applications and advanced patterns

BFS, level-order traversal, task scheduling, sliding-window maximum/minimum, 0–1 BFS, round-robin scheduling, and streaming data.

Circular queue

Teach head, tail, capacity, count or one-empty-slot strategy, modulo wraparound, full/empty distinction, and edge cases when capacity is one.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

With head == tail meaning both “empty” and “full” in a pure two-index design, you must either keep a count (as here) or leave one slot permanently empty. The capacity-one case is where off-by-one versions of the second strategy break.

Sliding-window maximum with a monotonic deque An element smaller than a newer element can never again be a window maximum, so it is discarded; each index enters and leaves the deque once, O(n) total.

#include <bits/stdc++.h>
using namespace std;

class CircularQueue {
    vector<int> buf;
    size_t head = 0, count = 0;            // count distinguishes full from empty
public:
    explicit CircularQueue(size_t capacity) : buf(capacity) {}
    bool push(int x) {
        if (count == buf.size()) return false;            // full
        buf[(head + count) % buf.size()] = x;
        ++count;
        return true;
    }
    bool pop(int& out) {
        if (count == 0) return false;                     // empty
        out = buf[head];
        head = (head + 1) % buf.size();
        --count;
        return true;
    }
    size_t size() const { return count; }
    size_t tailIndex() const { return (head + count) % buf.size(); }
    size_t headIndex() const { return head; }
};

int main() {
    CircularQueue q(3);
    int x;
    auto state = [&](const string& op) { cout << setw(10) << left << op << " head=" << q.headIndex() << " tail=" << q.tailIndex() << " size=" << q.size() << '\n'; };
    q.push(1); state("push 1");
    q.push(2); state("push 2");
    q.push(3); state("push 3");
    cout << "push 4 accepted? " << boolalpha << q.push(4) << " (full)\n";
    q.pop(x); state("pop -> " + 
…

push 1     head=0 tail=1 size=1
push 2     head=0 tail=2 size=2
push 3     head=0 tail=0 size=3
push 4 accepted? false (full)
pop -> 1   head=1 tail=0 size=2
push 4     head=1 tail=1 size=3
popped 2
popped 3
popped 4
pop on empty accepted? false
capacity 1: push=true push=false pop=true value=9

#include <bits/stdc++.h>
using namespace std;

vector<int> windowMax(const vector<int>& a, int k) {
    deque<int> dq;                                   // indices; values decreasing front to back
    vector<int> out;
    for (int i = 0; i < (int)a.size(); ++i) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();     // left the window
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();     // can never be a maximum again
        dq.push_back(i);
        if (i >= k - 1) out.push_back(a[dq.front()]);
    }
    return out;
}

int main() {
    vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
    for (int x : windowMax(a, 3)) cout << x << ' ';
    cout << '\n';
}

3 3 5 5 6 7

Practice

Easy: implement a queue using two stacks with amortized O(1) operations.

Medium: generate binary numbers 1..n in order using a queue.

Hard: shortest subarray with sum at least K when values can be negative (prefix sums + monotonic deque).

Quiz

? In a circular queue with only `head` and `tail` indices, why is `head == tail` ambiguous?
+ It can mean empty or full. :: Keep a count or leave one slot empty.
- It means the buffer overflowed. :: No.
- It never happens. :: It happens after equal numbers of pushes and pops.
- It means capacity is one. :: Not necessarily.

? In the sliding-window maximum, why pop smaller elements from the back?
+ A smaller, older element can never be a window maximum while a larger, newer one is in the window. :: It is dominated.
- To keep the deque sorted ascending. :: It is kept decreasing.
- To save memory only. :: Correctness and O(n) time.
- Because the window moved. :: Front pops handle window movement.

? Which tasks use a FIFO queue? (select all that apply)
+ Breadth-first search :: Visits vertices in order of distance.
+ Round-robin scheduling :: Each task gets a turn in order.
- Always serving the most urgent job first :: That is a priority queue.
+ Buffering stream data between producer and consumer :: A bounded buffer.