Stacks mit nur einer Warteschlange umsetzen – so geht’s effizient

Stellen Sie sich vor, Sie müssten eine der grundlegendsten Datenstrukturen der Informatik – den Stack – mit einer anderen, der Queue, simulieren. Klingt ungewöhnlich, ist aber möglich. Die Idee dahinter ist nicht nur ein theoretisches Gedankenspiel, sondern zeigt, wie flexibel Algorithmen sein können, wenn man sie richtig kombiniert. Eine Stack-Implementierung mit nur einer Queue mag auf den ersten Blick ineffizient wirken, doch sie demonstriert, wie man mit einfachen Mitteln komplexe Datenstrukturen nachbilden kann.

Was genau ist eine Stack- und eine Queue-Implementierung?

Eine Stack-Implementierung mit einer Queue bedeutet, dass Sie die Eigenschaften einer LIFO-Struktur (Last In, First Out) mit den FIFO-Eigenschaften (First In, First Out) einer Warteschlange kombinieren. Das Ziel ist es, die Funktionalität eines Stacks zu erreichen, also das Hinzufügen (push) und Entfernen (pop) von Elementen nur am oberen Ende der Struktur zu ermöglichen, obwohl die Queue selbst nur am Ende hinzufügt und am Anfang entfernt.

In der Praxis bedeutet das: Jede Operation, die normalerweise in konstanter Zeit abläuft, erfordert hier zusätzliche Schritte, um die Elemente umzuordnen. Dennoch ist diese Methode ein hervorragendes Beispiel dafür, wie man mit begrenzten Mitteln viel erreichen kann – ähnlich wie bei der Simulation einer Queue mit zwei Stacks, einem klassischen Algorithmus-Thema.

Schritt 1: Eine Queue mit zwei Stacks simulieren

Bevor wir uns der eigentlichen Aufgabe widmen, lohnt es sich, das Grundprinzip zu verstehen. Eine Queue kann mit zwei Stacks implementiert werden, indem man die Elemente zwischen den Stacks hin- und herschiebt. Hier ist ein einfaches Beispiel in Java:

public class Fila<T> {
    private final Pilha<T> elementos = new Pilha<>();
    private final Pilha<T> secundaria = new Pilha<>();

    public void push(T t) {
        elementos.push(t);
    }

    public T pop() {
        while (!elementos.empty()) {
            secundaria.push(elementos.pop());
        }
        final var v = secundaria.pop();
        while (!secundaria.empty()) {
            elementos.push(secundaria.pop());
        }
        return v;
    }

    public boolean empty() {
        return elementos.isEmpty();
    }
}

In diesem Code wird die Queue durch zwei Stacks dargestellt. Beim Hinzufügen von Elementen landet alles in der primären Stack. Beim Entfernen werden alle Elemente in den sekundären Stack verschoben, sodass das zuletzt hinzugefügte Element (das erste in der Queue) oben liegt und entfernt werden kann. Anschließend werden die restlichen Elemente zurück in die primäre Stack verschoben.

Schritt 2: Eine Stack mit zwei Queues simulieren

Der nächste logische Schritt ist die Simulation einer Stack-Implementierung mit zwei Queues. Der Algorithmus funktioniert nach einem ähnlichen Prinzip: Beim Entfernen eines Elements (pop) werden alle Elemente bis auf das letzte aus der primären Queue in die sekundäre Queue verschoben. Das letzte Element wird entfernt, und die verbleibenden Elemente wandern zurück in die primäre Queue.

public class Pilha<T> {
    private final Fila<T> elementos = new Fila<>();
    private final Fila<T> secundaria = new Fila<>();

    public void push(T t) {
        elementos.push(t);
    }

    public T pop() {
        while (true) {
            final var candidato = elementos.pop();
            if (elementos.empty()) {
                // Elemente zurückführen
                while (!secundaria.empty()) {
                    elementos.push(secundaria.pop());
                }
                return candidato;
            }
            secundaria.push(candidato);
        }
    }

    public boolean empty() {
        return elementos.empty();
    }
}

Dieser Ansatz zeigt, wie die Queue-Elemente umsortiert werden, um die LIFO-Logik eines Stacks nachzuahmen. Obwohl jede pop-Operation hier linear in der Anzahl der Elemente ist, bleibt die Implementierung korrekt und funktionsfähig.

Schritt 3: Die ultimative Herausforderung – ein Stack mit nur einer Queue

Die Frage ist nun: Kann man einen Stack mit nur einer einzigen Queue implementieren? Die Antwort lautet ja – allerdings erfordert dies eine kreative Herangehensweise. Der Schlüssel liegt darin, ein spezielles Marker-Element zu verwenden, das nicht zum eigentlichen Datentyp gehört, um das Ende der Queue zu markieren.

Stellen Sie sich vor, Sie fügen jedes Mal, wenn ein neues Element hinzugefügt wird, ein Marker-Element an das Ende der Queue an. Wenn Sie dann ein Element entfernen, durchsuchen Sie die Queue, bis Sie auf das Marker-Element stoßen. Das Element direkt davor ist das, das entfernt werden soll. Anschließend wird die Queue neu aufgebaut, um das Marker-Element zu entfernen.

public class Pilha<T> {
    private final Fila<T> elementos = new Fila<>();

    public void push(T t) {
        elementos.push(t);
        elementos.push(null); // Marker-Element
    }

    public T pop() {
        T result = null;
        T current;
        while (true) {
            current = elementos.pop();
            if (current == null) {
                break;
            }
            result = current;
        }
        return result;
    }

    public boolean empty() {
        return elementos.empty();
    }
}

In dieser Implementierung wird jedes Element mit einem null-Marker gefolgt. Beim Entfernen wird die Queue durchlaufen, bis der Marker gefunden wird. Der letzte gültige Wert vor dem Marker ist das Element, das entfernt werden soll. Dieser Ansatz ist zwar nicht die effizienteste Methode, zeigt aber die Flexibilität von Algorithmen und wie man mit einfachen Mitteln komplexe Probleme lösen kann.

Warum solche Implementierungen wichtig sind

Obwohl diese Methoden in der Praxis selten verwendet werden, sind sie ein hervorragendes Training für das Verständnis von Datenstrukturen und Algorithmen. Sie zeigen, wie man mit begrenzten Ressourcen komplexe Anforderungen erfüllen kann – eine Fähigkeit, die in der Softwareentwicklung immer wichtiger wird, insbesondere bei der Optimierung von Speicher und Geschwindigkeit.

Die Implementierung eines Stacks mit einer Queue ist nicht nur ein theoretisches Experiment, sondern auch eine wertvolle Übung, um das Verständnis für die Grundlagen der Informatik zu vertiefen. Wer diese Konzepte beherrscht, ist besser gerüstet, um innovative Lösungen für reale Probleme zu entwickeln.

In Zukunft könnten solche Techniken in spezialisierten Systemen Anwendung finden, in denen die Anzahl der verfügbaren Datenstrukturen begrenzt ist. Bis dahin bleiben sie ein faszinierendes Beispiel dafür, wie kreativ man mit den Grundlagen der Programmierung umgehen kann.