Datenstrukturen in Java – Stack und Queue

Hallo! Heute werden wir über so wichtige Dinge für jeden Programmierer wie Datenstrukturen sprechen . Wikipedia sagt: Datenstruktur ( engl. Datenstruktur ) ist eine Softwareeinheit, die es Ihnen ermöglicht, viele gleichartige und/oder logisch verwandte Daten in der Informatik zu speichern und zu verarbeiten. Die Definition ist etwas verwirrend, aber ihr Kern ist klar. Eine Datenstruktur ist eine Art Speicher, in dem wir Daten zur weiteren Verwendung speichern. In der Programmierung gibt es eine große Vielfalt an Datenstrukturen. Sehr oft kommt es bei der Lösung eines konkreten Problems vor allem darauf an, die für diesen Zweck am besten geeignete Datenstruktur auszuwählen. Und viele davon kennen Sie bereits! Zum Beispiel mit Arrays . Und auch mit Map(was normalerweise als „Wörterbuch“, „Karte“ oder „assoziatives Array“ übersetzt wird). Es ist sehr wichtig zu verstehen: Datenstrukturen sind nicht an eine bestimmte Sprache gebunden . Hierbei handelt es sich lediglich um abstrakte „Blaupausen“, nach denen jede Programmiersprache ihre eigenen Klassen erstellt – Implementierungen dieser Struktur. Eine der bekanntesten Datenstrukturen ist beispielsweise die verknüpfte Liste . Sie können auf Wikipedia nachlesen, wie es funktioniert und welche Vor- und Nachteile es hat. Die Definition kommt Ihnen vielleicht bekannt vor :) „Eine verknüpfte Liste ist eine grundlegende dynamische Datenstruktur in der Informatik, die aus Knoten besteht, von denen jeder sowohl die Daten selbst als auch einen oder zwei Links („Links“) zum nächsten und/oder enthält vorherige Knotenliste“ Das ist also unser LinkedList! Genau so ist es :) Die Datenstruktur der verknüpften Liste ist in der Java-Sprache in der Klasse implementiert LinkedList. Aber auch andere Sprachen implementieren verknüpfte Listen! In Python heißt es „ llist“, in Scala heißt es genauso wie in Java – „ LinkedList“. Eine verknüpfte Liste ist eine der grundlegenden gemeinsamen Datenstrukturen, sodass Sie ihre Implementierung in jeder modernen Programmiersprache finden können. Das Gleiche gilt für ein assoziatives Array. Hier ist die Definition aus Wikipedia: Ein assoziatives Array ist ein abstrakter Datentyp (eine Schnittstelle zu einem Datenspeicher), der das Speichern von Paaren der Form „(Schlüssel, Wert)“ ermöglicht und das Hinzufügen eines Paares sowie das Suchen unterstützt und Löschen eines Paares per Schlüssel. Erinnert Sie an nichts? :) Genau, für uns Javaisten ist ein assoziatives Array eine SchnittstelleMap. Aber diese Datenstruktur ist auch in anderen Sprachen implementiert! C#-Programmierer kennen es beispielsweise unter dem Namen „Dictionary“. Und in der Ruby-Sprache ist es in einer Klasse namens „Hash“ implementiert. Im Allgemeinen verstehen Sie ungefähr, was die Bedeutung ist: Eine Datenstruktur ist etwas, das jeder Programmierung gemeinsam ist und in jeder spezifischen Sprache unterschiedlich implementiert wird. Heute werden wir zwei solcher Strukturen untersuchen und sehen, wie sie in Java implementiert werden – Stack und Queue.

Stapel in Java

