Double-Ended Queue

Double-Ended Queue

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, bei der die Daten an beiden Enden eingefügt oder entfernt werden können.

Die Operationen der Deque sind:

  • PUSH und POP für das Einfügen oder Entnehmen eines Elements am vorderen Ende der Deque.
  • PUT und GET für das Einfügen oder Entnehmen am hinteren Ende der Deque.
  • FIRST und LAST für das Lesen des ersten oder letzten Elementes, ohne es zu entfernen.

Technisch wird die Deque entweder als doppelt verkettete Liste realisiert - also ähnlich wie bei der Warteschlange oder dem Stapelspeicher - oder als Feld mit Hilfsindizes.

In der Praxis verwendet man die Deque unter anderem zur Implementierung von nichtdeterministischen endlichen Automaten und zur Textsuche mittels regulärer Ausdrücke (Pattern-Matching-Algorithmus)

In der esoterischen Programmiersprache „AlPhAbEt“ ist ein Deque (dort bekannt als „Queack“) als einzige Datenstruktur verfügbar.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Double-ended queue — Not to be confused with Double ended priority queue. In computer science, a double ended queue (dequeue, often abbreviated to deque, pronounced deck) is an abstract data structure that implements a queue for which elements can only be added to or …   Wikipedia

  • double-ended queue — noun An abstract list type data structure where elements can be added to or removed from the front (head) or the back (tail) …   Wiktionary

  • Double-ended priority queue — Not to be confused with Double ended queue. A double ended priority queue (DEPQ)[1] is an abstract data type similar to a priority queue except that it allows for efficient removal of both the maximum and minimum element. It is a data structure… …   Wikipedia

  • double-ended — adjective a) Having two ends. This double ended arrow appears to point in two directions. b) to have a locomotive at each end We created a computer version of the card game using a double ended queue …   Wiktionary

  • Priority queue — A priority queue is an abstract data type in computer programming. It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a priority . stack: elements are pulled in last in first out order (e …   Wikipedia

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

  • Linked list — In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the… …   Wikipedia

  • Persistent data structure — In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in… …   Wikipedia

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • Java collections framework — class and interface hierarchy of java.util.Collection class and interface hierarchy …   Wikipedia

Share the article and excerpts

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