In computer science theory, a deque (short for double-ended queue—Deque is usually pronounced deck.) is an abstract list type data structure, also called a head-tail linked list, for which elements can be added to or removed from the front (head) or back (tail). Naming conventions Deque is sometimes written dequeue, but this use is generally deprecated (not preferred) in technical literature or technical writing because dequeue is also a verb meaning "to remove from a queue". Nevertheless, several libraries and some writers, such as Aho, Hopcroft, and Ullman in their textbook Data Structures and Algorithms, spell it dequeue. DEQ and DQ are also used.Distinctions and sub-types This differs from the queue abstract data type or First-In-First-Out List (FIFO), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types:
|insert element at back|| || || || || || |
|insert element at front|| || || || || || |
|remove last element|| || || || || || |
|remove first element|| || || || || || |
|examine last element|| || || || || || |
|examine first element|| || || || || || |
Deque are often implemented using a variant of a dynamic array that can grow from both ends, sometimes called array deques. These array deques have all the properties of a dynamic array, such as constant time random access, good locality of reference, and inefficient insertion/removal in the middle, with the addition of amortized constant time insertion/removal at both ends, instead of just one end. Two common implementations include:
As of Java 6, Java's Collections Framework provides a new interface that provides the functionality of insertion and removal at both ends. It is implemented by classes such as (also new in Java 6) and , providing the dynamic array and linked list implementations, respectively.
Python 2.4 introduced the collections module with support for deque objects.