Deques

Deques, short for double-ended queues, are a data structure that allows insertion and removal from both the front and the back. Unlike a standard queue, which supports insertion at the back and removal from the front, and unlike a stack, which supports insertion and removal at one end, a deque provides operations at both ends. Elements are stored in a linear order, and the end from which an operation occurs may be referred to as the front or back.

Common operations include push_front, push_back (sometimes called insert at front/back), pop_front, pop_back, as well as methods to peek at the front or back without removing. Some interfaces also allow inserting or removing at arbitrary positions, though such operations may not be constant time depending on the implementation.

Deques can be implemented using a doubly linked list, which gives O(1) time for all ends with no fixed capacity. Array-based implementations typically use a circular buffer and dynamic resizing, providing amortized O(1) time for end operations but potentially slower if resizing occurs. Most standard libraries provide a deque type, such as Python's collections.deque and C++'s std::deque.

Common applications include breadth-first search where both ends may be used, sliding window algorithms that extend or shrink at either end, and scenarios requiring flexible front insertion or removal without moving many elements. They are also used in caches and in algorithms that require a monotonic queue.