Double-ended queue

In computer science, a double-ended queue (abbreviated to deque), is an abstract data type that serves as an ordered collection of entities. It generalizes both a queue and a stack : elements can be added (enqueue) to or removed (dequeue) from either end. It provides similar services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the deque performs the function of a buffer. The additional flexibility in managing the order of elements or the properties of some implementations may allow the improvement and optimization of certain algorithms.

As a general data class, the deque has some possible sub-types:

• An input-restricted deque is one where deletion can be made from either end, but insertion can be made at one end only.
• An output-restricted deque is one where insertion can be made at either end, but deletion can be made from one end only.

Despite their limitations these sub-types have many applications and their implementations may be simpler.

Terminology

The term deque (Template:IPAc-en Template:Respell) is used as an acronym and in analogy to a deck of cards with which the structure shares some properties and the pronunciation.Template:Rp Dequeue is sometimes used but can be confusing as the term is also used for the operation of removing an element of the deque. A deque may also be called a head-tail linked list, though properly this refers to a specific implementation.
An input-restricted deque is often called a steque (for stack-ended queue).Template:RpTemplate:Rp

There is no standard vocabulary associated with deques. The terms enqueue and dequeue, borrowed from the queue structure, generally denote the basic operations on a deque, on either end. But papers and actual implementations often use different names. The names of the operations vary depending on the context, the author, the implementation or the programming language:

• in analogy to a queue: enqueue and dequeue, or push and pull;
• in analogy to a stack: push and pop on one side, and possibly inject and eject on the other side;
• in analogy to a list: cons and uncons on one side, snoc and unsnoc on the other side;
• in analogy to an array: append on one side, prepend on the other side, or shift and unshift.

Unlike the associated data structures the deque is symmetrical. Its sides may be freely named according to the context:

• in analogy to a queue: front and back;
• in analogy to a stack: top and bottom;
• in analogy to a list: head or last;
• in analogy to an array: first and end, or first and last;
• finally left and right preserves the original symmetry of the structure.

The full name of an operation may be a combination of the name of the basic operation and the name of the side: e.g. push_front and pop_back. Terms from different analogies may be associated in a single context: append and pop, push and shift, or front and tail. Finally some programming languages use even different names based on the underlying data structure.

Also generally implemented are "peek" operations, which return the value at one end without dequeuing it. It is often named after the target side: e.g. top is the value of the element at the top of the deque. In the context of the functional programming, the dequeue operation (that returns two values: the removed element and the new deque) is not used. It is replaced by a peek function (i.e. head and last) and a function that returns the deque minus the end, i.e. tail and init.

Implementations

There are at least two common ways to efficiently implement a deque, that are often pitted against one another: with a doubly linked list or with a modified dynamic array. There are many variations and actual implementations are often hybrid solutions. Additionally, several purely functional implementations of the double-ended queue exist.

Doubly linked list

While a simple list may implement a deque, a doubly-linked list is more adequate for its symmetry to achieve a fast access to both ends of the list (head and tail, hence the name head-tail linked list). The obvious solution is to manage two references; alternatively the deque can be build as a circular list.

A doubly linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.

A doubly linked list whose nodes contain three fields: the link to the previous node, an element value, and the link to the next node.

