dequeue

Dequeue (also spelled dequeue) has two related meanings in computer science. The verb refers to removing and returning the element at the front of a queue. The noun deque (short for double-ended queue) is a data structure that supports insertion and removal at both ends.

In a deque, common operations include push_front (or addFirst), push_back (or addLast), pop_front (or removeFirst), and pop_back (or removeLast). Many implementations provide O(1) time for these operations. Deques can be built using a dynamic array with a circular buffer, or using a linked list, or a combination of both.

Compared with a standard queue, which enqueues at the back and dequeues from the front, a deque offers insertions and removals at both ends. A stack typically allows access only to one end. Deques can implement both queues and stacks, and are often used as a general-purpose double-ended container.

Applications include algorithms requiring access to either end, such as breadth-first search with a double-ended frontier, or as a building block in caching and scheduling policies. In concurrent programming, there are multi-producer/multi-consumer deques and lock-free variants.

See also: queue, stack, linked list, circular buffer, priority queue.