Datenstrukturen: Stack und Queue

Hallo! Heute werden wir über etwas sprechen, das für jeden Programmierer äußerst wichtig ist: Datenstrukturen. Wikipedia sagt: „Eine Datenstruktur ist ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. Datenstrukturen sind nicht nur durch die enthaltenen Daten charakterisiert, sondern vor allem durch die Operationen auf diesen Daten, die Zugriff und Verwaltung ermöglichen und realisieren.“ Die Definition ist etwas verwirrend, aber das Wesentliche ist klar. Eine Datenstruktur ist eine Art Aufbewahrungsort, an dem wir Daten zur späteren Verwendung speichern. In der Programmierung gibt es eine große Vielfalt an Datenstrukturen. Bei der Lösung bestimmter Probleme kommt es oft darauf an, die am besten geeignete Datenstruktur für das Problem zu wählen. Und viele von ihnen kennst du bereits! Du kennst dich zum Beispiel mit Arrays aus. Und du kennst dich auch mit Map aus (diese Datenstruktur kann auch als „Wörterbuch“ oder „assoziatives Array“ bezeichnet werden). Es ist sehr wichtig zu verstehen, dass Datenstrukturen nicht an eine bestimmte Sprache gebunden sind. Sie sind vielmehr abstrakte „Entwürfe“, die jede Programmiersprache zur Erstellung ihrer eigenen Klassen oder zur Implementierung einer bestimmten Struktur verwenden kann. Eine der bekanntesten Datenstrukturen ist zum Beispiel eine verkettete Liste. Auf Wikipedia kannst du nachlesen, wie sie funktioniert und welche Vor- und Nachteile sie hat. Vielleicht kommt dir die Definition bekannt vor :) „Eine verkettete Liste ist eine lineare Sammlung von Datenelementen, deren Reihenfolge nicht durch ihre physische Anordnung im Speicher bestimmt ist. Stattdessen verweist jedes Element auf das nächste.“ Das beschreibt unsere geliebte LinkedList, nicht wahr? Ja, und genau das ist es auch :) In Java wird die Datenstruktur „verkettete Liste“ durch die Klasse LinkedList implementiert. Aber auch andere Sprachen implementieren verkettete Listen! In Python wird diese Datenstruktur „llist“ genannt. In Scala heißt sie „LinkedList“, genau wie in Java. Die verkettete Liste ist eine der grundlegenden und gebräuchlichsten Datenstrukturen und daher in jeder modernen Programmiersprache implementiert. Das Gleiche gilt für assoziative Arrays. Hier die Definition aus der Wikipedia: „Ein assoziatives Array – auch Zuordnungstabelle oder Wörterbuch/Dictionary – ist ein abstrakter Datentyp, der aus einer Sammlung von (Schlüssel-, Wert-)Paaren besteht, so dass jeder mögliche Schlüssel höchstens einmal in der Sammlung vorkommt.“ Erinnert dich das an etwas? :) Klar. Für uns Java-Entwickler ist ein assoziatives Array das Map-Interface. Aber diese Datenstruktur ist auch in anderen Sprachen implementiert! C#-Programmierer kennen es zum Beispiel unter dem Namen „Dictionary“. Und in Ruby ist sie in einer Klasse namens „Hash“ implementiert. Nun, du verstehst schon: Datenstrukturen sind universelle Konzepte in der Programmierung, und jede Programmiersprache implementiert sie auf ihre eigene Weise. Heute werden wir zwei solcher Strukturen untersuchen – Stack und Queue – und sehen, wie sie in Java implementiert sind.

Stacks in Java

Ein Stack ist eine bekannte Datenstruktur. Er ist sehr simpel. Viele Dinge in unserem täglichen Leben werden als Stack (dt. Stapel) „implementiert“. Stell dir diese einfache Situation vor: Du wohnst in einem Hotel und hast im Laufe des Tages einige Geschäftsbriefe erhalten. Du warst zu der Zeit nicht in deinem Zimmer, also hat der Hotelangestellte die eingehenden Briefe einfach auf deinen Schreibtisch gelegt. Zuerst legte er den ersten Brief auf den Schreibtisch. Dann kam ein zweiter Brief und er legte ihn auf den ersten. Er legte den dritten Brief auf den zweiten und den vierten auf den dritten. Und jetzt beantworte eine einfache Frage: Welchen Brief wirst du zuerst lesen, wenn du in dein Zimmer zurückkommst und den Stapel auf dem Tisch siehst? Richtig, du wirst den obersten Brief lesen. Das heißt, denjenigen, der zuletzt auf den Stapel gelegt wurde. Genau so funktioniert ein Stack. Dieses Prinzip wird „Last In First Out“ (LIFO) genannt. Wozu sind Stacks gut? Angenommen, du entwickelst eine Art Kartenspiel in Java. Ein Kartenspiel liegt auf dem Tisch. Die gespielten Karten werden abgelegt. Du kannst zwei Stacks verwenden, um sowohl den Nachziehstapel als auch den Ablagestapel zu implementieren. Die Spieler nehmen immer die oberste Karte und folgen dabei dem gleichen Prinzip wie bei den Geschäftsbriefen. Wenn die Spieler Karten auf den Ablagestapel legen, werden die neu abgelegten Karten auf die alten gelegt. Hier ist unser erster Versuch, das Spiel auf der Basis eines Stacks zu implementieren:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       discardPile.push(card);
   }

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

