Datastructuren: stapel en rij

Hoi! Vandaag zullen we het hebben over iets dat super belangrijk is voor elke programmeur: datastructuren. Wikipedia zegt: "Een datastructuur is een gegevensorganisatie, -beheer en -opslagformaat dat efficiënte toegang en wijziging mogelijk maakt. Nauwkeuriger gezegd, een gegevensstructuur is een verzameling gegevenswaarden, de onderlinge relaties en de functies of bewerkingen die kunnen worden toegepast op de gegevens." De definitie is een beetje verwarrend, maar de essentie is duidelijk. Een datastructuur is een soort opslagplaats waar we gegevens opslaan voor toekomstig gebruik. Bij het programmeren is er een grote verscheidenheid aan gegevensstructuren. Bij het oplossen van specifieke problemen is het vaak het belangrijkste om de meest geschikte datastructuur voor het probleem te kiezen. En velen van hen ken je al! U weet bijvoorbeeld van arrays. En je bent ook bekend metMap(deze gegevensstructuur kan ook een "woordenboek" of "associatieve array" worden genoemd). Het is erg belangrijk om te begrijpen dat datastructuren niet gebonden zijn aan een bepaalde taal. Het zijn eenvoudigweg abstracte "blauwdrukken" die elke programmeertaal gebruikt om zijn eigen klassen of implementaties van een bepaalde structuur te creëren. Een van de bekendste datastructuren is bijvoorbeeld een gelinkte lijst. U kunt naar Wikipedia gaan en lezen hoe het werkt en welke voor- en nadelen het heeft. Misschien komt de definitie u bekend voor :) "Een gelinkte lijst is een lineaire verzameling gegevenselementen, waarvan de volgorde niet wordt bepaald door hun fysieke plaatsing in het geheugen. In plaats daarvan verwijst elk element naar het volgende." Dat beschrijft onze geliefde LinkedList, nietwaar? Ja, en dat is precies wat het is :) In Java wordt de "linked list" datastructuur geïmplementeerd door de LinkedListklasse. Maar ook andere talen implementeren gelinkte lijsten! In Python wordt deze datastructuur " llist" genoemd. In Scala heet het " LinkedList", net als op Java. Een gekoppelde lijst is een van de meest voorkomende gegevensstructuren, dus u zult merken dat deze in elke moderne programmeertaal is geïmplementeerd. Hetzelfde geldt voor associatieve arrays. Hier is de definitie van Wikipedia: "Een associatieve array, kaart, symbooltabel of woordenboek is een abstract gegevenstype dat is samengesteld uit een verzameling (sleutel-, waarde-)paren, zodat elke mogelijke sleutel maximaal één keer in de verzameling voorkomt." Doet dat je ergens aan denken? :) Jazeker. Voor ons Java-ontwikkelaars is een associatieve array deMapkoppel. Maar deze datastructuur is ook in andere talen geïmplementeerd! C#-programmeurs kennen het bijvoorbeeld onder de naam "Dictionary". En in Ruby is het geïmplementeerd in een klasse genaamd "Hash". Nou, je begrijpt het punt: datastructuren zijn universele concepten in programmeren en elke programmeertaal implementeert ze op zijn eigen manier. Vandaag zullen we twee van dergelijke structuren bestuderen - de stapel en de wachtrij - en kijken hoe ze in Java zijn geïmplementeerd.

Stapels in Java

Een stack is een bekende datastructuur. Het is erg makkelijk. Heel wat items in ons dagelijks leven worden als een stapel "geïmplementeerd". Stel je deze simpele situatie eens voor: je verblijft in een hotel en in de loop van de dag ontvang je zakelijke brieven. U was op dat moment niet in uw kamer, dus de hotelreceptionist legde de binnenkomende brieven gewoon op uw bureau. Eerst legde hij de eerste brief op het bureau. Toen kwam er een tweede brief en hij legde die bovenop de eerste. Hij legde de derde letter boven op de tweede en de vierde boven op de derde. En beantwoord nu een simpele vraag: welke letter lees je als eerste als je terugkomt in je kamer en de stapel op tafel ziet liggen? Juist, u leest de bovenstebrief. Dat wil zeggen, degene die het laatst is aangekomen . Dit is precies hoe een stapel werkt. Dit principe wordt "last in, first out" (LIFO) genoemd . Waar zijn stapels goed voor? Nou, stel dat je een soort kaartspel maakt in Java. Op tafel ligt een pak kaarten. De gespeelde kaarten worden afgelegd. Je kunt twee stapels gebruiken om zowel de trekstapel als de aflegstapel te implementeren. Spelers nemen hun kaarten van de bovenkant van de stapel, volgens hetzelfde principe als bij uw zakelijke brieven. Wanneer spelers kaarten op de aflegstapel leggen, worden de nieuw weggegooide kaarten bovenop de oude gelegd. Dit is onze eerste poging tot het spel, geïmplementeerd op basis van een stapel:

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.
}

