Queue

A queue keeps items like a line at a shop: newcomers join at the back, and the person at the front is served first, so the oldest item leaves first. Each operation takes $O (1)$ time. If the newest item must leave first, use a stack; if the smallest, use a priority queue.

Use it when items keep arriving while earlier ones are being handled, and they must be handled in the order they came. If all the items are known before the first one is handled, a loop over an array does the job.

How it works

As in the line at a shop, the item served next is at the front, and newcomers join at the back. Adding an item is called push and removing one is called pop (some problems say enqueue and dequeue). This order is called first in, first out.

Operation	What it does	Time
`push(x)`	adds `x` at the back	$O (1)$
`front()`	the item at the front	$O (1)$
`pop()`	removes the item at the front	$O (1)$
`empty()`, `size()`	is it empty, how many items	$O (1)$

The obvious way to keep a queue in an array is with the front in cell 0. But then every pop has to move all the other items one cell to the left.

An array of cells 0 to 4 holding 5 8 2 6 1, with the 5 in cell 0 red; beside it, the array after the pop holds 8 2 6 1 in cells 0 to 3, all four red because each moved one cell left, and cell 4 is empty.

Fig. 1. One pop, four moves: every item still in the queue moves.

The items don't need to move at all. Leave each item in its cell and keep two indices. head is the cell of the front item. tail is the first free cell, right after the back item. The queue is the cells from head to tail - 1.

push writes x into cell tail and adds 1 to tail;
front reads cell head;
pop adds 1 to head;
the queue is empty when head == tail, and its size is tail - head.

Each of these touches one cell, so each takes $O (1)$ time.

Let's run a few commands on an empty queue to see how it works.

A queue in an array of 7 cells with head and tail, step 1.

The queue is empty: head and tail are both 0.

1/12

Fig. 2. The 11 commands on an array of 7 cells. A pushed item joins at tail; a popped item leaves from head, to the left.

The queue never held more than 5 items, but tail reached 7. Cells before head are not used again, so the array needs one cell for every push.

In C++

In contests you rarely write the queue yourself. The C++ queue is in the header <queue>, and queue<int> q; declares an empty queue of integers, as in vector<int>. It has the operations from the table, plus back(), which gives the item at the back, and it grows as items are pushed: there is no size to set.

The program below reads the number of commands n ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5), then n lines, each push x ( $∣ x ∣ \leq 1 0^{9}$ |x| \le 10^9), pop, front or size. pop and front come only when the queue is not empty. For pop it prints the removed item, for front the item at the front, for size the number of items. The commands in Fig. 2 are this input:

11
push 5
push 8
push 2
push 6
push 1
pop
push 4
pop
push 7
front
size

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    queue<int> q;

    for (int i = 0; i < n; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int x;
            cin >> x;
            q.push(x);
        } else if (cmd == "pop") {
            cout << q.front() << '\n';   // read the front first
            q.pop();                     // pop returns nothing
        } else if (cmd == "front") {
            cout << q.front() << '\n';
        } else if (cmd == "size") {
            cout << q.size() << '\n';
        }
    }
}

Examples of use

Breadth-first search keeps the cities it has found in a queue and handles them in the order they were found, so every city one road from the start is handled before any city two roads away. Topological sort by Kahn's method keeps the tasks that can start now in a queue.

A sliding window over a sequence is a queue: new numbers enter it at the back and old ones leave from the front, and each number is pushed and popped at most once.

Common mistakes

Removing the front item with v.erase(v.begin()), which moves every remaining item like the array in Fig. 1. Use std::queue.
Making the two-index array only as long as the most items held at once, so tail runs past its end and nothing reports it. Give the array one cell per push.

Similar structures

A stack is the opposite order: items are added and removed at the same end, so the newest item leaves first.

A priority queue gives the smallest item first, whatever order the items came in.

A deque is open at both ends: items can be pushed and popped at the front and at the back, all in $O (1)$ . A monotonic queue keeps the minimum of a sliding window in a deque. 0-1 BFS uses a deque in place of the queue of breadth-first search.