deque

A deque, short for double-ended queue, is a linear collection that supports insertion and removal at both ends. It can function as both a queue (first in, first out) and a stack (last in, first out) depending on how it is used. Deques allow efficient addition or removal of elements from the front and back without shifting the entire sequence.

Typical operations include adding to the front (push_front or appendleft), adding to the back (push_back or append), removing from the front (pop_front or popleft), and removing from the back (pop_back or pop). Many implementations also provide peeking at either end and querying size or emptiness. Complexity characteristics are generally favorable: insertions and removals at either end are amortized constant time in well-implemented deques. Random access to interior elements is usually linear in the number of elements, though some libraries offer direct indexing.

Memory layout for deques varies. They can be implemented as dynamic arrays with circular buffering, as linked lists with head and tail pointers, or as segmented structures that hold blocks of elements. Such designs aim to balance fast end operations with reasonable memory and cache efficiency.

Standard library support includes Python’s collections.deque, C++’s std::deque, and Java’s Deque interface with implementations such as ArrayDeque and LinkedList. These libraries typically provide O(1) time for end insertions and removals and offer iteration over elements.

Common use cases include task scheduling, undo/redo stacks, breadth-first search, sliding window calculations, and buffering streams where frequent additions and removals occur at both ends. Deques are not ideal for frequent middle insertions or deletions due to their typically linear cost in that region.