Deque

Deque

In computer science theory, a deque (short for "double-ended queue"—"Deque" is usually pronounced "deck.") is an abstract list type data structure, also called a head-tail linked list, for which elements can be added to or removed from the front (head) or back (tail).

;Naming conventions"Deque" is sometimes written "dequeue", but this use is generally deprecated (not preferred) 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". DEQ and DQ are also used.

;Distinctions and sub-typesThis 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 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, the 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. For information about doubly-linked lists, see the linked list article.

Dynamic array implementation

Deque are often implemented using 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. Two common implementations include:
* Storing deque contents in a circular buffer, and only resizing when the buffer becomes completely full. This decreases the frequency of resizings, but requires an expensive branch instruction for indexing.
* 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.

Language support

C++'s Standard Template Library provides the templated classes std::deque and std::list, for the dynamic array and linked list implementations, respectively.

As of Java 6, Java's Collections Framework provides a new Javadoc:SE|java/util|Deque interface that provides the functionality of insertion and removal at both ends. It is implemented by classes such as Javadoc:SE|java/util|ArrayDeque (also new in Java 6) and Javadoc:SE|java/util|LinkedList, providing the dynamic array and linked list implementations, respectively.

Python 2.4 introduced the "collections" module with support for deque objects.

Complexity

* In a doubly-linked list implementation, the time complexity of all operations is O(1), except for accessing an element in the middle using only its index, which is O(n).
* In a growing array, the amortized time complexity of all operations is O(1), except for removals and inserts into the middle of the array, which are O(n).

See also

*Data structure
**Linear data structures
***Array
***Linked list
***Queue
***Stack

References

* Donald Knuth. "The Art of Computer Programming", Volume 1: "Fundamental Algorithms", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.

External links

* [http://www.sgi.com/tech/stl/Deque.html SGI STL Documentation: deque]
* [http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp Code Project: An In-Depth Study of the STL Deque Container]
* [http://pages.cpsc.ucalgary.ca/~kremer/STL/1024x768/deque.html Diagram of a typical STL deque implementation]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • deque — s. m. 1. Pavimento superior dos navios. = CONVÉS 2. Pavimento de madeira num jardim, terraço ou espaço ao ar livre. 3. Dispositivo de leitura ou de gravação de cassetes.   ‣ Etimologia: inglês deck …   Dicionário da Língua Portuguesa

  • dequé — m. avoir ; bien ; fortune ; aisance …   Diccionari Personau e Evolutiu

  • deque — (De de2 y que). conj. coloq. p. us. Después que, luego que …   Diccionario de la lengua española

  • Deque (C++) — C++ Standard Library fstream iomanip ios iostream sstream string …   Wikipedia

  • Deque — Eine Deque (Double Ended QUEue, sprich: „Deck“) bezeichnet eine Datenstruktur der Informatik. Hierbei handelt es sich um eine Datenstruktur ähnlich der Warteschlange oder des Stapelspeichers. Der Unterschied besteht darin, dass die Daten an… …   Deutsch Wikipedia

  • deque — ► adverbio vulgar Después que, luego que, en cuanto: ■ deque lo vi acercarse, salí corriendo para no verle. * * * deque (de «de2» y «que»; pop.) conj. *Cuando o en cuanto: ‘Deque le vi llegar me marché por la otra puerta’. * * * deque …   Enciclopedia Universal

  • deque — noun A linear data structure in which elements may be appended to or removed from either end. This algorithm is difficult to implement with a standard queue, but with a deque its easy …   Wiktionary

  • deque — De de , del latín y que , del latín quid . (cnj.) (des.) (Muchos sitios) Cuando, después que, en cuanto. Deque terminéis de jugar hago la cena …   Diccionario Jaén-Español

  • susque deque — …   Useful english dictionary

  • DEQ — deque …   Abbreviations in Latin Inscriptions

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”