Double-ended queue

From Wikipedia, the free encyclopedia

In computer science, a double-ended queue (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 head-tail linked list.

Contents 1 Naming conventions 2 Distinctions and sub-types 3 Operations 4 Implementations 5 Language support 6 Complexity 7 Applications 8 See also 9 References 10 External links

[edit] 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. DEQ and DQ are also used^{[citation needed]}.

[edit] 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:

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

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

Both the basic and most common list types in computing, the queues and stacks can be considered specializations of deques, and can be implemented using deques.

[edit] Operations

The following operations are possible on a deque:

operation	C++	Java	Perl	PHP	Python	Ruby	JavaScript
insert element at back	push_back	offerLast	push	array_push	append	push	push
insert element at front	push_front	offerFirst	unshift	array_unshift	appendleft	unshift	unshift
remove last element	pop_back	pollLast	pop	array_pop	pop	pop	pop
remove first element	pop_front	pollFirst	shift	array_shift	popleft	shift	shift
examine last element	back	peekLast	$_[-1]	end	<obj>[-1]	last	<obj>[<obj>.length - 1]
examine first element	front	peekFirst	$_[0]	reset	<obj>[0]	first	<obj>[0]

[edit] Implementations

There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly-linked list.

Dynamic array implementation 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. Two 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.

[edit] Language support

C++'s Standard Template Library provides the templated classes std::deque and std::list, for the dynamic 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.

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.

[edit] Complexity

• In a doubly-linked list implementation, 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).

[edit] Applications

One of examples where deque can be used is A-Steal job scheduling algorithm.^[2] This algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute a next thread, the processor gets the first element from the deque (using "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 processors finished execution of all own threads (i.e. its deque is empty), it can "steal" a thread from another processor: get the last element from deque of another processor ("remove last element") and execute it.

[edit] See also

• Queue
• Priority queue

[edit] References

[edit] External links

• SGI STL Documentation: deque<T, Alloc>
• Code Project: An In-Depth Study of the STL Deque Container
• Diagram of a typical STL deque implementation
• deque implementation in flash actionscript 3 open source library

v • d • e Data structures Types Collection · Container Arrays Associative array · Set · Multiset · Hash table Lists Double-ended queue · Linked list · Queue · Stack Trees B-tree · Binary search tree · Heap List of data structures