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, 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.