deque
A deque (pronounced "deck", short for double-ended queue) is a line you can join or leave from either end. You can push and pop at both the front and the back, all in O(1). That makes it a superset of both a stack and a queue: ignore one end and it behaves like a stack; push at one end and pop at the other and it behaves like a queue.
Under the hood it is usually a circular buffer or a list of fixed-size chunks, so growing at either end stays cheap and there is no big shifting. C++ std::deque also supports O(1) indexed access like a vector, though inserting in the middle is still O(n). Compared with a vector it gives you a cheap front, which a plain dynamic array lacks.
Deques shine when you need to add and remove from both ends. The classic example is the sliding-window-maximum trick, where a deque keeps candidate indices in order and discards stale ones from the front while pushing new ones at the back — turning a naive O(n*k) scan into O(n).
#include <deque> std::deque<int> dq; dq.push_back(2); // [2] dq.push_front(1); // [1, 2] O(1) at the front dq.push_back(3); // [1, 2, 3] // front <- [ 1 | 2 | 3 ] -> back dq.pop_front(); // [2, 3] O(1) int b = dq.back(); // 3 O(1)
Both ends are O(1); it can act as a stack or a queue.
A deque generalizes both stack and queue, so many libraries implement std::queue and std::stack on top of a deque.