Deque
aus Wikipedia, der freien Enzyklopädie
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, bzw. Entnehmen eines Elements am vorderen Ende der Deque.
- PUT und GET für das Einfügen, bzw. Entnehmen am hinteren Ende der Deque.
- FIRST und LAST für das Lesen des ersten, bzw. letzten Elementes, ohne es zu entfernen.
Technisch wird die Deque entweder als doppelt verzeigerte 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)
