{"id":29848,"date":"2022-05-16T17:22:00","date_gmt":"2022-05-16T15:22:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=29848"},"modified":"2024-11-27T15:02:04","modified_gmt":"2024-11-27T14:02:04","slug":"queue-implementieren-array","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/queue-implementieren-array\/","title":{"rendered":"Queue mit einem Array implementieren"},"content":{"rendered":"\n

Im letzten Teil der Tutorialserie ging es darum, wie man eine Queue mit einer verketteten Liste implementiert<\/a>. In diesem Teil implementieren wir eine Queue mit einem Array \u2013 zun\u00e4chst eine bounded Queue (also eine mit fester Kapazit\u00e4t) \u2013 und dann eine unbounded Queue (also eine, deren Kapazit\u00e4t sich \u00e4ndern kann).<\/p>\n\n\n\n

Beginnen wir mit der einfachen Variante, der bounded Queue.<\/p>\n\n\n\n

Implementierung einer bounded Queue mit einem Array<\/h2>\n\n\n\n

Wir legen ein leeres Array an und f\u00fcllen dieses von links nach rechts (also von Index 0 an aufsteigend) mit den in die Queue eingef\u00fcgten Elementen. <\/p>\n\n\n\n

Die folgende Grafik zeigt eine Queue mit einem Array namens elements<\/code>, das acht Elemente fassen kann. Bisher wurden sechs Elemente in die Queue eingef\u00fcgt. Der tailIndex<\/code> zeigt immer die n\u00e4chste Einf\u00fcgeposition:<\/p>\n\n\n\n

\"Queue
Queue mit einem Array implementieren<\/figcaption><\/figure><\/div>\n\n\n\n

Beim Entnehmen der Elemente lesen wir diese ebenfalls von links nach rechts aus und entfernen sie aus dem Array. Der headIndex zeigt dabei immer die n\u00e4chste Leseposition.<\/p>\n\n\n\n

Die folgende Darstellung zeigt die Queue, nachdem wir vier der sechs Elemente wieder entnommen haben:<\/p>\n\n\n\n

\"Queue
Queue mit einem Array implementiert: Array in der Mitte gef\u00fcllt<\/figcaption><\/figure><\/div>\n\n\n\n

Da wir nun kurz vor dem Ende des Arrays angekommen sind, k\u00f6nnten wir (ohne zus\u00e4tzliche Logik) nur noch zwei Elemente in die Queue schreiben. Um die Queue wieder auf acht Elemente aufzuf\u00fcllen, gibt es zwei L\u00f6sungsm\u00f6glichkeiten:<\/p>\n\n\n\n

  1. Wir schieben die verbleibenden Elemente nach links, an den Anfang des Arrays. Diese Operation ist, insbesondere bei gro\u00dfen Arrays, sehr teuer.<\/li>
  2. Die bessere L\u00f6sung ist ein Ringbuffer (englisch: \"circular array\"). Das bedeutet, dass wir, wenn wir am Ende des Arrays angekommen sind, am Anfang des Arrays fortfahren. Das gilt sowohl f\u00fcr die Schreib- als auch die Leseoperation.<\/li><\/ol>\n\n\n\n

    Ringbuffer<\/h3>\n\n\n\n

    Um die Funktionsweise des Ringbuffers zu verdeutlichen, habe ich das Array aus dem Beispiel kreisf\u00f6rmig dargestellt:<\/p>\n\n\n\n

    \"Queue<\/figure><\/div>\n\n\n\n

    Weitere Elemente f\u00fcgen wir im Uhrzeigersinn ein, im folgenden Beispiel \"mango\", \"fig\", \"pomelo\" und \"apricot\" an die Positionen 6, 7 \u2013 und dann 0 und 1:<\/p>\n\n\n\n

    \"Queue<\/figure><\/div>\n\n\n\n

    Zur\u00fcck in der \"flachen\" Darstellung sieht das Array nunmehr wie folgt aus:<\/p>\n\n\n\n

    \"Queue
    Queue mit \"flacher\" Darstellung des Ringpuffers<\/figcaption><\/figure><\/div>\n\n\n\n

    Sowohl in der Kreisdarstellung als auch in dieser ist gut zu sehen, dass nach dem Element \"fig\" an Index 7 das Element \"pomelo\" an Index 0 folgt. <\/p>\n\n\n\n

    Das Entnehmen der Elemente erfolgt analog. Mit jeder Dequeue-Operation wandert der headIndex<\/code> um eine Position nach rechts, wobei auf die 7 nicht die 8, sondern die 0 folgt.<\/p>\n\n\n\n

    Volle Queue vs. leere Queue<\/h3>\n\n\n\n

    tailIndex<\/code> und headIndex<\/code> liegen sowohl bei einer leeren als auch bei einer vollen Queue auf derselben Position. Damit wir erkennen k\u00f6nnen, wann die Queue voll ist, speichern wir zus\u00e4tzlich die Anzahl der Elemente.<\/p>\n\n\n\n

    So k\u00f6nnte eine volle Queue aussehen:<\/p>\n\n\n\n

    \"Queue-Implementierung:
    Queue-Implementierung: voller Ringpuffer<\/figcaption><\/figure><\/div>\n\n\n\n

    Und so eine leere (z. B. nachdem aus der eben dargestellten Queue alle acht Elemente entnommen wurden):<\/p>\n\n\n\n

    \"Queue-Implementierung:
    Queue-Implementierung: leerer Ringpuffer<\/figcaption><\/figure><\/div>\n\n\n\n

    Das Speichern der Anzahl der Elemente ist nicht die einzige M\u00f6glichkeit, aber eine sehr simple, um eine volle von einer leeren Queue zu unterscheiden. Alternativen sind z. B.:<\/p>\n\n\n\n