From Wikipedia, the free encyclopedia

Linear data structures
Array Deque Linked list Queue Stack

In computer science, a deque (short for double-ended queue) is an abstract data structure for which elements can be added to or removed from the front or back. This differs from a normal queue, where elements can only be added to one end and removed from the other. 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 queues and stacks can be considered specializations of deques, and can be implemented using deques.

Deque is usually pronounced deck.

Contents 1 Naming 2 Operations 3 Implementations 3.1 Dynamic array implementation 4 Language support 5 Complexity 6 See also 7 References 8 External links

Deque is sometimes written dequeue, but this is generally not preferred 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.

The following operations are possible on a deque:

operation	C++	Java	Perl	Python
insert element at back	push_back	offerLast	push	append
insert element at front	push_front	offerFirst	unshift	appendleft
remove last element	pop_back	pollLast	pop	pop
remove first element	pop_front	pollFirst	shift	popleft
examine last element	back	peekLast	$_[-1]	[-1]
examine first element	front	peekFirst	$_[0]	[0]

There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly-linked list. For information about doubly-linked lists, see the linked list article.

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:

• 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.

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.

Python 2.4 introduced the collections module with support for deque objects.

• In a doubly-linked list implementation, the time complexity of all operations is O(1), except for accessing an element in the middle using only its index, which is O(n).
• In a growing array, the amortized time complexity of all operations is O(1), except for removals and inserts into the middle of the array, which are O(n).

• Data structure
  • Linear data structures
    • Array
    • Linked list
    • Queue
    • Stack

• Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.

• SGI STL Documentation: deque
• Code Project: An In-Depth Study of the STL Deque Container
• Diagram of a typical STL deque implementation