A line at the bank
A queue is just an orderly line. New people join at the back; the teller serves from the front. The first person in is the first person out — First In, First Out, or FIFO. It's the natural choice whenever fairness or arrival-order matters.
The two core operations have their own names: enqueue to add at the back, and dequeue to remove from the front. Both are O(1) — adding to one end and removing from the other never requires shifting anyone.
dequeue <- [ 1 | 2 | 3 ] <- enqueue
front back
enqueue 4: [ 1 | 2 | 3 | 4 ]
dequeue : returns 1 -> [ 2 | 3 | 4 ]std::queue in C++
The standard library gives you `std::queue`. The vocabulary differs a little from a stack: you `push` (enqueue) at the back, read `front()`, and `pop()` from the front.
#include <queue> #include <iostream> std::queue<int> q; q.push(1); // enqueue q.push(2); q.push(3); std::cout << q.front(); // 1 (the FIRST one in) q.pop(); // dequeue -> removes 1 std::cout << q.front(); // 2
The circular buffer idea
Building a queue on a plain array hits a snag: if you keep removing from the front by shifting everything left, each dequeue costs O(n). The clever fix is a circular buffer — keep two indices, `head` and `tail`, and let them wrap around the end of a fixed array back to the start. Nothing ever shifts.
capacity 5, head=front, tail=next free slot:
index: 0 1 2 3 4
[ . | 2 | 3 | 4 | . ]
^head ^tail
enqueue 5 -> tail goes to 4; enqueue 6 -> tail WRAPS to 0
[ 6 | 2 | 3 | 4 | 5 ]
^tail ^head
(use tail = (tail + 1) % capacity to wrap)The key trick is the modulo: `index = (index + 1) % capacity` makes the index jump from the last slot back to slot 0. With that, both enqueue and dequeue stay O(1) and no element is ever moved.
Deques and where queues shine
A deque ("double-ended queue", say "deck") lets you add and remove at both ends — front and back. It's a superset of both a stack and a queue. In C++, `std::deque` gives you `push_front`, `push_back`, `pop_front`, and `pop_back`, all O(1).
#include <deque> std::deque<int> d; d.push_back(2); // [2] d.push_front(1); // [1, 2] d.push_back(3); // [1, 2, 3] d.pop_front(); // [2, 3] removed 1 d.pop_back(); // [2] removed 3
Why care? Task queues process jobs in arrival order. The operating system schedules programs from a queue. And breadth-first search — exploring a graph level by level, which you'll meet in the Trees & Graphs rung — is built entirely on a queue: you enqueue neighbors and dequeue them in the order discovered. A queue is the engine of "deal with things in the order they arrived."