Double-ended queue

In computer science, a double-ended queue (abbreviated to deque, pronounced "deck", like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a head-tail linked list, though properly this refers to a specific data structure "implementation" of a deque (see below).
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.
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:
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 basic operations on a deque are "enqueue" and "dequeue" on either end. Also generally implemented are "peek" operations, which return the value at that end without dequeuing it.
Names vary between languages; major implementations include:
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:
Purely functional implementation.
Double-ended queues can also be implemented as a purely functional data structure. Two versions of the implementation exist. The first one, called "'real-time deque", is presented below. It allows the queue to be persistent with operations in worst-case time, but requires lazy lists with memoization. The second one, with no lazy lists nor memoization is presented at the end of the sections. Its amortized time is if the persistency is not used; but the worst-time complexity of an operation is where is the number of elements in the double-ended queue.
Let us recall that, for a list codice_1, codice_2 denotes its length, that codice_3 represents an empty list and codice_4 represents the list whose head is codice_5 and whose tail is codice_6. The functions codice_7 and codice_8 return the list codice_1 without its first codice_10 elements, and the first codice_10 elements of codice_1, respectively. Or, if codice_13, they return the empty list and codice_1 respectively.
A double-ended queue is represented as a sextuple codice_15 where codice_16 is a linked list which contains the front of the queue of length codice_17. Similarly, codice_18 is a linked list which represents the reverse of the rear of the queue, of length codice_19. Furthermore, it is assured that codice_20 and codice_21 - intuitively, it means that neither the front nor the rear contains more than a third of the list plus one element. Finally, codice_22 and codice_23 are tails of codice_16 and of codice_18, they allow scheduling the moment where some lazy operations are forced. Note that, when a double-ended queue contains codice_26 elements in the front list and codice_26 elements in the rear list, then the inequality invariant remains satisfied after codice_10 insertions and codice_29 deletions when codice_30. That is, at most codice_31 operations can happen between each rebalancing.
Intuitively, inserting an element codice_32 in front of the double-ended queue codice_33 leads almost to the double-ended queue codice_34, the head and the tail of the double-ended queue codice_35 are codice_32 and almost codice_37 respectively, and the head and the tail of codice_38 are codice_32 and codice_40 respectively. The function to insert an element in the rear, or to drop the last element of the double-ended queue, are similar to the above function which deal with the front of the double-ended queue. It is said "almost" because, after insertion and after an application of "tail", the invariant codice_21 may not be satisfied anymore. In this case it is required to rebalance the double-ended queue.
In order to avoid an operation with an formula_1 costs, the algorithm uses laziness with memoization, and forces the rebalancing to be partly done during the following codice_42 operations, that is, before the following rebalancing. In order to create the scheduling, some auxiliary lazy functions are required. The function codice_43 returns the list codice_16, followed by the list codice_18, and followed by the list codice_46. It is required in this function that codice_47 is 2 or 3. This function is defined by induction as codice_48 where ++ is the concatenation operation, and by codice_49. codice_50 returns the list codice_16 followed by the list codice_18 reversed. The function codice_53 which returns codice_16 followed by (codice_18 without codice_56's first element) reversed is also required, for codice_57. It is defined by codice_58, codice_59 and codice_60.
The balancing function can now be defined with
fun balance(q as (lenf, f, sf, lenr, r, sr)) =
 if lenf > 2*lenr+1 then
 let val i = (left+lenr) div 2
 val j = lenf + lenr - i
 val f' = take(i, f)
 val r' = rotateDrop(r, i, f)
 in (i, f', f', j, r', r')
 else if lenf > 2*lenr+1 then
 let val j = (lenf+lenr) div 2
 val i = lenf + lenr - j
 val r' = take(i, r)
 val f' = rotateDrop(f, i, r)
 in (i, f', f', j, r', r')
 else q
Note that, without the lazy part of the implementation, this would be a non-persistent implementation of queue in amortized time. In this case, the lists codice_22 and codice_23 could be removed from the representation of the double-ended queue.
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 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. However, the ArrayDeque, contrary to its name, does not support random access.
Javascript's Array prototype & Perl's arrays have native support for both removing (shift and pop) and adding (unshift and push) elements on both ends.
Python 2.4 introduced the codice_63 module with support for deque objects. It is implemented using a doubly linked list of fixed-length subarrays.
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 2–3 finger trees annotated with sizes. There are other (fast) possibilities to implement purely functional (thus also persistent) double queues (most using heavily lazy evaluation). Kaplan and Tarjan were the first to implement optimal confluently persistent catenable deques. Their implementation was strictly purely functional in the sense that it did not use lazy evaluation. Okasaki simplified the data structure by using lazy evaluation with a bootstrapped data structure and degrading the performance bounds from worst-case to amortized. Kaplan, Okasaki, and Tarjan produced a simpler, non-bootstrapped, amortized version that can be implemented either using lazy evaluation or more efficiently using mutation in a broader but still restricted fashion. Mihaesau and Tarjan created a simpler (but still highly complex) strictly purely functional implementation of catenable deques, and also a much simpler implementation of strictly purely functional non-catenable deques, both of which have optimal worst-case bounds.
Rust's codice_64 includes VecDeque which implements a double-ended queue using a growable ring buffer.
Applications.
One example where a deque can be used is the work stealing algorithm. 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. The work stealing algorithm is used by Intel's Threading Building Blocks (TBB) library for parallel programming.