Schlange und Stapel


Die Datenstruktur Schlange

Die Datenstruktur Schlange (Queue) wird verwendet, wenn Datenobjekte, die als erstes der Schlange hinzugefügt wurden, auch als erstes aus der Schlange entfernt werden sollen. Dieses Prinzip nennt man FIFO (First In, First Out).

Beispiele sind Druckerwarteschlange, Containerabhol-Lastwagenschlange, Schlange an der Supermarktkasse,...

Um die Datenstruktur Schlange zu realisieren, brauchen wir Funktionen (Methoden), mit denen das FIFO-Prinzip in einem Programm umgesetzt werden kann. Die Daten selbst werden wir im folgenden in einem Array (Datenfeld) speichern.

Im folgenden Beispielprogramm können Sie Datenobjekte aus dem Array entfernen, indem Sie mit der linken Maustaste klicken (das erste Element wird entfernt) oder indem Sie mit der rechten Maustaste klicken (das letzte Element wird entfernt). Als Programmierer haben Sie die Freiheit, die Daten so zu verwalten, wie Sie wollen. Wenn die FIFO-Eigenschaft von Ihrem Programm erfüllt wird, kann man die Datenstruktur eine Schlange (Queue) nennen.

JavaScript bietet Funktionen (Methoden) an, mit denen das erste oder das letzte Element eines Arrays entfernt werden kann:

  • shift() entfernt das erste Element eines Arrays
  • pop() entfernt das letzte Element eines Arrays

Wenn der Wert des zu entfernenden Elements weiter verwendet werden soll, kann man vor dem Entfernen den Wert einer anderen Variable zuordnen:

let zuentfernenderWert = schlangeArray.pop(); 

oder

let zuentfernenderWert = schlangeArray.shift(); 

Damit kann man das zu entfernende Element noch einmal anzeigen lassen:


Im folgenden Beispiel soll ein Zeichen, das mit der Tastatur eingegeben wird einer Schlange hinzugefügt werden. Bei einem Mausklick mit der linken Maustaste soll das zuerst eingegebene Zeichen wieder entfernt werden.

Neu ist die Funktion keyPressed():

function keyPressed() {
  schlangeArray.push(`${key}`);
}

Sobald eine Taste auf der Tastatur gedrückt wird, wird diese Funktion aufgerufen. Mit dem Befehl push() wird ein Element an das Ende der Schlange angefügt und ${key} gibt das Zeichen aus, das für die p5-Bibliothek zu der gedrückten Taste gehört.

Neu ist auch die Abfrage if(schlangeArray.length > 0). Es macht nur Sinn ein Element aus der Schlange zu entfernen, wenn die Schlange nicht leer ist. Mit schlangeArray.length holt man die Anzahl der Elemente im Array schlangeArray und prüft, ob diese Anzahl größer ist als 0.

Die Funktionen (Methoden, Operationen), die man zur Verarbeitung einer Schlange verwendet, sind also folgende:

  • push(element): fügt ein neues Element an das Ende der Schlange hinzu,
  • shift(): entfernt das erste Element der Schlange,
  • zuentfernenderWert = schlangeArray.shift(): falls die Schlange nicht leer ist, ordnet man der Variablen den Wert des ersten Elements zu und entfernt dieses dann aus der Schlange,
  • if(schlangeArray.length > 0) { ... }: damit prüft man, ob die Schlange leer ist.

Die Datenstruktur Stapel

Die Datenstruktur Stapel (Stack) wird verwendet, wenn Datenobjekte, die als erstes dem Stapel hinzugefügt wurden, als letztes aus dem Stapel entfernt werden sollen. Daraus folgt, dass Objekte die als letztes dem Stapel hinzugefügt werden, als erstes dem Stapel entnommen werden sollen. Dieses Prinzip nennt man FILO (First In, Last Out) bzw. LIFO (Last In, First Out).

Beispiele sind Tellerstapel, Aktenstapel, Rechenreihenfolge bei Rechentermen,...

Um die Datenstruktur Stapel zu realisieren, brauchen wir Funktionen (Methoden), mit denen das LIFO-Prinzip in einem Programm umgesetzt werden kann.

Um einen Stapel zu realisieren muss beim letzten Programm nur eine einzige Zeile geändert werden:

Aus zuentfernenderWert = stapelArray.shift(); wird zuentfernenderWert = stapelArray.pop();.

Damit wird das letzte Element des Arrays entfernt und das ist das Element, das als Letztes dem Array hinzugefügt wurde. Das erste hinzugefügte Element wird als letztes aus dem Array entfernt. Damit haben wir unseren Stapel.

Die Funktionen (Methoden, Operationen), die man zur Verarbeitung eines Stapels verwendet, sind also folgende:

  • push(element): legt ein neues Element auf den Stapel,
  • pop(): entfernt das oberste Element des Stapels,
  • zuentfernenderWert = stapelArray.pop(): falls der Stapel nicht leer ist, ordnet man der Variablen den Wert des letzten Elements zu und entfernt diesen dann aus dem Stapel,
  • if(stapelArray.length > 0) { ... }: damit prüft man, ob der Stapel leer ist.

Projekt: Visuelle Darstellung von Schlange und Stapel

Aufgabe:

Programmieren Sie mit p5.js ein oder zwei Programme, mit denen die Datenstrukturen Schlange und Stapel grafisch veranschaulicht werden können. Wenn Sie möchten, können Sie als Ausgangspunkt für Ihr Projekt eines der beiden folgenden Beispielprogramme verwenden.

Die Farbnamen finden Sie z.B. auf folgender Internetseite: Farbnamen.


Beispielprogramm zur Visualisierung der Datenstruktur Schlange. Drücken Sie eine Taste, um der Schlange ein neues Element hinzuzufügen. Klicken Sie mit der linken Maustaste, um ein Element zu entfernen.


Beispielprogramm zur Visualisierung der Datenstruktur Stapel. Drücken Sie eine Taste, um dem Stapel ein neues Element hinzuzufügen. Klicken Sie mit der linken Maustaste, um ein Element zu entfernen.


Lösungsvorschlag von Henrik, Chris, Jendrik

Anleitung: Klicken Sie zuerst mit der Maus auf die Zeichenfläche, damit der Fokus auf der Zeichenfläche ist. Drücken Sie dann wiederholt die linke Pfeiltaste um Flugnummern der Flugliste hinzuzufügen. Wenn Sie die rechte Pfeiltaste drücken, werden Flugnummern aus der Liste entfernt.