Double-ended queue

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 implemenation of a deque uses a doubly linked list.

Deque is usually pronounced deck.

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