Deque

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 beiden Enden gelesen, 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 hinteren Ende der Deque.
  • PUT und GET für das Einfügen oder Entnehmen am vorderen 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)

Trivia[Bearbeiten]

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

Weblinks[Bearbeiten]