HOME
The Info List - Double-ended Queue


--- Advertisement ---



In computer science , a DOUBLE-ENDED QUEUE (DEQUEUE, often abbreviated to DEQUE) 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). 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).

CONTENTS

* 1 Naming conventions * 2 Distinctions and sub-types * 3 Operations

* 4 Implementations

* 4.1 Purely functional implementation

* 5 Language support * 6 Complexity * 7 Applications * 8 See also * 9 References * 10 External links

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.

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 deletion can be made from both ends, but insertion can be made at one end only. * An output-restricted deque is one where insertion can be made at both ends, but deletion 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 basic operations on a deque are enqueue and dequeue on either end. Also generally implemented are peek operations, which return the value at that end without dequeuing it.

Names vary between languages; major implementations include:

OPERATION COMMON NAME(S) ADA C++
C++
JAVA PERL PHP
PHP
PYTHON RUBY JAVASCRIPT

insert element at back inject, snoc, push Append push_back offerLast push array_push append push push

insert element at front push, cons Prepend push_front offerFirst unshift array_unshift appendleft unshift unshift

remove last element eject Delete_Last pop_back pollLast pop array_pop pop pop pop

remove first element pop Delete_First pop_front pollFirst shift array_shift popleft shift shift

examine last element peek Last_Element back peekLast $array end

last

examine first element

First_Element front peekFirst $array reset

first

IMPLEMENTATIONS

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

The dynamic array approach 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:

* Storing deque contents in a circular buffer , and only resizing when the buffer becomes full. This decreases the frequency of resizings. * Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end. * Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.

PURELY FUNCTIONAL IMPLEMENTATION

Double-ended queues can also be implemented as a purely functional data structure. Two versions of the implementation exist. The first one, called 'real-time deque, is presented below. It allows the queue to be persistent with operations in O ( 1 ) {displaystyle O(1)} worst-case time, but requires lazy lists with memoization . The second one, with no lazy lists nor memoization is presented at the end of the sections. Its amortized time is O ( 1 ) {displaystyle O(1)} if the persistency is not used; but the worst-time complexity of an operation is O ( n ) {displaystyle O(n)} where n {displaystyle n} is the number of elements in the double-ended queue.

Let us recall that, for a list l, l denotes its length, that NIL represents an empty list and CONS(h,t) represents the list whose head is h and whose tail is t. The functions drop(i,l) and take(i,l) return the list l without its first i elements, and the i's first elements respectively. Or, if l < i, they return the empty list and l respectively.

A double-ended queue is represented as a sixtuple lenf,f,sf,lenr,r,sr where f is a linked list which contains the front of the queue of length lenf. Similarly, r is a linked list which represents the reverse of the rear of the queue, of length lenr. Furthermore, it

.