c++ deque vs queue vs stack
Solution 1:
Moron/Aryabhatta is correct, but a little more detail may be helpful.
Queue and stack are higher level containers than deque, vector, or list. By this, I mean that you can build a queue or stack out of the lower level containers.
For example:
std::stack<int, std::deque<int> > s;
std::queue<double, std::list<double> > q;
Will build a stack of ints using a deque as the underlying container and a queue of doubles using a list as the underlying container.
You can think of s
as a restricted deque and q
as a restricted list.
All that is necessary is that the lower level container implements the methods needed by the higher level container. These are back()
, push_back()
, and pop_back()
for stack and front()
, back()
, push_back()
, and pop_front()
for queue.
See stack and queue for more detail.
With respect to the deque, it is much more than a queue where you can insert at both ends. In particular, it has the random access operator[]
. This makes it more like a vector, but a vector where you can insert and delete at the beginning with push_front()
and pop_front()
.
See deque for detail.
Solution 2:
Queue
: you can insert only in one end and remove from the other.
Deque
: you can insert and remove from both ends.
So using a Deque
, you can model a Queue
as well as a Stack
.
Hint:Deque
is short for "Double ended queue".
Solution 3:
deque
is a container template. It satisfies the requirements for a sequence with random-access iterators, much like a vector
.
queue
is not a container at all, it is an adaptor. It contains a container and provides a different, more specific interface. Use queue
when you want to remember (or remind) to avoid operations besides push[_back]
and pop[_front]
, front
and back
, size
and empty
. You can't look at elements inside the queue
besides the first and last, at all!