Ein Stapel ist eine bekannte Datenstruktur. Es ist ganz einfach und viele Gegenstände aus unserem täglichen Leben werden als Stapel „implementiert“. Stellen Sie sich eine einfache Situation vor: Sie wohnen in einem Hotel und erhalten tagsüber Geschäftsbriefe. Da Sie zu diesem Zeitpunkt nicht im Zimmer waren, legte Ihnen der Hotelmitarbeiter die eingehenden Briefe einfach auf den Tisch. Zuerst legte er den ersten Buchstaben auf den Tisch. Dann kam der zweite und legte ihn auf den ersten. Den dritten angekommenen Brief legte er auf den zweiten und den vierten auf den dritten. Beantworten Sie nun eine einfache Frage: Welchen Buchstaben werden Sie zuerst lesen , wenn Sie in Ihr Zimmer kommen und einen Stapel auf dem Tisch sehen? Das ist richtig, Sie werden den obersten Buchstaben lesen. Das heißt, derjenige, der zeitlich zuletzt kam . Genau so funktioniert ein Stack. Dieses Funktionsprinzip nennt sich LIFO – „Last In – First Out“ („Last In, First Out“). Wozu kann ein Stack nützlich sein? Sie erstellen beispielsweise eine Art Kartenspiel in Java. Auf dem Tisch liegt ein Kartenspiel. Ausgespielte Karten werden abgeworfen. Sie können sowohl den Stapel als auch den Abwurf mithilfe von zwei Stapeln umsetzen. Die Spieler ziehen Karten von oben vom Stapel – das gleiche Prinzip wie bei den Buchstaben. Wenn Spieler Karten abwerfen, werden neue Karten auf die alten gelegt. So würde der erste Entwurf unseres Spiels aussehen, implementiert mit einem Stack:

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 {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

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

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

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

Wie bereits erwähnt, haben wir zwei Stapel: den Stapel und den Ablagestapel. Die Stack-Datenstruktur ist in Java im implementiert java.util.Stack. In unserem Kartenspiel gibt es 3 Methoden, die die Aktionen der Spieler beschreiben:

• eine Karte vom Stapel nehmen (Methode getCardFromDeck());
• Karte abwerfen (Methode discard());
• Schauen Sie sich die oberste Karte an (Methode lookTopCard()). Nehmen wir an, dass es sich um die Bonusmechanik „Intelligenz“ handelt, die es dem Spieler ermöglicht, herauszufinden, welche Karte als nächstes ins Spiel kommt.

Innerhalb unserer Methoden werden Klassenmethoden aufgerufen Stack:

• push()– Fügt ein Element oben im Stapel hinzu. Wenn wir eine Karte abwerfen, wird sie auf die zuvor abgeworfenen Karten gelegt;
• pop()– Entfernt das oberste Element vom Stapel und gibt es zurück. Diese Methode ist ideal für die Implementierung der Mechanik „Spieler zieht eine Karte“.
• peek()– gibt das oberste Element des Stapels zurück, entfernt es jedoch nicht vom Stapel

Mal sehen, wie unser Spiel funktionieren wird:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

Deshalb haben wir unserem Deck fünf Karten hinzugefügt. Der erste Spieler nahm 3 davon. Welche Karten hat er bekommen? Konsolenausgabe:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

Achten Sie auf die Reihenfolge, in der die Karten an die Konsole ausgegeben wurden. Die „Edwin Van Cleiff“-Karte war die letzte, die auf den Stapel kam (fünfte in Folge), und es war die Karte, die der Spieler zuerst nahm. „Michhlaus“ war der vorletzte Spieler auf dem Deck, und sein Spieler belegte den zweiten Platz. „Sylvanas“ landete als Dritter am Ende auf dem Deck und ging an den dritten Spieler. Als nächstes wirft der Spieler seine Karten ab. Zuerst lässt er Edwin fallen, dann Millhouse, dann Sylvanas. Danach geben wir nacheinander die Karten, die sich in unserem Abwurf befinden, an die Konsole aus: Ausgabe an die Konsole:

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

Und wieder sehen wir, wie der Stapel funktioniert! Der Abwurf in unserem Spiel ist ebenfalls ein Stapel (genau wie der Stapel). „Edwin Van Clyffe“ war der erste, der gestrichen wurde. Der zweite, der fallen gelassen wurde, war „Millhouse Manastorm“ – und lag im Abwurf auf Edwin. Als nächstes wurde Sylvanas abgeworfen – und diese Karte lag auf Millhouse. Wie Sie sehen, ist die Funktionsweise des Stapels nicht kompliziert. Es ist jedoch notwendig, diese Datenstruktur zu kennen – sie wird in Interviews häufig gefragt und auf ihrer Grundlage werden häufig komplexere Datenstrukturen aufgebaut.

Warteschlange

Eine Warteschlange (oder auf Englisch „Queue“) ist eine weitere gängige Datenstruktur. Genau wie ein Stack ist es in vielen Programmiersprachen implementiert, darunter auch Java. Was ist der Unterschied zwischen einer Warteschlange und einem Stapel? Seine Warteschlange basiert nicht auf LIFO, sondern auf einem anderen Prinzip – FIFO („First In – First Out“, „First In – First Out“) . Es ist leicht zu verstehen, wenn man sich ein Beispiel nimmt ... oder zumindest eine gewöhnliche, echte Warteschlange aus dem wirklichen Leben! Zum Beispiel eine Warteschlange vor dem Laden. Stehen fünf Personen in der Schlange, betritt der erste den Laden . Wenn noch eine weitere Person (außer den fünf in der Schlange) etwas kaufen möchte und sich in die Schlange stellt, dann kommt sie als Letzter , also als Sechster, in den Laden. Wenn Sie mit einer Warteschlange arbeiten, werden neue Elemente am Ende hinzugefügt. Wenn Sie ein Element erhalten möchten, wird es vom Anfang übernommen. Dies ist das Grundprinzip seiner Funktionsweise, das Sie sich merken müssen. Das Prinzip der Warteschlange ist intuitiv sehr leicht zu verstehen, da es im wirklichen Leben oft anzutreffen ist. Es ist erwähnenswert, dass in Java eine Warteschlange nicht durch eine Klasse, sondern durch eine Schnittstelle dargestellt wird Queue. Aber gleichzeitig ist eine Warteschlange in Java eine Schnittstelle, die viele Implementierungen hat. Wenn wir uns die Oracle-Dokumentation ansehen, werden wir feststellen, dass 4 verschiedene Schnittstellen und eine äußerst beeindruckende Liste von Klassen von der Warteschlange geerbt werden:

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 große Liste! Aber natürlich müssen Sie sich jetzt nicht alle diese Klassen und Schnittstellen merken – Ihr Kopf könnte explodieren :) Wir werden uns nur einige der wichtigsten und interessantesten Punkte ansehen. Schauen wir uns zunächst eine der vier „Unterschnittstellen“ der Warteschlange an – Deque. Was ist das Besondere daran? Deque- Dies ist eine Zwei-Wege-Warteschlange. Es erweitert die Funktionalität einer regulären Warteschlange, indem es Ihnen ermöglicht, Elemente an beiden Enden (am Anfang und am Ende der Warteschlange) hinzuzufügen und Elemente von beiden Enden der Warteschlange zu übernehmen. Die Deque wird häufig in der Entwicklung verwendet. Beachten Sie die Liste der Warteschlangenklassen, die wir oben bereitgestellt haben. Die Liste ist ziemlich lang, aber gibt es dort etwas Bekanntes?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, unser alter Freund ist also hier LinkedList! Das heißt, es implementiert die Schnittstelle Queue? Aber wie kann er eine Warteschlange sein? Schließlich LinkedListhandelt es sich hier um eine zusammenhängende Liste! Stimmt, aber das hindert es nicht daran, eine Warteschlange zu sein :) Hier ist eine Liste aller Schnittstellen, die es implementiert:

