=====C++ Double-ended Queues=====

Double-ended queues (or deques) are similar to [[stl/vector/|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 [[/complexity|constant time]] access, amortized constant time insertion and deletion at either end of the deque, and [[/complexity|linear time]] insertion and deletion from the middle of the deque.

|[[deque_constructors|Constructors]]|create deques and initialize them with some data|
|[[deque_operators|Operators]]|compare, assign, and access elements of a deque|
|[[assign]]|assign elements to a deque|
|[[at]]|returns a reference to 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. [[http://www-cs-faculty.stanford.edu/~uno/taocp.html|(D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition. Addison-Wesley, 1973.)]]