7.1 The deque Data Abstraction

The name "deque" is short for "double-ended queue," and is pronounced like "deck." Traditionally, the term is used to describe any data structure that permits both insertions and removals from either the front or the back of a collection. The deque container class permits this, as well as much more. In fact, the capabilities of the deque data structure are almost a union of those provided by the vector and list classes.

• Like a vector, the deque is an indexed collection. Values can be accessed by subscript, using the position within the collection as a key. (A capability not provided by the list class).
• Like a list, values can be efficiently added either to the front or to the back of a deque. (A capability provided only in part by the vector class).
• As with both the list and vector classes, insertions can be made into the middle of the sequence held by a deque. Such insertion operations are not as efficient as with a list, but slightly more efficient that they are in a vector.

In short, a deque can often be used both in situations that require a vector and in those that call for a list. Often, the use of a deque in place of either a vector or a list will result in faster programs. To determine which data structure should be used, you can refer to the set of questions described in Section 4.2

The deque header file must appear in all programs that use the deque data type.

# include <deque>

©Copyright 1996, Rogue Wave Software, Inc.