All Implemented Interfaces:

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

Wie Sie sehen, LinkedListimplementiert es eine Schnittstelle Deque– eine bidirektionale Warteschlange. Warum ist das notwendig? Dadurch können wir Elemente sowohl vom Anfang als auch vom Ende erhalten LinkedList. Und außerdem – fügen Sie Elemente sowohl am Anfang als auch am Ende hinzu. Hier sind die LinkedListvon der Schnittstelle geerbten Methoden Deque:

• peekFirst()– gibt das erste Element zurück (entfernt es jedoch nicht aus der Warteschlange).
• peekLast()– gibt das letzte Element zurück (entfernt es jedoch 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 Sie sehen, LinkedListist die Funktionalität einer Zwei-Wege-Warteschlange vollständig implementiert! Und wenn eine solche Funktionalität im Programm benötigt wird, wissen Sie, dass sie genutzt werden kann :) Und unser heutiger Vortrag geht zu Ende. Abschließend gebe ich Ihnen noch ein paar Links zur weiteren Lektüre. Beachten Sie zunächst den Artikel über PriorityQueue – „Prioritätswarteschlange“. Dies ist eine der interessantesten und nützlichsten Implementierungen von Queue. Wenn in Ihrem Geschäft beispielsweise 50 Personen in der Schlange stehen und 7 davon VIP-Kunden sind, PriorityQueuekönnen Sie diese zuerst bedienen! Eine sehr nützliche Sache, finden Sie nicht auch? :) Zweitens wäre es nicht überflüssig, noch einmal Robert Laforets Buch „Data Structures and Algorithms in Java“ zu erwähnen . Beim Lesen des Buches lernen Sie nicht nur viele Datenstrukturen (einschließlich Stack und Queue) kennen, sondern werden viele davon auch selbst implementieren! Stellen Sie sich zum Beispiel vor, Java hätte keine Stack-Klasse. Was würden Sie tun, wenn Sie eine solche Datenstruktur für Ihr Programm benötigen würden? Natürlich müsste ich es selbst schreiben. Wenn Sie Laforets Buch lesen, werden Sie oft genau das tun. Dadurch wird Ihr Verständnis von Datenstrukturen viel umfassender sein, als wenn Sie nur die Theorie studieren :) Für heute sind wir mit der Theorie fertig, aber Theorie ohne Praxis ist nichts! Die Probleme lösen sich nicht von selbst, also ist es jetzt an der Zeit, sie anzugehen! :) :)