Zoals we eerder zeiden, hebben we twee stapels: een trekstapel en een aflegstapel. In Java is de stapelgegevensstructuur geïmplementeerd in de java.util.Stackklasse. Ons kaartspel heeft 3 methoden die de acties van de spelers beschrijven:

• een kaart uit de stapel nemen ( getCardFromDeck()methode)
• een kaart afleggen ( discard()methode)
• kijk naar de bovenste kaart ( lookAtTopCard()methode). Laten we zeggen dat dit een "Intelligentie"-bonus is waarmee de speler kan uitzoeken welke kaart als volgende in het spel komt.

Binnen onze methoden noemen we de volgende methoden van de klasse Stack:

• push()- voegt een item toe aan de bovenkant van de stapel. Als we een kaart naar de aflegstapel sturen, gaat deze naar de top van de stapel
• pop()— verwijdert het bovenste element van de stapel en geeft het terug. Deze methode is perfect voor het uitvoeren van acties waarbij de speler een kaart trekt.
• peek()— retourneert het bovenste element van de stapel, maar verwijdert het niet van de stapel

Laten we eens kijken hoe ons spel zal werken:

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());
   }
}

We hebben vijf kaarten aan ons kaartspel toegevoegd. De eerste speler nam er 3. Welke kaarten heeft ze gekregen? Console-uitvoer:

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

Let op de volgorde waarin de kaarten op de console worden weergegeven. De "Edwin VanCleef"-kaart ging als laatste in de stapel (het was de vijfde kaart), en het was de kaart die de speler als eerste trok. "Millhouse" was als een na laatste in het kaartspel en de speler trok het als tweede. "Sylvanas" ging als derde van boven in het kaartspel en het was de derde kaart die de speler trok. Vervolgens legt de speler kaarten af. Eerst legt ze Edwin af, dan Millhouse en dan Sylvanas. Vervolgens tonen we de kaarten in onze aflegstapel één voor één: Console-uitvoer:

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

Nogmaals, we zien hoe een stapel werkt! In ons spel is de aflegstapel ook een stapel (net als de trekstapel). "Edwin VanCleef" werd als eerste weggegooid. De tweede weggegooide kaart was Millhouse Manastorm en werd bovenop Edwin op de aflegstapel gelegd. Daarna werd Sylvanas afgelegd en deze kaart werd bovenop Millhouse gelegd. Zoals je kunt zien, is er niets ingewikkelds aan een stapel. Toch moet u deze datastructuur kennen - er wordt vaak naar gevraagd tijdens sollicitatiegesprekken en het is vaak de basis voor het bouwen van complexere datastructuren.

Wachtrij in Java

Een wachtrij is een andere veel voorkomende gegevensstructuur. Naast stacks implementeren veel programmeertalen, waaronder Java, ook de wachtrijgegevensstructuur. Wat is het verschil tussen een wachtrij en een stapel? Een wachtrij is niet gebaseerd op het LIFO-principe, maar op het FIFO-principe ("first in, first out"). Dit principe is gemakkelijk te begrijpen door bijvoorbeeld een gewone lijn of wachtrij in het echte leven te beschouwen! Bijvoorbeeld een rij bij de supermarkt. Als er vijf mensen in de rij staan, is de eerste die bediend wordt degene die als eerste in de rij is gekomen . Als een andere persoon (naast vijf die al in de rij staan) iets wil kopen en in de rij gaat staan, dan wordt hij als laatste bediend, dat wil zeggen zesde. Wanneer u met een wachtrij werkt, worden nieuwe elementen aan de staart (achterkant) toegevoegd en als u een element wilt krijgen, wordt dit vanaf de kop (voorkant) genomen. Dit is het belangrijkste principe dat u moet onthouden over hoe een wachtrij werkt. De bediening van een wachtrij is zeer intuïtief, aangezien we wachtrijen vaak in het echte leven tegenkomen. Het is vermeldenswaard dat in Java een wachtrij niet wordt weergegeven door een klasse, maar door een interface: Queue. Bovendien zijn er veel implementaties van deze wachtrij-interface in Java. Als we naar de Oracle-documentatie kijken, zullen we zien dat 4 verschillende interfaces, evenals een buitengewoon indrukwekkende lijst met klassen, de Queue-interface erven:

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

