Einführung

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

Sie sind einfach zu erlernen und leicht zu implementieren und werden häufig verwendet, so dass Sie sie höchstwahrscheinlich für verschiedene Aufgaben in Ihre Software einbauen werden.

Stapel und Warteschlangen werden üblicherweise mit einem Array oder einer Linked List implementiert. Wir werden uns auf die Datenstruktur List verlassen, um sowohl Stapel als auch Warteschlangen unterzubringen.

Wie funktionieren sie?

Stapel

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

Um einen Stapel zu implementieren, brauchen wir also zwei einfache Operationen:

• push – fügt ein Element an die Spitze des Stapels hinzu:

• pop – entfernt das Element an der Spitze des Stapels:

Warteschlange

Warteschlangen folgen, wie der Name schon sagt, dem First-in-First-Out (FIFO) Prinzip. Wie bei einer Warteschlange für Kinokarten ist derjenige, der zuerst in der Schlange steht, auch der erste, der eine Karte kauft und den Film genießen kann.

Um eine Warteschlange zu implementieren, brauchen wir also 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

Die in Python eingebaute List Datenstruktur wird mit Methoden geliefert, die sowohl Stapel- als auch Warteschlangenoperationen simulieren.

Betrachten wir einen Stapel von Buchstaben:

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

So können wir pop mit dem ersten Index der Liste verwenden, d.h. 0, um ein Warteschlangen-ähnliches Verhalten zu erhalten.

Betrachten wir 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 hat eine deque (ausgesprochen ‚Deck‘) Bibliothek, die eine Sequenz mit effizienten Methoden bereitstellt, um als Stapel oder Warteschlange zu arbeiten.

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, die Python zur Verfügung stellt, erfahren möchten, können Sie unseren Artikel Einführung in das Python-Modul Sammlungen lesen.

Stricter-Implementierungen in Python

Wenn Ihr Code einen Stack benötigt und Sie ein List zur Verfügung stellen, hindert nichts einen Programmierer daran, insert, remove oder andere Listenfunktionen aufzurufen, die die Reihenfolge Ihres Stacks beeinflussen! Dies macht den Sinn der Definition eines Stacks zunichte, da er nicht mehr so funktioniert, wie er sollte.

Es gibt Situationen, in denen wir sicherstellen möchten, dass nur gültige Operationen mit unseren Daten durchgeführt werden können.

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

Zu diesem Zweck 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 aufgefordert, stattdessen die bereitgestellten Methoden zu verwenden, um die Daten zu manipulieren.

Beispiele

Stellen Sie sich vor, Sie sind ein Entwickler, der an einer brandneuen Textverarbeitung arbeitet. Sie haben die Aufgabe, eine Rückgängig-Funktion zu entwickeln, die es dem Benutzer ermöglicht, seine Aktionen bis zum Beginn der Sitzung zurückzuverfolgen.

Ein Stack ist für dieses Szenario ideal geeignet. Wir können jede Aktion des Benutzers aufzeichnen, indem wir sie in den Stapel schieben. Wenn der Benutzer eine Aktion rückgängig machen will, holt er sie aus dem Stapel. Wir können die Funktion schnell wie folgt simulieren:

Queues werden auch in der Programmierung häufig verwendet. Denken Sie an Spiele wie Street Fighter oder Super Smash Brothers. In diesen Spielen können die Spieler spezielle Bewegungen ausführen, indem sie eine Kombination von Tasten drücken. Diese Tastenkombinationen können in einer Warteschlange gespeichert werden.

Stellen Sie sich nun vor, dass Sie ein Entwickler sind, der an einem neuen Kampfspiel arbeitet. In Ihrem Spiel wird jedes Mal, wenn eine Taste gedrückt wird, ein Eingabeereignis ausgelöst. Einem Tester ist aufgefallen, dass, wenn die Tasten zu schnell gedrückt werden, das Spiel nur die erste Taste verarbeitet und die Spezialbewegungen nicht funktionieren!

Das kann man mit einer Warteschlange beheben. Wir können alle Eingabeereignisse in eine Warteschlange stellen, sobald sie eintreffen. Auf diese Weise macht es nichts aus, wenn Eingabeereignisse mit wenig Zeit dazwischen kommen, sie werden alle gespeichert und sind für die Verarbeitung verfügbar. Wenn wir die Züge verarbeiten, können wir sie aus der Warteschlange nehmen. Ein spezieller Zug kann folgendermaßen ausgeführt werden:

Schlussfolgerung

Stapel und Warteschlangen sind einfache Datenstrukturen, die es uns ermöglichen, Daten nacheinander zu speichern und abzurufen. 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 einem Stapel Elemente mit der Operation push hinzufügen und Elemente mit der Operation pop abrufen. Bei Warteschlangen fügen wir Elemente mit der enqueue-Operation hinzu und holen Elemente mit der dequeue-Operation 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 Stack- und Queue-Operationen in einem Objekt bereitstellen kann. Schließlich haben wir unsere Stack- und Queue-Klassen erstellt, um unsere Daten besser kontrollieren zu können.

Es gibt viele reale Anwendungsfälle für Stacks und Queues, und wenn wir sie verstehen, können wir viele Probleme der Datenspeicherung auf einfache und effektive Weise lösen.