Wie bereits erwähnt, haben wir zwei Stacks: einen Nachziehstapel und einen Ablagestapel. In Java ist die Stack-Datenstruktur in der Klasse java.util.Stack implementiert. Unser Kartenspiel hat 3 Methoden, die die Aktionen der Spieler beschreiben:

• eine Karte vom Stapel nehmen (getCardFromDeck()-Methode
• eine Karte ablegen (discard()-Methode)
• die oberste Karte anschauen (lookAtTopCard()-Methode). Angenommen, es gibt einen „Intelligenz“-Bonus. Dieser erlaubt es dem Spieler herauszufinden, welche Karte als nächstes ins Spiel kommt.

Innerhalb unserer Methoden rufen wir die folgenden Methoden der Stack-Klasse auf:

• push() – fügt ein Element oben auf dem Stack hinzu. Wenn wir eine Karte auf den Ablagestapel legen, kommt sie oben auf den Stapel
• pop() – entfernt das oberste Element vom Staack und gibt es zurück. Diese Methode ist perfekt, um Aktionen durchzuführen, bei denen der Spieler eine Karte zieht.
• peek() – gibt das oberste Element des Stacks zurück, entfernt es aber nicht vom Stack.

Schauen wir mal, wie unser Spiel funktionieren wird:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

Wir haben fünf Karten zu unserem Kartenstapel hinzugefügt. Der erste Spieler hat 3 von ihnen genommen. Welche Karten hat sie bekommen? Konsolenausgabe:

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

Achte auf die Reihenfolge, in der die Karten auf der Konsole angezeigt werden. Die Karte „Edwin VanCleef“ kam als letzte auf den Stapel (sie war die fünfte Karte), und sie war die Karte, die der Spieler zuerst gezogen hat. „Millhouse“ war der vorletzte im Stapel und der Spieler zog ihn als zweiten. "Sylvanas" kam als dritte Karte von oben auf den Stapel und war die dritte Karte, die der Spieler gezogen hat. Als nächstes legt der Spieler Karten ab. Zuerst wird Edwin abgelegt, dann Millhouse und dann Sylvanas. Dann geben wir die Karten in unserem Ablagestapel eine nach der anderen aus: Konsolenausgabe:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

Wieder einmal sehen wir, wie ein Stack funktioniert! In unserem Spiel ist der Ablagestapel auch ein Stack (genau wie der Nachziehstapel). „Edwin VanCleef“ wurde als erstes abgelegt. Die zweite Karte, die abgelegt wurde, war Millhouse Manastorm, und sie wurde auf Edwin im Ablagestapel gelegt. Dann wurde Sylvanas abgelegt, und diese Karte wurde auf Millhouse gelegt. Wie du siehst, ist an einem Stack nichts Kompliziertes. Dennoch ist es wichtig, diese Datenstruktur zu kennen, da sie häufig in Vorstellungsgesprächen abgefragt wird und oft die Grundlage für den Aufbau komplexerer Datenstrukturen bildet.

Queue in Java

Eine Queue (dt. Warteschlange) ist eine weitere gängige Datenstruktur. Neben Stacks implementieren viele Programmiersprachen, darunter auch Java, auch die Queue-Datenstruktur. Was ist der Unterschied zwischen einer Queue und einem Stack? Eine Queue basiert nicht auf dem LIFO-Prinzip, sondern auf dem FIFO-Prinzip („First In, First Out“). Dieses Prinzip ist leicht zu verstehen, wenn du dir zum Beispiel eine gewöhnliche Warteschlange im echten Leben ansiehst! Zum Beispiel eine Schlange im Supermarkt. Wenn fünf Personen in der Schlange stehen, wird derjenige zuerst bedient, der sich zuerst in die Schlange gestellt hat. Wenn eine weitere Person (zusätzlich zu den fünf, die bereits in der Schlange stehen) etwas kaufen möchte und sich anstellt, wird sie als letzte, also als sechste bedient. Wenn du mit einer Warteschlange arbeitest, werden neue Elemente am Ende (hinten) hinzugefügt, und wenn du ein Element holen willst, wird es vom Kopf (vorne) genommen. Das ist das wichtigste Prinzip, das du dir merken musst, wenn du wissen willst, wie eine Queue funktioniert. Die Funktionsweise einer Queue ist sehr intuitiv, da wir im wirklichen Leben häufig auf Warteschlangen treffen. Es ist zu beachten, dass in Java eine Warteschlange nicht durch eine Klasse, sondern durch ein Interface repräsentiert wird: Queue. Außerdem gibt es viele Implementierungen dieses Queue-Interfaces in Java. Wenn wir uns die Oracle-Dokumentation ansehen, werden wir feststellen, dass vier verschiedene Interfaces sowie eine äußerst beeindruckende Liste von Klassen das Queue-Interface erben:

All known subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All known implementing classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Was für eine lange Liste! Aber natürlich musst du dir all diese Klassen und Interfaces nicht sofort merken – dein Kopf könnte sonst explodieren :) Wir werden nur ein paar der wichtigsten und interessantesten Punkte betrachten. Schauen wir uns zunächst eines der vier „Sub-Interfaces“ von Queue an: Deque. Was macht sie so besonders? Eine Deque ist eine Warteschlange mit zwei Enden. Sie erweitert die Funktionalität einer normalen Warteschlange und ermöglicht es dir, Elemente an beiden Enden (am Kopf und am Ende) hinzuzufügen und Elemente von beiden Enden der Warteschlange zu nehmen. Doppelendige Warteschlangen sind in der Softwareentwicklung weit verbreitet. Beachte die Liste der Queue-Klassen, die wir oben angegeben haben. Die Liste ist ziemlich lang, aber kommt dir etwas bekannt vor?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Hier ist unser alter Freund LinkedList! Sie implementiert also das Queue-Interface? Aber wie kann sie eine Warteschlange sein? Schließlich ist eine LinkedList eine verkettete Liste! Stimmt, aber das hindert sie nicht daran, eine Warteschlange zu sein :) Hier ist eine Liste aller Interfaces, die sie implementiert:

