Dequeues

A deque, short for double-ended queue, is a data structure that supports insertion and removal of elements at both ends. It combines aspects of queues and stacks, offering end-oriented operations while maintaining the order of elements in the middle. Deques are versatile when both ends of a sequence may need to be accessed or modified.

Core operations typically include adding to the front (push_front or addFirst) and adding to the back (push_back or addLast), removing from the front (pop_front or removeFirst), and removing from the back (pop_back or removeLast). Many interfaces also provide peeking at either end without removing an element. While some languages expose random access by index, efficient access is generally limited to the two ends, and most end operations are designed to be constant time.

Implementations of deques commonly fall into two categories. An array-based circular buffer keeps elements in a contiguous array with wraparound indexing and resizes as needed, providing fast end operations with good cache locality. A doubly linked-list implementation uses nodes linked in both directions, allowing true constant-time insertions and removals at either end without resizing, at the cost of additional per-element memory for links.

Use cases for deques include breadth-first search, task scheduling, and buffering scenarios where both ends may be used to enqueue or dequeue data efficiently. They are implemented in many standard libraries, such as Python’s collections.deque, Java’s ArrayDeque, and C++’s std::deque, each delivering efficient end operations and varying levels of support for random access.