This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end. Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached.

This decreases the frequency of resizings.

Storing deque contents in a circular buffer, and only resizing when the buffer becomes full.

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. The dynamic array approach uses a variant of a dynamic array that can grow from both ends, sometimes called array deques. There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list. Names vary between languages major implementations include: Also generally implemented are peek operations, which return the value at that end without dequeuing it. The basic operations on a deque are enqueue and dequeue on either end.

An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.īoth the basic and most common list types in computing, queues and stacks can be considered specializations of deques, and can be implemented using deques.

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

This general data class has some possible 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. John Mitchell, author of Concepts in Programming Languages, also uses this terminology. Nevertheless, several libraries and some writers, such as Aho, Hopcroft, and Ullman in their textbook Data Structures and Algorithms, spell it dequeue. The other common implementation of deques is with a doubly linked list, which allows for constant-time insertion and removal at both ends, but with less efficient random access than dynamic array-based implementations.ĭeque 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'. Three common implementations of array deques include storing deque contents in a circular buffer, allocating deque contents from the center of the underlying array, and storing contents in multiple smaller arrays. Dynamic array-based deques, also called array deques, can grow from both ends and have all the properties of a dynamic array, such as constant-time random access and good locality of reference, with the addition of amortized constant-time insertion and removal at both ends. Additionally, peek operations allow the value at one end to be examined without removing it. The basic operations on a deque are adding elements to either end and removing elements from either end. For example, queues and stacks can both be considered specializations of deques. Deques can have several sub-types, including input-restricted deques, where deletion can be made from both ends but insertion can only be made at one end, and output-restricted deques, where insertion can be made at both ends but deletion can only be made from one end.ĭeques are a fundamental data structure in computing, and many other data structures can be implemented using them. This is different from a queue, which only allows insertion at one end and removal from the other end, following a first-in, first-out (FIFO) order. It is also often called a head-tail linked list, though properly this refers to a specific data structure implementation of a deque (see below).Ī deque is a data structure that allows insertion and removal of elements from both ends. In computer science, a double-ended queue (abbreviated to deque, pronounced deck, like 'cheque' ) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

( April 2022) ( Learn how and when to remove this template message) Please help improve it to make it understandable to non-experts, without removing the technical details.

This article may be too technical for most readers to understand.

Java queue vs deque