ADTqueue and the STL queue Container Adaptor
Like the stack, the queue is a very simple and straightforward abstract data type, but is nevertheless one of the most useful in programming.
The idea of a queue in the context of programming is in fact what we normally think of as a "queue" or "line up" of anything: a queue of people, a queue of print jobs for a particular printer, a queue of planes waiting to take off or land at an airport, and so on. The way we usually use a queue is to put a new item added to the queue at the "end" or the "back" of the queue, and we remove (or access in any other way) the item at the "front" of the queue. As anyone who has tried to "jump" a queue at a bus stop knows, the activity is frowned upon at best, and can even be hazardous to your health.
The queue abstract data type enforces this behavior, which is usually given the acronym FIFO (First In, First Out). The STL queue is not a "first class" container in its own right, like the vector, deque and list, but is instead based on a tightly controlled interface to an underlying deque container class (by default). This is why it is called a container "adaptor".
| queue Operations | |
|---|---|
| Generic (ADT) | Specific (STL) |
| Construct a queue |
queue<T> q;
queue<T> q(otherContainer); |
| Test for emptiness | empty() |
| Add value to back | push(val) |
| Remove front value | pop() |
| Get front value, without removing it | front() |
| Get back value, without removing it | back() |
| Get current size | size() |
The above interface for a queue contains the usual operations you would find if you looked up "queue" in most any textbook on data structures, and these are in fact the operations provided by the STL. However, in some "standard" queue implementations, you may not see the back() member function.
We need to say something about the second constructor. The "otherContainer" that may be used to initialize a queue cannot be just any other container. It must, in fact, be another queue having the same kind of components as the queue being constructed, or another container of the type on which the queue is based (which, by default, is the deque) and also having the same kind of components as the queue being constructed.
The queue container adaptor does not support any iterators.
The queue container adaptor should be used in any situation where components are being added to and removed from the container in FIFO fashion.