↑Rezepte

Datenstrukturen

Warteschlangen

Mittels zweier Stapel

Eine Warteschlange ist, wie der Name bereits nahelegt, eine Datenstruktur, bei der Elemente effizient in derselben Reihenfolge entnommen werden können, in der sie in die Datenstruktur hineingebracht wurden. Ein eleganter Ansatz zur Umsetzung beruht auf der folgenden Idee. Bei der Entnahme der Elemente von einem Stapel dreht sich, wie man weiß, die Reihenfolge um, in welcher die Elemente auf den Stapel gelegt wurden. Durchläuft eine Reihe von Elementen diese Prozedur also zweimal aufeinanderfolgend, liegt danach wieder die ursprüngliche Reihenfolge vor.

Den ersten Stapel benennen wir istack für input stack, dt. Eingangsstapel und den zweiten ostack für output stack, dt. Ausgangsstapel. Die Operation enqueue soll ein Element zur Schlange hinzufügen, die Operation dequeue eines entnehmen. Bei enqueue wird das Element schlicht auf den Eingangsstapel gepackt. Dagegen verhält sich dequeue ein wenig komplizierter. Ist der Ausgangsstapel nichtleer, wird eines abgehoben. Ist der Ausgangsstapel dagegen leer, wird solange ein Element des Eingangsstapels entnommen und auf den Ausgangsstapel gelegt, bis der Eingangsstapel geleert wurde. Erst danach wird ein Element vom Ausgangsstapel abgehoben.

Zu beachten gilt, dass die Leerung des Eingangsstapels vollständig sein muss und nur dann erfolgen darf, wenn ein leerer Ausgangsstapel vorliegt. Andernfalls käme es zu einem logischen Fehler, das heißt, einer falschen Reihenfolge bei der Entnahme.

class Queue:
    def __init__(self):
        self.istack = []
        self.ostack = []

    def enqueue(self, x):
        self.istack.append(x)

    def dequeue(self):
        if len(self.ostack) == 0:
            while len(self.istack) != 0:
                self.ostack.append(self.istack.pop())
        if len(self.ostack) != 0:
            return self.ostack.pop()
        else:
            return None

Zur Analyse eine Testfunktion.

from itertools import product

def is_sorted(a):
    return all(a[i] < a[i+1] for i in range(len(a) - 1))

def test(n):
    assert isinstance(n, int) and n >= 0
    for ops in product("io", repeat = n):
        acc = []
        q = Queue()
        k = 0
        for op in ops:
            if op == "i":
                q.enqueue(k)
                k += 1
            else:
                result = q.dequeue()
                if not result is None:
                    acc.append(result)
        assert is_sorted(acc)