Deque
From Wikipedia, the free encyclopedia
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. Both queues and stacks can be considered specializations of deques, and can be implemented using deques.
Deque is usually pronounced deck, possibly due to the conceptual similarity to a deck of cards, where a card can be dealt from or returned to either the face or patterned side.
Contents |
[edit] Naming
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.
Donald Knuth reports that the name was coined by E. J. Schweppe.
[edit] Operations
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] |
<obj>[-1] |
| examine first element | front | peekFirst | $_[0] |
<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. For information about doubly-linked lists, see the linked list article.
[edit] Dynamic array implementation
Deque are often implemented using a dynamic array that grows in both ends, sometimes called array deques. These array deques have all the properties of a dynamic array (e.g. constant time random access, but inefficient insertion/removal in the middle, etc.), with the addition of efficient insertion/removal at both ends, instead of just one end. Implementations vary, but sometimes elements wrap around in a circular buffer, and when the buffer becomes full it is resized (like with dynamic arrays).
[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.
Python 2.4 introduced the collections module with support for deque objects.
[edit] Complexity
- In a doubly-linked list implementation, the Time complexity of all operations is O(1).
- In a growing array, the amortized complexity of all operations is O(1).
[edit] See also
- Data structure
- Linear data structures
[edit] References
- 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.
