Stapel und Warteschlangen in Python

Einführung

Datenstrukturen organisieren den Speicher in Computern, damit wir effizient auf Daten zugreifen und sie ändern können. Stapel und Warteschlangen sind einige der frühesten Datenstrukturen, die in der Informatik definiert wurden.

Einfach zu erlernen und einfach zu implementieren, sind ihre Verwendungen üblich und Sie werden höchstwahrscheinlich feststellen, dass Sie sie für verschiedene Aufgaben in Ihre Software integrieren.

Es ist üblich, dass Stacks und Warteschlangen mit einem Array oder einer verknüpften Liste implementiert werden. Wir verlassen uns auf die List Datenstruktur, um sowohl Stapel als auch Warteschlangen aufzunehmen.

Wie funktionieren sie?

Stack

Stacks folgen, wie der Name schon sagt, dem LIFO-Prinzip (Last-in-First-Out). Als ob wir Münzen übereinander stapeln würden, ist die letzte Münze, die wir darauf legen, diejenige, die als erste später vom Stapel genommen wird.

Um einen Stapel zu implementieren, benötigen wir daher zwei einfache Operationen:

• push – fügt ein Element oben auf dem Stapel hinzu:

• pop – entfernt das Element oben auf dem Stapel:

Warteschlange

Warteschlangen, wie die wie der Name schon sagt, folgen Sie dem First-in-First-Out-Prinzip (FIFO). Als würde man in einer Warteschlange auf die Kinokarten warten, ist der erste, der in der Schlange steht, der erste, der ein Ticket kauft und den Film genießt.

Um eine Warteschlange zu implementieren, benötigen wir daher zwei einfache Operationen:

• enqueue – fügt ein Element am Ende der Warteschlange hinzu:

• dequeue – entfernt das Element am Anfang der Warteschlange:

Stapel und Warteschlangen mit Listen

Pythons built-in List Datenstruktur kommt mit Methoden gebündelt sowohl Stapel- und Warteschlangenoperationen zu simulieren.

Betrachten wir einen Buchstabenstapel:

Wir können die gleichen Funktionen verwenden, um eine Warteschlange zu implementieren. Die Funktion pop nimmt optional den Index des Elements, das wir abrufen möchten, als Argument.

Wir können also pop mit dem ersten Index der Liste verwenden, dh 0 , um warteschlangenartiges Verhalten zu erhalten.

Betrachten Sie eine „Warteschlange“ von Früchten:

Auch hier verwenden wir die append und pop Operationen der Liste, um die Kernoperationen einer Warteschlange zu simulieren.

Stapel und Warteschlangen mit der Deque-Bibliothek

Python verfügt über eine deque (ausgesprochen „deck“) Bibliothek, die eine Sequenz mit effizienten Methoden zum Arbeiten als Stapel oder Warteschlange bereitstellt.

deque ist die Abkürzung für Double Ended Queue – eine verallgemeinerte Warteschlange, die das erste oder letzte gespeicherte Element abrufen kann:

Wenn Sie mehr über die deque Bibliothek und andere Arten von Sammlungen erfahren möchten, die Python bereitstellt, lesen Sie unseren Artikel Einführung in Pythons Collections-Modul.

Strengere Implementierungen in Python

Wenn Ihr Code einen Stack benötigt und Sie eine List , hindert nichts einen Programmierer daran, insertremove oder andere Listenfunktionen aufzurufen, die die Reihenfolge Ihres Stacks beeinflussen! Dies ruiniert grundlegend den Punkt der Definition eines Stapels, da er nicht mehr so funktioniert, wie er sollte.

Es gibt Zeiten, in denen wir sicherstellen möchten, dass nur gültige Operationen an unseren Daten ausgeführt werden können.

Wir können Klassen erstellen, die nur die notwendigen Methoden für jede Datenstruktur verfügbar machen.

Dazu erstellen wir eine neue Datei mit dem Namen stack_queue.py und definieren zwei Klassen:

Die Programmierer, die unsere Stack und Queue verwenden, werden nun ermutigt, stattdessen die bereitgestellten Methoden zur Manipulation der Daten zu verwenden.

Beispiele

Stellen Sie sich vor, Sie sind ein Entwickler, der an einem brandneuen Textverarbeitungsprogramm arbeitet. Sie haben die Aufgabe, eine Rückgängig-Funktion zu erstellen, mit der Benutzer ihre Aktionen bis zum Beginn der Sitzung zurückverfolgen können.

Ein Stack eignet sich ideal für dieses Szenario. Wir können jede Aktion aufzeichnen, die der Benutzer ausführt, indem wir sie auf den Stapel schieben. Wenn der Benutzer eine Aktion rückgängig machen möchte, wird sie vom Stapel entfernt. Wir können die Funktion schnell wie folgt simulieren:

Warteschlangen werden auch in der Programmierung häufig verwendet. Denken Sie an Spiele wie Street Fighter oder Super Smash Brothers. Spieler in diesen Spielen können Spezialbewegungen ausführen, indem sie eine Tastenkombination drücken. Diese Tastenkombinationen können in einer Warteschlange gespeichert werden.

Nun stell dir vor, du bist ein Entwickler, der an einem neuen Kampfspiel arbeitet. In Ihrem Spiel wird jedes Mal, wenn eine Taste gedrückt wird, ein Eingabeereignis ausgelöst. Ein Tester bemerkte, dass, wenn Tasten zu schnell gedrückt werden, das Spiel nur die erste verarbeitet und spezielle Bewegungen nicht funktionieren!

Sie können das mit einer Warteschlange beheben. Wir können alle Eingabeereignisse in die Warteschlange stellen, sobald sie eingehen. Auf diese Weise spielt es keine Rolle, ob Eingabeereignisse mit wenig Zeit dazwischen kommen, sie werden alle gespeichert und stehen zur Verarbeitung zur Verfügung. Wenn wir die Züge verarbeiten, können wir sie aus der Warteschlange nehmen. Ein spezieller Schritt kann folgendermaßen ausgearbeitet werden:

Fazit

Stapel und Warteschlangen sind einfache Datenstrukturen, mit denen wir Daten nacheinander speichern und abrufen können. In einem Stapel ist das letzte Element, das wir eingeben, das erste, das herauskommt. In einer Warteschlange ist das erste Element, das wir eingeben, das erste, das herauskommt.

Wir können Elemente mit der Operation push zu einem Stapel hinzufügen und Elemente mit der Operation pop abrufen. Bei Warteschlangen fügen wir Elemente mit der Operation enqueue hinzu und rufen Elemente mit der Operation dequeue ab.

In Python können wir Stapel und Warteschlangen implementieren, indem wir einfach die eingebaute List Datenstruktur verwenden. Python hat auch die deque Bibliothek, die effizient Stapel- und Warteschlangenoperationen in einem Objekt bereitstellen kann. Schließlich haben wir unsere Stack- und Queue-Klassen für eine engere Kontrolle unserer Daten erstellt.

Es gibt viele reale Anwendungsfälle für Stapel und Warteschlangen, deren Verständnis es uns ermöglicht, viele Datenspeicherprobleme auf einfache und effektive Weise zu lösen.