1

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!

Major
  • 159
  • 1
  • 7
  • 1
    They're not mutually exclusive. In fact, both `std::stack` and `std::queue` use `std::deque` by default. – chris Nov 09 '18 at 14:12
  • https://stackoverflow.com/questions/2247982/c-deque-vs-queue-vs-stack?rq=1 – Mat Nov 09 '18 at 14:15
  • 1
    Sometimes less is more. It's much easier to understand the role in the program of a **stack** than of a **deque that's being used as if it were a stack**. – Pete Becker Nov 09 '18 at 14:17
  • If stacks and queues supported random access or iteration they wouldn’t be stacks and queues. – molbdnilo Nov 09 '18 at 14:18
  • 1
    A type's "power" is often synonymous with risk of use. More "powerful" features make it harder to detect errors since by definition there are fewer things you aren't allowed to do. A prime example of this is c style casts. They are immensely powerful in what casts they can perform they may replace any of the c++ style casts. But their power also means they are dangerous to use. So despite the fact that they make all other casts redundant, their use is discouraged specifically because it's so powerful. Rather than viewing `queue` and `stack` being "less powerful", look at them as being safer. – François Andrieux Nov 09 '18 at 14:23
  • 2
    @FrançoisAndrieux nicely put, i'd add that using `queue` and `stack` is more expressive. Code is much easier to reason about when a stack is a `stack` and a queue is a `queue` – 463035818_is_not_an_ai Nov 09 '18 at 15:20

3 Answers3

7

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.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
3

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).
Matteo Italia
  • 123,740
  • 17
  • 206
  • 299
  • Your second bullet point is easy to overcome by adding an extra template parameter to the function: http://coliru.stacked-crooked.com/a/79028b2d002e58fe. The other points though are very valid. – NathanOliver Nov 09 '18 at 14:35
  • @NathanOliver: that's exactly the case I mention in my second paragraph, about compile-time polymorphism. But that's not the same as "regular" polymorphism, as it infects everything with templates, and the only advantage it provides over having the function accepting a generic container is that it provides better error messages. – Matteo Italia Nov 09 '18 at 14:37
1

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.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185