Queue

• Queue: Datenstruktur, welche effizientes Entfernen in der Einfügereihenfolge ermöglicht.
• First-In-First-Out (FIFO) Datenstruktur.
• Zugriff durch Methoden enqueue/dequeue realisiert.
• Einsatzbereiche:
  • Mensa
  • Verwaltung
  • Druckjobs
  • Wursttheke
• Implementierung durch linked list möglich
  • !introprog-v04-listen, p.161
  • Auch hier gelingt die Implementierung von enqueue und dequeue mit konstanter Laufzeit O(1).
• Array-Implementierung der Warteschlange üblicherweise als Ringpuffer (Ringbuffer) realisiert.
• Es werden zwei Zeiger (Indizes) mitgeführt, die auf den Anfang bzw. das Ende der Warteschlange zeigen.
  • Nachteil: Maximale Größe ist fest
  • Zugriff auf Elemente kann effizienter sein als mit Linked Lists
    !introprog-v04-listen, p.163