Wat een grote lijst! Maar je hoeft natuurlijk niet al deze klassen en interfaces nu uit je hoofd te leren - je hoofd zou kunnen ontploffen :) We zullen alleen een paar van de belangrijkste en interessantste punten bespreken. Laten we eerst eens kijken naar een van de vier "subinterfaces" van Queue: Deque . Wat maakt het zo speciaal? A Dequeis een wachtrij met twee uiteinden. Het breidt de functionaliteit van een gewone wachtrij uit, waardoor u elementen aan beide uiteinden (aan de kop en de staart) kunt toevoegen en elementen van beide uiteinden van de wachtrij kunt nemen. Double-ended wachtrijen worden veel gebruikt bij softwareontwikkeling. Let op de lijst met wachtrijklassen die we hierboven hebben gegeven. De lijst is vrij lang, maar staat er iets bekends in?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Hier is onze oude vriend LinkedList! Dus het implementeert de wachtrij-interface? Maar hoe kan het een wachtrij zijn? A is immers LinkedListeen gelinkte lijst! Klopt, maar dat neemt niet weg dat het een wachtrij is :) Hier is een lijst van alle interfaces die het implementeert:

All implemented interfaces:

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

Zoals u kunt zien, LinkedListimplementeert de Dequeinterface (nogmaals, dit betekent dubbele wachtrij). Waarom is dit nodig? Hierdoor kunnen we elementen van het begin en het einde van een LinkedList. Het stelt ons ook in staat om elementen aan het begin en einde toe te voegen. Dit zijn de methoden die LinkedListuit de interface komen Deque:

• peekFirst()— geeft het eerste element terug (maar verwijdert het niet uit de wachtrij).
• peekLast()— geeft het laatste element terug (maar verwijdert het niet uit de wachtrij).
• pollFirst()— retourneert het eerste element uit de wachtrij en verwijdert het.
• pollLast()— retourneert het laatste item uit de wachtrij en verwijdert het.
• addFirst()- voegt een nieuw item toe aan de voorkant van de wachtrij.
• addLast()— voegt een item toe aan het einde van de wachtrij.

Zoals u kunt zien, LinkedListimplementeert het de functionaliteit van een dubbele wachtrij volledig! En je hebt zulke functionaliteit nodig in je programma, je weet waar je het kunt vinden :) De les van vandaag loopt ten einde. Tot slot zal ik u een aantal links geven voor meer informatie. Let eerst op dit artikel over PriorityQueue . Dit is een van de meest interessante en nuttige Queueimplementaties. Stel dat er 50 mensen in de rij staan ​​te wachten bij uw winkel, en 7 van hen zijn VIP-klanten. Met een PriorityQueue kunt u ze als eerste bedienen! Zeer nuttige dingen, toch? :) Ten tweede zou het geen kwaad om nog eens het boek van Robert Lafore "Data Structures and Algorithms in Java" te noemen.. Door dit boek te lezen, leer je niet alleen veel datastructuren (inclusief stack en wachtrij), maar zul je er ook veel zelf implementeren! Wat als Java bijvoorbeeld geen Stack-klasse had? Wat zou u doen als u zo'n datastructuur nodig had voor uw programma? Die moet je natuurlijk zelf schrijven. Als je het boek van Lafore leest , zul je dat vaak doen. Als gevolg hiervan zal uw begrip van datastructuren veel dieper zijn dan wat u zou krijgen van een eenvoudige studie van de theorie :) We ronden de theorie voor vandaag af, maar theorie zonder praktijk is niets! De taken lossen zichzelf niet op, dus het is tijd om ze aan te pakken! :)