Deque
Encyclopedia : D : DE : DEQ : Deque
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 doubly 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.
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.Operations
The following operations are possible on a deque:- push_back
- push_front
- pop_back
- pop_front
- peek_back
- peek_front
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).
See also
- Data structure
- *Linear data structures
- **Array
- **Linked list
- **Queue
- **Stack
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.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.