Step 3 of 7
deque, the double-ended queue
std::vector is fast at the back but slow at the front: removing element 0 shifts every other element down. std::deque (a "double-ended queue", said "deck") is fast at both ends: push_back, push_front, pop_back and pop_front are all O(1). It still supports d[i] indexing.
#include <deque>
#include <iostream>
#include <string>
int main() {
std::deque<std::string> history;
const std::size_t limit = 3;
for (const char* page : {"home", "news", "sports", "weather", "mail"}) {
history.push_back(page);
if (history.size() > limit) history.pop_front(); // forget the oldest
}
for (const auto& p : history) std::cout << p << " ";
std::cout << "\n";
history.push_front("start");
std::cout << history.front() << " ... " << history.back() << " (" << history.size() << ")\n";
}
sports weather mail
start ... mail (4)
The sliding window pattern
The example keeps only the most recent 3 pages: push the new one at the back, and if that makes it too big, pop the oldest from the front. That's a sliding window, and it's exactly what a moving average needs.
To keep an average cheap, don't add up the whole window every time. Keep a running sum as a member:
- when a value enters,
sum += value, - when a value leaves from the front,
sum -= d.front()beforepop_front().
Then average() is just sum / size, in constant time. Remember to divide as double, and decide what an empty window returns (0 is a safe choice).
std::queue is a restricted wrapper around a deque that only allows the queue operations.
Your task
Write class MovingAverage that remembers only the last n values added and reports their average.
Challenge 2
Write class UndoHistory that keeps at most capacity actions. push(action) adds the newest; when that goes over capacity, the oldest is forgotten. undo() removes and returns the newest action, or "" when there is none. size() returns how many are kept. Use a std::deque.
Challenge 3
Write std::vector<int> window_max(const std::vector<int>& v, int k) that returns the largest value of every window of k neighbours, left to right. Keep a std::deque of indexes whose values are in decreasing order: drop indexes from the back while their value is <= the new one, and drop the front once it slides out of the window. The front is then always the window's maximum.