C++ default implementation of stack and queue

Question

In C++ Primer 5th, it says that the default implementation of stack and queue is deque.

I'm wondering why they don't use list? Stack and Queue doesn't support random access, always operate on both ends, therefore list should be the most intuitive way to implement them, and deque, which support random access (with constant time) is somehow not necessary.

Could anyone explain the reason behind this implementation?

Answer 1

With std::list as underlying container each std::stack::push does a memory allocation. Whereas std::deque allocates memory in chunks and can reuse its spare capacity to avoid the memory allocation.

With small elements the storage overhead of list nodes can also become significant. E.g. std::list<int> node size is 24 bytes (on a 64-bit system), with only 4 bytes occupied by the element - at least 83% storage overhead.

Answer 2

I think the question should be asked the other way around: Why use a list if you can use an array?

The list is more complicated: More allocations, more resources (for storing pointers) and more work to do (even if it is all in constant time). On the other hand, the main property for preferring lists is also not relevant to stacks and queues: constant-time random insertion and deletion.