In C++, what containers do std::stack and std::queue wrap, and why does their pop() return nothing?
answer
- adaptors, not containers
- deque underneath by default
- which members each one needs
- read first, then remove
basics
~20 sstd::stack and std::queue adapt a sequence container, std::deque by default; a stack can also use vector or list, a queue list but not vector. pop() returns void so that a throwing copy can never lose the removed element.
solid answer
~40 sBoth are class templates with a `Container` parameter that defaults to `std::deque<T>`; they store it as a protected member `c` and expose a restricted interface. `std::stack` needs `back()`, `push_back()` and `pop_back()`, so `std::vector`, `std::list` and `std::deque` all qualify. `std::queue` needs `front()`, `back()`, `push_back()` and `pop_front()`, so `std::deque` and `std::list` qualify and `std::vector`, which has no `pop_front`, does not. Neither adaptor offers iteration or `clear()`. Their `pop()` returns `void`: you read with `top()` or `front()`, then call `pop()`. Returning the removed element by value would have to copy or move it after it left the container, and if that threw, the element would be gone with no way to recover it. Splitting read and remove keeps each step safe. In a print server, a `std::queue<PrintJob>` is the FIFO spool.
code
cpp · 30 lines#include <cstdio>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
struct PrintJob { int id; std::string owner; };
int main() {
std::queue<PrintJob> spool; // std::deque<PrintJob> underneath
spool.push({1, "ana"});
spool.push({2, "bob"});
spool.push({3, "eve"});
while (!spool.empty()) {
PrintJob job = std::move(spool.front()); // read first...
spool.pop(); // ...then remove: pop() returns void
std::printf("printing job %d for %s\n", job.id, job.owner.c_str());
}
std::stack<int, std::vector<int>> undo; // vector is fine: back, push_back, pop_back
undo.push(10);
undo.push(20);
std::printf("undo top=%d size=%zu\n", undo.top(), undo.size());
std::queue<int, std::list<int>> retries; // list is fine: front, back, push_back, pop_front
retries.push(7);
retries.pop();
std::printf("retries empty: %d\n", int(retries.empty()));
}go deeper
Know that std::stack and std::queue are adaptors over std::deque by default, and the read-then-pop pattern because pop() returns void.
Name the members each adaptor needs from its container and which containers qualify; explain why vector works for stack but not for queue.
Explain the exception-safety reason for a void pop(), and switch to the underlying container when the design needs iteration or access to both ends.
Choose whether a FIFO, a double-ended queue or a priority queue models the workload, and keep the type's restrictions as documentation of the intended access pattern.
## Adaptors, not containers `std::stack` (header `<stack>`) and `std::queue` (header `<queue>`) are **container adaptors**: class templates that wrap an existing sequence container and expose only the operations that fit a stack or a queue. The standard declares both as `template<class T, class Container = deque<T>>`, stores the container in a **protected** member named `c`, and defines each operation as one call on it. | Adaptor | Operations it offers | Calls it makes on `c` | |---|---|---| | `std::stack` | `push`, `emplace`, `top`, `pop`, `empty`, `size`, `swap` | `push_back`, `back`, `pop_back` | | `std::queue` | `push`, `emplace`, `front`, `back`, `pop`, `empty`, `size`, `swap` | `push_back`, `front`, `back`, `pop_front` | ## Which underlying containers are allowed - **`std::stack`**: any sequence container with `back()`, `push_back()` and `pop_back()`. The standard names `std::vector`, `std::list` and `std::deque`. A `std::stack<int, std::vector<int>>` is common for undo stacks, since a vector is contiguous and has no per-block overhead. - **`std::queue`**: any sequence container with `front()`, `back()`, `push_back()` and `pop_front()`. The standard names `std::list` and `std::deque`. `std::vector` has no `pop_front`, so it does not qualify. With libc++, `std::queue<int, std::vector<int>>` even compiles until `pop()` is called, because member functions of a class template are instantiated only when used; then it fails with "no member named 'pop_front' in 'std::vector<int>'". - **Why `std::deque` is the default**: it offers constant-time insertion and removal at both ends without reallocating its elements, so it suits both adaptors. ## Why pop() returns void `top()` and `front()` return a reference to the element, and `pop()` removes it and returns nothing. A combined "remove and return" would look like `T pop()`. To return the element by value, it would have to copy or move the element into the return value after removing it from the container. If that copy throws, the element is already gone from the container and never reaches the caller: it is lost. Splitting the operation in two keeps each step safe: 1. `T job = std::move(q.front());` copies or moves the element out; if this throws, the queue is unchanged. 2. `q.pop();` destroys the front element, which does not throw for well-behaved types. The same design runs through the standard containers: `pop_back` and `pop_front` on `std::vector`, `std::deque` and `std::list` also return `void`. For the queue, the non-const `front()` returns a plain `reference`, so moving out of it is allowed, as in step 1 above. `std::stack::top()` likewise has a non-const overload returning `reference`. ## What the adaptors deliberately leave out - **Iteration**: there is no `begin()` or `end()`, so you cannot list a queue's contents. If a print server's dashboard must show pending jobs, use a `std::deque<PrintJob>` directly. - **`clear()`**: assign an empty adaptor instead (`spool = {};`) or pop until `empty()`. - **Access to the middle**: by design, only the ends are reachable. Because `c` is protected, a class derived from the adaptor can reach the container, but if you need that access, using the underlying container directly is usually clearer. ## Common mistakes 1. Calling `top()` or `front()` on an empty adaptor. They forward to the container's `back()` or `front()`, whose precondition is a non-empty container, so the call is undefined behaviour unless a checked library mode catches it. Test `empty()` first. 2. Holding the reference returned by `front()` across `pop()`. After `pop()` it refers to a destroyed element; copy or move the value out first, as in the two-step pattern above. 3. Declaring `std::queue<T, std::vector<T>>` and discovering the error only at the first `pop()`. 4. Expecting `std::stack` to offer iteration for debugging output; it does not, by design. ## The print server example A print server spools jobs in arrival order. `std::queue<PrintJob>` documents that intent in the type: jobs are added with `push` at the back and taken with `front` then `pop` at the front. When urgent jobs must jump the line, the design has outgrown a plain FIFO: either a `std::deque` with `push_front`, or a `std::priority_queue` keyed by urgency.
- Can you use std::vector as the underlying container of std::queue?No. `std::queue` requires `pop_front()`, which `std::vector` does not have, because removing the first element of a vector would shift every other element. With libc++ the declaration compiles until `pop()` is called, since class template members are instantiated only when used, and then fails with "no member named 'pop_front' in 'std::vector<int>'". Use `std::deque` or `std::list`.
- How do you remove every element from a std::queue, given that it has no clear()?Assign an empty queue, `spool = {};`, which replaces the underlying container, or swap with an empty one, `std::queue<PrintJob>().swap(spool);`. Both release the elements at once; popping in a loop until `empty()` also works but is slower and only worth it when each element needs handling on the way out.
- std::queue stores its elements in a std::vector by default
- pop() returns the removed element, so top() is redundant
- std::queue<int, std::vector<int>> is a valid FIFO
- std::stack and std::queue are standalone containers with their own storage
- You can loop over a std::queue with a range-for to inspect pending jobs