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 7Practice
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.