Deque

related topics
{math, number, function}
{language, word, form}

In computer science, a double-ended queue (often abbreviated to deque, pronounced deck) is an abstract data structure that implements a queue for which elements can only be added to or removed from the front (head) or back (tail).[1] It is also often called a head-tail linked list.

Contents

Naming conventions

Deque is sometimes written dequeue, but this use is generally deprecated in technical literature or technical writing because dequeue is also a verb meaning "to remove from a queue". Nevertheless, several libraries and some writers, such as Aho, Hopcroft, and Ullman in their textbook Data Structures and Algorithms, spell it dequeue. John Mitchell, author of Concepts in Programming Languages, also uses this terminology. DEQ and DQ are also used[citation needed].

Distinctions and sub-types

This differs from the queue abstract data type or First-In-First-Out List (FIFO), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types:

  • An input-restricted deque is one where removal can be made from both ends, but input can only be made at one end.
  • An output-restricted deque is one where input can be made at both ends, but output can be made from one end only.

Both the basic and most common list types in computing, queues and stacks can be considered specializations of deques, and can be implemented using deques.

Operations

The following operations are possible on a deque:

Implementations

There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly-linked list.

Dynamic array implementation uses a variant of a dynamic array that can grow from both ends, sometimes called array deques. These array deques have all the properties of a dynamic array, such as constant time random access, good locality of reference, and inefficient insertion/removal in the middle, with the addition of amortized constant time insertion/removal at both ends, instead of just one end. Three common implementations include:

Full article ▸

related documents
List of logarithmic identities
Interior (topology)
Congruence relation
Bézout's theorem
Sigma-algebra
Toeplitz matrix
Inverse element
Homeomorphism
Quaternion group
CYK algorithm
Combination
Coset
Compiler-compiler
Normal subgroup
Hidden Markov model
Infinite product
Event (probability theory)
Box-Muller transform
Identity element
Harmonic series (mathematics)
Euclidean domain
Parity (mathematics)
Convex hull
De Moivre's formula
Triangle inequality
PSPACE-complete
Euphoria (programming language)
Memento pattern
Monomorphism
Nash embedding theorem