In a doubly-linked list implementation, and assuming no allocation/deallocation overhead, the time complexity of all deque operations is [[Big O notation|Template:Math]]. Additionally, insertion or deletion in the middle, given an iterator, can also be achieved in constant time; however, the time taken for random access by index is Template:Math. As well finding a specific element normally [[Linked list#Speeding up search|requires Template:Math time]]. Generally linked data structures have poor locality of reference.

Dynamic array

File:Dynamic array.svg

Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for expansion. Most insertions are fast (constant time), while some are slow due to the need for reallocation (Template:Math time, labelled with turtles).

In this case as well, while a dynamic array can be used to implement a deque, a variant that can grow from both ends is more appropriate. This is sometimes called array deques. This can be achieved in various ways, e.g.:

• by offsetting the position of the first element of the array in the reserved memory: the unused space is distributed on both side of the data;
• with a circular array.

The amortized time complexity of all deque operations with an array deque is [[Big O notation|Template:Math]], thanks to the geometric expansion of the back-end buffer. Additionally, random access by index takes constant time ; but the average time taken for insertion or deletion in the middle are Template:Math. Thank to the fast random access, finding an element in an ordered array is time Template:Math (binary search). Each time the array is resized, the whole content is moved: the memory usage is then momentarily doubled (or more), and all direct (external) references to the content of the array are lost.

Purely functional implementation

Doubly linked lists cannot be used as immutable data structures. And an immutable array would be highly inefficient (an array is often simulated by a tree). A purely functional implementation of the deque can be based on stack, that is easily implemented with a singly linked list as an immutable and persistent structure.

There are several works in the literature dealing with this problem. All of these use two key ideas. The first is that a deque can be represented by a pair of stacks, one representing the front part of the deque and the other representing the reversal of the rear part. When one side becomes empty because of too many pop or eject operations, the deque, now all on one stack, is copied into two stacks each containing half of the deque elements. This fifty-fifty split guarantees that such copying, even though expensive, happens infrequently. A simple amortization argument shows that this gives a linear-time simulation of a deque by a constant number of stacks: k deque operations starting from an empty deque are simulated by O(k) stack operations.
[…]
The second idea is to use incremental copying to convert this linear-time simulation into a real-time simulation: as soon as the two stack become sufficiently unbalanced, recopying to create two balanced stacks begins.

— Template:Comma separated entries

This last process could be rather complicated as it needs to be executed concurrently with other operations and completed before the next one, to achieve an amortized real-time complexity. The next step is to support the operations in Template:Math worst-case time. Another challenge is the real-time catenation of deques. Okasaki gives a simple solution that uses lazy lists combined with memoization. The stack to stack balancing is then partially automatic by means of a precise scheduling of incremental functions. Template:RpTemplate:Rp However some authors deem such algorithm as not purely functional since memoization is considered as a side effect.Template:Rp Kaplan and Tarjan gives their own version of the purely functional deque (non-catenable), based on three ideas:

• data-structural bootstrapping, resulting in a recursive structure that foresees the finger tree: a deque is a triple consisting of a sub-deque flanked by two size-bounded buffers. Enqueue and dequeue basically operate on the buffers (in real-time because of the bounded size), and move forward one step in the balancing process;
• recursive slow down, inspired by Redundant binary representation (RBR), where an additional 2 digit stands for a suspended carry: the sub-deque contains pairs of elements from the parent deque, and the propagation of the balancing process to the sub-deque is delayed like is the carry propagation after the increment or decrement of a RBR number;Template:Rp
• and a modification of the spine of the finger tree-like structure (a stack) into a stack of stacks that can be thought of as a 2-level skip list. This allows a real-time access to the unbalanced sub-deques. In analogy to a RBR, the sub-stacks stand for contiguous blocks of 1 digits, that can be skipped to access the next 2, i.e. a suspended carry.

Kaplan and Tarjan also present an even more complex version that achieves catenation in real-time. More generally, real-time catenation requires a deque is a tuple consisting mainly in two sub-structures, that themselves contain deques or compounds of deques. The linear spine of the non-catenable deque is then replaced by a binary skeleton.

Kaplan, Okasaki, and Tarjan produced a simpler, amortized version that can be implemented either using lazy evaluation or more efficiently using mutation in a broader but still restricted fashion. Mihaescu 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 (not officially published).

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.

UML class diagram of a double-ended queue

UML class diagram of a double-ended queue

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 as ArrayDeque (also new in Java 6) and LinkedList, 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 collections 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.

Rust's std::collections includes VecDeque which implements a double-ended queue using a growable ring buffer.

Applications

A double-ended queue can always be substituted for a queue or a stack structure. Thus real-world applications of the deque are often extended versions of stack- or queue-based algorithms. Actually many applications only need an output- or (more rarely) input-restricted deque. Only real-world applications that are optimally based on strict deque, i.e. witch only need access to the elements at both ends and one by one, are listed here.

Simple priority queue

Stacks and queues can be seen as a particular kinds of priority queues, with the priority determined by the order in which the elements are inserted. Similarly a deque can implement a priority queue with two levels of priority: high priority elements are added to the front side of the deque while low priority ones are added to the rear. Unless an element could be canceled or stolen and then ejected from the bottom, an output-restricted deque is adequate.

Thus it's possible to modify the standard Breadth-First Search algorithm to find single source shortest path in a graph with 0-cost and 1-cost edges. 0-cost elements are enqueued in front of the deque (high-priority) and then are always processed before the higher cost elements (low-priority).

A deque is used in 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.

Deque automaton

A Deque automaton (DA) is a finite-state machine equipped with a deque auxiliary memory. It generalizes Pushdown automaton (PDA) (stack automaton) and Queue automaton (Pull up automaton, PUA). As such it is equivalent to a Turing machine, and therefore it can process the same class of formal languages. But unlike the PDA and the PUA which impose serialization, a deque automaton permits parallel or interleaved execution of some operations.

See also

• Pipe
• Priority queue

External links

• Type-safe open source deque implementation at Comprehensive C Archive Network
• SGI STL Documentation: deque<T, Alloc>
• Code Project: An In-Depth Study of the STL Deque Container
• Deque implementation in C Template:Webarchive
• VBScript implementation of stack, queue, deque, and Red-Black Tree
• Multiple implementations of non-catenable deques in Haskell