C++ Double-ended Queues
Double-ended queues (or deques) are similar to vectors, except that they allow fast insertions and deletions at both the beginning and the end of the container.
C++ deques are commonly implemented as dynamically allocated arrays that can grow at both ends. This guarantees constant time access, amortized constant time insertion and deletion at either end of the deque, and linear time insertion and deletion from the middle of the deque.
| Constructors | create deques and initialize them with some data |
| Operators | compare, assign, and access elements of a deque |
| assign | assign elements to a deque |
| at | returns an element at a specific location |
| back | returns a reference to last element of a deque |
| begin | returns an iterator to the beginning of the deque |
| clear | removes all elements from the deque |
| empty | true if the deque has no elements |
| end | returns an iterator just past the last element of a deque |
| erase | removes elements from a deque |
| front | returns a reference to the first element of a deque |
| insert | inserts elements into the deque |
| max_size | returns the maximum number of elements that the deque can hold |
| pop_back | removes the last element of a deque |
| pop_front | removes the first element of the deque |
| push_back | add an element to the end of the deque |
| push_front | add an element to the front of the deque |
| rbegin | returns a reverse_iterator to the end of the deque |
| rend | returns a reverse_iterator to the beginning of the deque |
| resize | change the size of the deque |
| size | returns the number of items in the deque |
| swap | swap the contents of this deque with another |
Notes
The name deque is pronounced “deck”, and stands for “double-ended queue.” Knuth reports that the name was coined by E. J. Schweppe. See section 2.2.1 of Knuth for more information about deques. (D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition. Addison-Wesley, 1973.)