Dfyjkt

I am wondering why does C++ have queue and stack given it already have deque.

It seems that the runtime of the stack/queue and using deque to simulate stack/queue is the same. Also, the deque supports the modifiers like erase, iterators and random access, which neither the stack or queue supports.

So why do C++ provide all three of them given that the deque is much more powerful than the rest of the two?

Thanks!

std::queue and std::stack aren't actually containers in the standard library. They are container adaptors and exist to give you an specific interface on top of an actual container.

You wouldn't want your stack to have an operator so we wrap std::deque (by default, you could use a different container) so we don't expose operations a stack wouldn't have.

std::stack and std::queue are so-called "container adapters", as in they adapt the interface of the wrapped container (a template parameter, defaulted to std::deque, but could be anything that implements back(), push_back() and pop_back() for std::stack, and back(), pop_front() and push_back() for std::queue) to the restricted interface of a stack or a queue; if you prefer, they dumb down the underlying container interface.

The general idea should be that the "restricted" container provides just the operations of the "expected mode of operation" of the container - an std::stack allows only stack-like operations, unlike the underlying std::deque that allows, for example, random insert/access. Another advantage is that compile-time polymorphism over the underlying container type is a little more comfortable than passing the plain container (you may get better error messages).

In practice, I always found these adapters at least useless, more often just hindrances:

• they don't restrict the space of available states, as, given extra space, both an std::stack and std::queue can be mutated in any way;


• they don't provide type erasure over the underlying container type, as it's a template parameter, so they aren't useful to write a non-template function that takes any stack, regardless of the underlying container;


• most often their interface is way too restricted; you cannot even do a debug print of the full content of an std::stack, even if the underlying container fully supported forward iterators (or even random access).

Both, std::stack and std::queue are container adaptors. The use a std::deque as the backing container by default, but thats not necessarily the case.

Both, stack and queue, have a reduced interface compared to a deque. Hence, you might want to have a stack that does not use a std::deque but some other container and this is what the adaptors are for.