Queue: serve the oldest first
Model FIFO commands, repeated turns, copies, and fresh state between test cases.
The front is the oldest unserved item
std::queue uses FIFO: first in, first out. push(x) adds at the back, front() reads the next item, back() reads the newest item, and pop() removes one front item without returning a value. The default queue uses deque, so these fixed-cost-element operations are O(1).
There is no indexing, begin(), or top() in the queue interface. Check empty() before front(), back(), or pop(). Equal labels still represent separate inserted items; one pop removes one occurrence.
// Complete C++23 program. No input; output: 4 9
#include <iostream>
#include <queue>
int main() {
std::queue<int> waiting;
waiting.push(4);
waiting.push(9);
waiting.push(2);
int next = waiting.front();
waiting.pop();
std::cout << next << ' ' << waiting.front() << '\n';
}Read first; remove second
A value copy of front() stays usable after pop(). A reference to the removed front does not: its element has been destroyed. To visit every queued value through the restricted interface, repeatedly read front and pop, which consumes the queue.
To preserve the original, copy the queue and drain that copy, paying O(n) copy time and extra storage. To drain, use while (!q.empty()). Comparing an increasing i to a shrinking q.size() can stop early; four initial items can leave two behind.
Requeue unfinished jobs
Store (ID, remaining work). On each turn copy the front job, pop it, subtract one unit, then either record completion or push the unfinished job at the back. Positive initial workloads ensure each decrement moves toward completion.
For workloads 2 1 3, completion order is 2 1 3. Let W be the sum of initial workloads: the loop runs exactly W turns, not merely n turns. Time is O(n + W + 1), and at most n jobs are stored.
Fresh objects prevent leaked test state
Place a case’s queue inside solve() to create a new empty state for every call. empty() is only a query and does not reset a queue. The adaptors have no clear() member: drain them, assign a fresh empty object, or use a local lifetime.
Sequential cases add their processing costs but do not keep all local queues alive together. Destruction and copying still do work; a one-line statement is not automatically constant-time.
Container workbench
Insert values, then remove the next accessible item. Priority queue values are shown sorted for explanation, not as an internal heap.
Next removal: 5. Size: 3.
Guided simulation · Change the inputs to test your understanding.
Two queued jobs require 100 and 1 one-unit turns. How many iterations does the repeated-turn loop need?
Turn the idea into code
Implement a service line. Commands: 1 id joins, 2 prints and removes the oldest ID, 3 prints it without removal. Print EMPTY for type 2 or 3 on an empty queue. There are at most 200000 valid commands.
Give me a hint
Handle insertion first, then guard all remaining accesses with empty(). Only type 2 removes.
Show the explained solution
The invariant is that the queue contains exactly the unserved arrivals in their original order. Each command uses O(1) queue operations, so total time is O(q + 1), with O(q + 1) possible stored items.
// Complete C++23 program. Input: q, then commands 1 id, 2, or 3.
#include <iostream>
#include <queue>
int main() {
int q = 0;
std::cin >> q;
std::queue<int> waiting;
while (q--) {
int type = 0;
std::cin >> type;
if (type == 1) {
int id = 0;
std::cin >> id;
waiting.push(id);
} else if (waiting.empty()) {
std::cout << "EMPTY\n";
} else {
std::cout << waiting.front() << '\n';
if (type == 2) waiting.pop();
}
}
}Your notes
Mark complete when you can explain it yourself.