ADTdeque and the STL deque Container Class
The word "deque" is pronounced either as "deck" or as DQ (kind of like Dairy Queen). It is short for "double-ended queue", and conceptually may be informally thought of as a line-up that permits entry and exit at both ends. The deque may also be viewed as a generalization of both a stack and a queue.
From an STL point of view, however, the deque seems closer to the vector than to either the queue or the stack. Note that, among other similarities, the deque has analogues to each of the five constructors possessed by the vector class. In fact, the member functions of the vector and the deque are essentially the same, except that deque has push_front() and pop_front() member functions (while vector doesn't) and vector has capacity() and reserve() functions (while deque doesn't).
| deque Operations | |
|---|---|
| Generic (ADT) | Specific (STL) |
| Construct a deque |
deque<T> d; deque<T> d(num); deque<T> d(num, someValueOfTypeT); deque<T> d(otherDeque); deque<T> d(inputIter1, inputIter2); |
| Test for emptiness | empty() |
| Add one or more values | |
| Add value to back | push_back(val) |
| Add value to front | push_front(val) |
| Insert values |
insert(iter, val) insert(iter, num, val) insert(iter, startIter, endIter) |
| Assign values |
assign(startIter, endIter) assign(num, val) |
| Remove one or more values | |
| Remove all values | clear() |
| Remove value pointed to | erase(iter) |
| Remove a range of values | erase(startIter, endIter) |
| Remove value from back | pop_back() |
| Remove value from front | pop_front() |
| Retrieve a value (without removing it) | |
| Get value at front | front() |
| Get value at back | back() |
| Get value at index location (read or write) |
at(index) operator[ ] (i.e., d[index]) |
| Retrieve size | |
| Get current size | size() |
| Get maximum size | max_size() |
| Miscellaneous operations affecting the entire container | |
| Change size |
resize(num) resize(num, val) |
| Exchange contents of self with another deque | swap(otherDeque) |
If you look up "deque" in most any textbook on data structures, you will probably find a much more limited interface than that given above. For example, you might encounter an interface that would allow you to construct a deque in one or more ways, test for emptiness, add an element to and remove an element from the front or back of the deque, get the value at the front or back without removing it, and not much more. So, the STL deque has a "richer" interface than many.
The deque<T>::iterator and deque<T>::reverse_iterator iterators are random access iterators, the most powerful kind of STL iterator and the same kind of iterator provided by the vector container class. The member function begin() returns an iterator pointing at the first element of the deque, while end() is a member function returning an iterator pointing at the position "one past the end" of the deque. Analogously, the "reverse iterators" rbegin() and rend() return iterators pointing at the last and "one before the first" positions, respectively.
Deques tend to be useful in situations where order of components, compact storage, and fast insertions and deletions at the ends are important. They can be used to implement any FIFO (First In First Out) structure, though a queue should be used if there must be strict FIFO behavior with no direct access by numeric index permitted. If fast insertions near the middle need to be made, a list is the better choice.
The deque is one of the three "sequential" container classes in the STL (the vector and the list are the other two). Usually, if you're wondering about using a deque, the choice will be between using a deque or using a vector, since they have so much in common. Element access tends to be a bit faster in vectors, though both vectors and deques offer constant-time access to elements (from a big-Oh perspective). If there are to be many insertions and deletions at the ends, and particularly at the front, the deque would be a better choice. In general, though, when an array-like object which can grow and shrink dynamically is needed, the vector tends to be the container of choice.