Deque: work at either end
Keep recent arrivals and make front/back updates without repeated vector shifts.
A double-ended sequence
std::deque supports push_front, push_back, pop_front, pop_back, front, back, indexed access, and iteration. End access and removal require a nonempty deque. Single-element end operations and indexed access have constant-time guarantees in the source’s container model; middle edits can be linear.
A deque’s front is not necessarily its minimum, and its back is not necessarily its maximum. Their meanings follow your operations. Start with 5 8, push_front(3), push_back(1), then pop_front(): the remaining order is 5 8 1.
Different storage, different validity rules
Unlike an ordinary vector, deque does not promise one contiguous element block. It has no vector-style reserve() or capacity(). Its random-access iterators can support algorithms such as sort when the algorithm’s other requirements hold.
Inserting at an end invalidates deque iterators but preserves references to existing elements. Middle edits have stronger effects. For beginner simulations, retrieve the current end when needed and copy a value before removing it. An item can retain a valid reference while its logical index changes after a front insertion.
// Complete C++23 program. No input; output: 10 40, then 20 99.
#include <deque>
#include <iostream>
int main() {
std::deque<int> line{20, 30};
line.push_front(10);
line.push_back(40);
std::cout << line.front() << ' ' << line.back() << '\n';
line.pop_front();
line.pop_back();
line[1] = 99;
std::cout << line[0] << ' ' << line[1] << '\n';
}Maintain the latest k arrivals
Store the oldest retained value at the front and the newest at the back. Append each arrival. If the size exceeds k, remove one front value. Before the append the size was at most k, so one removal restores that bound.
After i arrivals, the invariant is that the deque contains the last min(i, k) values in arrival order. For k = 0, the append creates an element before the removal, so no empty pop occurs. The n appends and at most n removals take O(n + 1) total time and O(min(n, k) + 1) logical storage.
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.
In the recent-history algorithm with k = 0, is the removal after each append invalid?
Turn the idea into code
Read n, k, and n integers with 0 ≤ n, k ≤ 200000. Retain only the latest k arrivals without saving the full input elsewhere. Print them oldest retained first. Handle k = 0 and k > n.
Give me a hint
Append at the back. If size is greater than k, discard the front.
Show the explained solution
The deque always represents the desired suffix of processed arrivals. If k exceeds n, nothing is discarded. If k is zero, all arrivals are immediately discarded and the output line is blank.
// Complete C++23 program. Input: n k, then n integers.
#include <deque>
#include <iostream>
int main() {
int n = 0, k = 0;
std::cin >> n >> k;
std::deque<int> recent;
for (int i = 0; i < n; ++i) {
int x = 0;
std::cin >> x;
recent.push_back(x);
if (static_cast<int>(recent.size()) > k) recent.pop_front();
}
for (int i = 0; i < static_cast<int>(recent.size()); ++i) {
if (i != 0) std::cout << ' ';
std::cout << recent[i];
}
std::cout << '\n';
}Your notes
Mark complete when you can explain it yourself.