Stack feature imageStack feature image
HappyCoders Glasses

Stack mit einer Queue implementieren

Sven Woltmann
Sven Woltmann
16. März 2022

Im vorherigen Teil dieser Tutorial-Serie ging es darum, wie man einen Stack mit einer verketteten Liste implementiert. In diesem Teil zeige ich dir, wie du einen Stack mit einer Queue (besser gesagt: mit zwei Queues) implementieren kannst.

Diese Variante hat kaum praktischen Nutzen und wird in erster Linie als Übungsaufgabe verwendet (als Gegenstück gibt es übrigens auch eine Übung zur Implementierung einer Queue mit Stacks). Von daher: Versuch doch einmal selbst auf die Lösung zu kommen!

Zur Erinnerung: Eine Queue ist eine Datenstruktur, bei der du Elemente auf einer Seite einfügst und auf der anderen Seite wieder entnimmst – also eine First-in-First-out-Datenstruktur (FIFO).

Wie können wir damit einen Stack, also eine Last-in-First-out-Datenstruktur (LIFO) implementieren?

Die Lösung – Schritt für Schritt

Das erste Element, das wir auf den Stack schieben (im Beispiel: "apple"), fügen wir in eine Queue ein. Um es vom Stack zu entnehmen, holen wir es wieder aus der Queue:

Einfügen und Entnehmen eines Elements aus einer Queue

Das zweite Element können wir nicht einfach auch in diese Queue schreiben. Denn die funktioniert ja nach dem FIFO-Prinzip. Wenn wir "apple" und dann "orange" in die Queue schieben, müssen wir auch "apple" zuerst wieder entnehmen:

Einfügen und Entnehmen von zwei Elementen aus einer Queue

Bei einem Stack müssen wir jedoch das zuletzt auf den Stack geschobene Elemente "orange" zuerst wieder entnehmen – und nicht den zuerst eingefügten "apple".

Das ist mit einer einzigen Queue nicht möglich.

Stattdessen gehen wir beim Einfügen eines Elements wie folgt vor:

  1. Wir erzeugen eine neue Queue (in der Grafik unten orange dargestellt) und schieben auf diese das einzufügende Element.
  2. Wir verschieben das Element aus der ersten Queue in die neu erstellte Queue.
  3. Wir ersetzen die bestehende Queue durch die neue Queue.

Die folgende Grafik zeigt die drei Schritte:

Stack mit Queue implementieren: Zweites Element auf den Stack schieben
Zweites Element auf den Stack schieben

Danach liegen die Elemente so in der Queue, dass wir als erstes das zuletzt eingefügte Element "orange" entnehmen können und danach das zuerst eingefügte Element "apple".

Das funktioniert so nicht nur mit zwei Elementen, sondern mit beliebig vielen. Die folgende Grafik zeigt, wie wir ein drittes Element "pear" auf den Stack schieben. Der zweite Schritt aus der vorherigen Grafik ist hier in die Schritte 2a und 2b aufgeteilt: Zuerst wird "orange" aus der alten Queue in die neue verschoben, danach "apple".

Stack mit Queue implementieren: Drittes Element auf den Stack schieben
Drittes Element auf den Stack schieben

Danach können wir die Elemente in Last-in-First-out-Reihenfolge aus dem Stack entnehmen, also erst die zuletzt eingefügte "pear", dann die "orange", dann den zuerst eingefügten "apple".

Quellcode für den Stack mit Queues

Im folgenden siehst du, dass der Quellcode für die Lösung ziemlich einfach ist.

Als Queue verwende ich die einfachste Queue-Implementierung, ArrayDeque. Dass es sich auch um ein Deque handelt, stört uns nicht, denn wir weisen es ja einer Variablen zu, deren Typ das Queue-Interface ist.

Du findest den Quellcode in der Klasse QueueStack im GitHub-Repository.

public class QueueStack<E> implements Stack<E> { private Queue<E> queue = new ArrayDeque<>(); @Override public void push(E element) { Queue<E> newQueue = new ArrayDeque<>(); newQueue.add(element); while (!queue.isEmpty()) { newQueue.add(queue.remove()); } queue = newQueue; } @Override public E pop() { return queue.remove(); } @Override public E peek() { return queue.element(); } @Override public boolean isEmpty() { return queue.isEmpty(); } }
Code-Sprache: Java (java)

Das Demo-Programm StackDemo zeigt dir, wie du den QueueStack einsetzen kannst.

Ausblick

Im nächsten und letzten Teil des Tutorials behandeln wir eine weitere Übungsaufgabe: Wie kann man einen Stack per Rekursion umkehren?

Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.