 Doubleended queue

Not to be confused with Doubleended priority queue.
In computer science, a doubleended queue (dequeue, often abbreviated to deque, pronounced deck) is an abstract data structure that implements a queue for which elements can only be added to or removed from the front (head) or back (tail).^{[1]} It is also often called a headtail linked list.
Contents
Naming conventions
Deque is sometimes written dequeue, but this use is generally deprecated 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. John Mitchell, author of Concepts in Programming Languages, also uses this terminology. DEQ and DQ are also used^{[citation needed]}.
Distinctions and subtypes
This differs from the queue abstract data type or FirstInFirstOut List (FIFO), where elements can only be added to one end and removed from the other. This general data class has some possible subtypes:
 An inputrestricted deque is one where deletion can be made from both ends, but insertion can only be made at one end.
 An outputrestricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.
Both the basic and most common list types in computing, queues and stacks can be considered specializations of deques, and can be implemented using deques.
Operations
The following operations are possible on a deque:
operation Ada C++ Java Perl PHP Python Ruby JavaScript insert element at back Append
push_back
offerLast
push
array_push
append
push
push
insert element at front Prepend
push_front
offerFirst
unshift
array_unshift
appendleft
unshift
unshift
remove last element Delete_Last
pop_back
pollLast
pop
array_pop
pop
pop
pop
remove first element Delete_First
pop_front
pollFirst
shift
array_shift
popleft
shift
shift
examine last element Last_Element
back
peekLast
$array[1]
end
<obj>[1]
last
<obj>[<obj>.length  1]
examine first element First_Element
front
peekFirst
$array[0]
reset
<obj>[0]
first
<obj>[0]
Implementations
There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list.
The dynamic array approach uses 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. Three common implementations include:
 Storing deque contents in a circular buffer, and only resizing when the buffer becomes completely full. This decreases the frequency of resizings, but requires an expensive branch instruction for indexing.
 Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.
 Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.
Language support
Ada's containers provides the generic packages Ada.Containers.Vectors and Ada.Containers.Doubly_Linked_Lists, for the dynamic array and linked list implementations, respectively.
C++'s Standard Template Library provides the class templates std::deque and std::list, for the multiple array and linked list implementations, respectively.
As of Java 6, Java's Collections Framework provides a new
Deque
interface that provides the functionality of insertion and removal at both ends. It is implemented by classes such asArrayDeque
(also new in Java 6) andLinkedList
, providing the dynamic array and linked list implementations, respectively. However, the ArrayDeque, contrary to its name, does not support random access.Python 2.4 introduced the
collections
module with support for deque objects.As of PHP 5.3, PHP's SPL extension contains the 'SplDoublyLinkedList' class that can be used to implement Deque datastructures. Previously to make a Deque structure the array functions array_shift/unshift/pop/push had to be used instead.
GHC's Data.Sequence module implements an efficient, functional deque structure in Haskell. The implementation uses 23 finger trees annotated with sizes. There are other (fast) possibilities to implement purely functional (thus also persistent) double queues (most using heavly lazy evaluation), see references ^{[2]}, ^{[3]}, ^{[4]}.
Complexity
 In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
 In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).
Applications
One example where a deque can be used is the ASteal job scheduling algorithm.^{[5]} This algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute the next thread, the processor gets the first element from the deque (using the "remove first element" deque operation). If the current thread forks, it is put back to the front of the deque ("insert element at front") and a new thread is executed. When one of the processors finishes execution of its own threads (i.e. its deque is empty), it can "steal" a thread from another processor: it gets the last element from the deque of another processor ("remove last element") and executes it.
See also
References
 ^ Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. AddisonWesley, 1997. ISBN 0201896834. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
 ^ www.cs.cmu.edu/~rwh/theses/okasaki.pdf C. Okasaki, "Purely Functional Data Structures", September 1996
 ^ Adam L. Buchsbaum and Robert E. Tarjan. Confluently persistent deques via data structural bootstrapping. Journal of Algorithms, 18(3):513–547, May 1995. (pp. 58, 101, 125)
 ^ Haim Kaplan and Robert E. Tarjan. Purely functional representations of catenable sorted lists. In ACM Symposium on Theory of Computing, pages 202–211, May 1996. (pp. 4, 82, 84, 124)
 ^ Eitan Frachtenberg, Uwe Schwiegelshohn (2007). Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006. Springer. ISBN 3540710345. See p.22.
External links
 SGI STL Documentation: deque<T, Alloc>
 Code Project: An InDepth Study of the STL Deque Container
 Diagram of a typical STL deque implementation
 Deque implementation in C
 VBScript implementation of stack, queue, deque, and RedBlack Tree
Data structures Types Abstract  List
 Associative array
 Multimap
 Set
 Multiset
 Doubleended queue
 Queue
 Priority queue
 Stack
Arrays Linked Trees Graphs Categories: Abstract data types
Wikimedia Foundation. 2010.
Look at other dictionaries:
DoubleEnded Queue — Eine Deque (Double Ended QUEue, sprich: „Deck“) bezeichnet eine Datenstruktur der Informatik. Hierbei handelt es sich um eine Datenstruktur ähnlich der Warteschlange oder des Stapelspeichers, bei der die Daten an beiden Enden eingefügt oder… … Deutsch Wikipedia
doubleended queue — noun An abstract list type data structure where elements can be added to or removed from the front (head) or the back (tail) … Wiktionary
Doubleended priority queue — Not to be confused with Double ended queue. A double ended priority queue (DEPQ)[1] is an abstract data type similar to a priority queue except that it allows for efficient removal of both the maximum and minimum element. It is a data structure… … Wikipedia
doubleended — adjective a) Having two ends. This double ended arrow appears to point in two directions. b) to have a locomotive at each end We created a computer version of the card game using a double ended queue … Wiktionary
Priority queue — A priority queue is an abstract data type in computer programming. It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a priority . stack: elements are pulled in last in first out order (e … Wikipedia
Deque (C++) — C++ Standard Library fstream iomanip ios iostream sstream string … Wikipedia
Linked list — In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the… … Wikipedia
Persistent data structure — In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in… … Wikipedia
Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space … Wikipedia
Java collections framework — class and interface hierarchy of java.util.Collection class and interface hierarchy … Wikipedia