std::deque supports efficient push/pop at both ends—O(1). Used as underlying container for queues and in sliding-window maximum problems (with monotonic deque).
deque vs vector
- vector — fast end append, slow front erase
- deque — O(1) push/pop front and back
- Not contiguous as single block—still reasonable iteration
BFS-style queue
#include
#include
int main() {
std::deque q;
q.push_back(1);
q.push_back(2);
q.push_front(0);
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop_front();
}
std::cout << "\n";
return 0;
} Monotonic deque preview
Maintain decreasing values for sliding window max—each element enters and leaves once → O(n).
Important interview questions and answers
- Q: Why BFS uses queue not stack?
A: BFS explores layer by layer—FIFO order. - Q: deque for window max?
A: Pop from back while smaller than new element; pop front when index out of window.
Self-check
- What is O(1) operation on deque ends?
- Why not use vector for queue front pops?
Tip: BFS queues should pop from front—use deque not vector for O(1) pops.
Interview prep
- deque advantage?
O(1) push/pop both ends.
- BFS queue?
deque or queue adapter—not vector front erase.