Queue and Stack are a structures widely mentioned. However, in C++, for queue you can do it in two ways:
#include <queue>
#include <deque>
but for stack you can only do it like this
#include <stack>
My question is, what's the difference between queue and deque, why two structures proposed? For stack, any other structure could be included?
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.
A deque is a double-ended queue, which allows easy insertion/removal from either end. Queues only allow insertion in one end and retrieval from the other.
deque supports insert/pop from back & front
queue only supports insert to the back, and pop from the front. You know, a FIFO (first in first out).
Moron is correct, but a little more detail may be helpful.
queue and stack are higher level containers. than deque or list or vector. 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.
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!
In the C++ library, both std::stack and std::queue are implemented as container adapters. That means they provide the interface of a stack or a queue respectively, but neither is really a container in itself. Instead, they use some other container (e.g. std::deque or std::list to actually store the data), and the std::stack class just has a tiny bit of code to translate push and pop to push_back and pop_back (and std::queue does roughly the same, but using push_front and pop_back).