8.5 Die Klassen »Queue« und »Stack«

Ganz spezielle Listen werden durch die Klassen Stack und Queue zur Verfügung gestellt, denn beide implementieren weder das Interface IList noch IDictionary. Dennoch werden sie den Auflistungen zugerechnet, weil sie die Schnittstellen ICollection und somit auch IEnumerable implementieren.

Stack ist eine Datenstruktur, die nach dem LIFO-Prinzip (Last In First Out) arbeitet: Das Element, das als Letztes eingefügt wurde, wird beim folgenden Lesevorgang als Erstes wieder entnommen. Daraus folgt, dass man auf das Element, das als Erstes auf den Stack gelegt worden ist, erst dann wieder zugreifen kann, wenn alle anderen Elemente den Stack verlassen haben.

Ein Queue-Objekt ist das Pendant zu Stack. Es arbeitet nach dem FIFO-Prinzip (First In First Out): Das zuerst in die Queue geschobene Element wird auch als Erstes wieder entnommen. Das Prinzip gleicht also einer Warteschlange an der Kasse eines Fußballstadions.

8.5.1 Die Klasse »Stack«

Schauen wir uns an einem Beispiel an, wie man mit der Klasse Stack arbeitet.

// Beispiel: ..\Kapitel 8\StackSample
class Program {
  static void Main(string[] args) {
    Stack myStack = new Stack(11);
    // Stack füllen
    for(int i = 0; i <= 10; i++)
      myStack.Push(i * i);
    // Ausgabe in der Konsole    
    PrintStack(myStack);
    Console.ReadLine();
  }
  public static void PrintStack(Stack obj) {
    // alle Elemente aus dem Stack holen
    while(obj.Count != 0) {
      Console.WriteLine(obj.Pop());
    }
  }
}

Listing 8.20 Beispielprogramm mit der Klasse »Stack«

Das Hinzufügen neuer Elemente geschieht durch den Aufruf der Methode Push, die als Argument ein Objekt erwartet. Im Beispielcode wird eine Schleife durchlaufen, in der insgesamt elf Zahlen auf den Stack gelegt werden. Es handelt sich dabei immer um das Quadrat des aktuellen Schleifenzählers.

Zugegriffen werden kann nur auf das oberste Element im Stack. Dabei handelt es sich immer um das Objekt, das als Letztes mit der Push-Methode auf den Stack gelegt wurde.

Es bieten sich zwei Alternativen an, das oberste Element auszuwerten: Mit Pop wird das oberste Element nicht nur zurückgeliefert, sondern gleichzeitig auch der Stack-Verwaltung entzogen. Mit Peek erhält man zwar die Referenz, ohne das Element jedoch gleichzeitig zu entfernen. Im Beispiel wird der Stack so lange mit Pop abgegriffen, bis die Liste wieder leer ist. Die Reihenfolge der Zahlen beim Hinzufügen lautete:

0 1 4 9 16 25 36 ... 81 100

Die Rückgabe erfolgt mit:

100 81 64 ... 25 16 9 4 1 0

Der Aufruf des parameterlosen Konstruktors der Klasse Stack führt zu einer Kapazität von zehn Elementen, die bei Bedarf automatisch erhöht wird, um weitere Elemente aufzunehmen. Dabei werden alle Elemente in ein neues Array kopiert. Wenn Sie wissen, dass Sie diese Anzahl überschreiten werden, sollten Sie aus Gründen einer besseren Performance den parametrisierten Konstruktor wählen, der die Übergabe der erforderlichen Startkapazität ermöglicht:

Stack stack = new Stack(100);

Reicht das immer noch nicht aus und wird zur Laufzeit die Initialisierungsgröße trotzdem überschritten, verdoppelt sich die Kapazität automatisch.

8.5.2 Die Klasse »Queue«

Das Beispiel, das vorhin die Klasse Stack veranschaulichte, wird nun auf ein Queue-Objekt umgeschrieben:

// Beispiel: ..\Kapitel 8\QueueSample
class Program {
  static void Main(string[] args) {
    Queue myQueue = new Queue();
    // Queue füllen
    for(int i = 0; i <= 10; i++)
      myQueue.Enqueue(i * i);
    // Ausgabe in der Konsole
    PrintQueue(myQueue);
    Console.ReadLine();
  }
  public static void PrintQueue(Queue obj) {
    // alle Elemente aus der Queue holen
    while(obj.Count != 0) {
      Console.WriteLine(obj.Dequeue());
    }
  }
}

Listing 8.21 Beispielprogramm mit der Klasse »Queue«

Diesmal sind es die beiden Methoden Enqueue und Dequeue, mit denen Elemente in die Liste geschoben und wieder aus ihr geholt werden. Dequeue liefert nicht nur die Referenz des am Anfang befindlichen Elements, es holt dieses Element auch aus der Warteschlange. Wie bei der Klasse Stack können Sie sich mit Peek auch die Referenz dieses Elements besorgen und es gleichzeitig in der Liste lassen.

Der Elementzugriff erfolgt in derselben Reihenfolge, in der die Objekte der Liste hinzugefügt wurden: Das erste hinzugefügte Element wird auch als Erstes herausgeholt, danach kann man das zweite in die Warteschlange gelegte Element holen usw. Ein Zugriff auf ein beliebiges Element ist weder beim Stack noch bei der Queue möglich.

Die Standardkapazität eines Queue-Objekts beträgt 32 Elemente, die Sie mit Hilfe eines anderen Konstruktors bei der Instanziierung bedarfsgerecht festlegen können.

Ihre Meinung

Wie hat Ihnen das Openbook gefallen? Wir freuen uns immer über Ihre Rückmeldung. Schreiben Sie uns gerne Ihr Feedback als E-Mail an kommunikation@rheinwerk-verlag.de.