All implemented interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Wie du siehst, implementiert LinkedList das Deque-Interface (was wiederum bedeutet, dass es sich um eine Warteschlange mit zwei Enden handelt). Warum ist das notwendig? So können wir Elemente vom Anfang und vom Ende einer LinkedList abrufen. Außerdem können wir Elemente am Anfang und Ende hinzuzufügen. Hier sind die Methoden, die LinkedList vom Deque-Interface erhält:

• peekFirst() – gibt das erste Element zurück (entfernt es aber nicht aus der Warteschlange).
• peekLast() – gibt das letzte Element zurück (entfernt es aber nicht aus der Warteschlange).
• pollFirst() – gibt das erste Element aus der Warteschlange zurück und entfernt es.
• pollLast() – gibt das letzte Element aus der Warteschlange zurück und entfernt es.
• addFirst() – fügt ein neues Element am Anfang der Warteschlange hinzu.
• addLast() – fügt ein Element am Ende der Warteschlange hinzu.

Wie du siehst, implementiert LinkedList die Funktionalität einer Warteschlange mit zwei Enden! Und wenn du solche Funktionen in deinem Programm brauchst, wirst du wissen, wo du sie findest :) Die heutige Lektion neigt sich dem Ende zu. Zum Schluss gebe ich dir noch ein paar Links für die weitere Lektüre. Schau dir zuerst diesen Artikel über PriorityQueue an. Dies ist eine der interessantesten und nützlichsten Queue-Implementierungen. Angenommen, in deinem Laden stehen 50 Leute an und 7 von ihnen sind VIP-Kunden. Mit einer PriorityQueue kannst du sie zuerst bedienen! Sehr nützlich, nicht wahr? :) Zweitens kann es nicht schaden, noch einmal Robert Lafores Buch „Data Structures and Algorithms in Java“ zu erwähnen. Wenn du dieses Buch liest, lernst du nicht nur viele Datenstrukturen kennen (einschließlich Stack und Queue), sondern du wirst auch viele davon selbst implementieren! Was wäre zum Beispiel, wenn es in Java keine Stack-Klasse gäbe? Was würdest du tun, wenn du eine solche Datenstruktur für dein Programm brauchst? Du müsstest sie natürlich selbst schreiben. Wenn du Lafores Buch liest, wirst du oft genau das tun. Auf diese Weise wird dein Verständnis von Datenstrukturen viel tiefer gehen, als wenn du nur die Theorie studierst :) Wir schließen die Theorie für heute ab, aber Theorie ohne Praxis ist nichts! Die Aufgaben lösen sich nicht von selbst, also ist es an der Zeit, sie anzupacken! :)