Deque
From Wikipedia, the free encyclopedia
In computer science, a deque (short for double-ended queue) is a 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. A deque maintains a slightly modified FIFO structure, doing so using each end as both left and right. A common implementation of a deque uses a dynamic array, where the elements wrap around the end in a circular buffer. Deques can also be implemented using a doubly linked list, but that is normally just referred to as a linked list.
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 of dequeue's existing meaning as a verb: "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.
[edit] Operations
The following operations are possible on a deque:
- push_back
- push_front
- pop_back
- pop_front
- peek_back
- peek_front
[edit] Implementations
C++'s Standard Template Library provides a std::deque templated class to implement a deque that is based on a dynamic array. This provides a random access data structure that is more powerful than a dynamic array, since it can insert and delete in constant time on both ends of the list instead of only on one end.
[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.
