Datastrukturer: stak og kø

Hej! I dag vil vi tale om noget, der er super vigtigt for enhver programmør: datastrukturer. Wikipedia siger: "En datastruktur er en dataorganisation, -styring og -lagringsformat, der muliggør effektiv adgang og modifikation. Mere præcist er en datastruktur en samling af dataværdier, relationerne mellem dem og de funktioner eller operationer, der kan være anvendt på dataene." Definitionen er lidt forvirrende, men dens kerne er klar. En datastruktur er en slags repository, hvor vi gemmer data til fremtidig brug. Inden for programmering er der et stort udvalg af datastrukturer. Ved løsning af specifikke problemer er det meget ofte det vigtigste at vælge den bedst egnede datastruktur til problemet. Og du er allerede bekendt med mange af dem! For eksempel kender du til arrays. Og du er også bekendt medMap(denne datastruktur kan også omtales som en "ordbog" eller "associativ array"). Det er meget vigtigt at forstå, at datastrukturer ikke er bundet til noget bestemt sprog. De er simpelthen abstrakte "blueprints", som hvert programmeringssprog bruger til at skabe sine egne klasser eller implementeringer af en bestemt struktur. For eksempel er en af ​​de mest berømte datastrukturer en sammenkædet liste. Du kan gå ind på Wikipedia og læse om hvordan det virker og hvilke fordele og ulemper det har. Måske vil dens definition virke bekendt for dig :) "En sammenkædet liste er en lineær samling af dataelementer, hvis rækkefølge ikke er givet af deres fysiske placering i hukommelsen. I stedet peger hvert element på det næste." Det beskriver vores elskede LinkedList, ikke? Ja, og det er lige hvad det er :) I Java implementeres "linked list" datastrukturen af ​​klassen LinkedList. Men andre sprog implementerer også linkede lister! I Python kaldes denne datastruktur " llist". I Scala hedder det " LinkedList", ligesom i Java. En sammenkædet liste er en af ​​de grundlæggende almindelige datastrukturer, så du vil opdage, at den er implementeret i ethvert moderne programmeringssprog. Det samme gælder for associative arrays. Her er definitionen fra Wikipedia: "En associativ matrix, kort, symboltabel eller ordbog er en abstrakt datatype sammensat af en samling af (nøgle, værdi) par, sådan at hver mulig nøgle højst optræder én gang i samlingen." Minder det dig om noget? :) Jep. For os Java-udviklere er et associativt arrayMapinterface. Men denne datastruktur er også implementeret på andre sprog! For eksempel kender C#-programmører det under navnet "Ordbog". Og i Ruby er det implementeret i en klasse kaldet "Hash". Nå, du forstår pointen: datastrukturer er universelle begreber inden for programmering, og hvert programmeringssprog implementerer dem på sin egen måde. I dag vil vi studere to sådanne strukturer - stakken og køen - og se, hvordan de er implementeret i Java.

Stabler i Java

En stak er en velkendt datastruktur. Det er meget enkelt. En hel del ting i vores daglige liv er "implementeret" som en stak. Forestil dig denne simple situation: du bor på et hotel, og i løbet af dagen modtog du nogle forretningsbreve. Du var ikke på dit værelse på det tidspunkt, så hotellets ekspedient lagde blot de indgående breve på dit skrivebord. Først lagde han det første bogstav på skrivebordet. Så kom der et andet brev, og han lagde det oven på det første. Han lagde det tredje bogstav oven på det andet og det fjerde oven på det tredje. Og nu, svar på et simpelt spørgsmål: Hvilket brev vil du læse først , når du kommer tilbage til dit værelse og ser stakken på bordet? Okay, du vil læse det øverstebrev. Altså den, der ankom senest . Det er præcis sådan en stak fungerer. Dette princip kaldes "sidst ind først ud" (LIFO) . Hvad er stakke gode til? Tja, antag, at du laver en form for kortspil i Java. Et sæt kort ligger på bordet. De spillede kort kasseres. Du kan bruge to stakke til at implementere både trækbunken og kasseringsbunken. Spillere tager deres kort fra toppen af ​​bunken efter samme princip som med dine forretningsbreve. Når spillere lægger kort i kasseringsbunken, lægges de nyligt kasserede kort oven på de gamle. Her er vores første forsøg på spillet, implementeret på basis af en stak:

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

Som vi sagde tidligere, har vi to stakke: et trækdæk og en smidbunke. I Java er stakdatastrukturen implementeret i java.util.Stackklassen. Vores kortspil har 3 metoder, der beskriver spillernes handlinger:

• tag et kort fra bunken ( getCardFromDeck()metode)
• kassere et kort ( discard()metode)
• se på det øverste kort ( lookAtTopCard()metode). Lad os sige, at dette er en "Intelligence"-bonus, der giver spilleren mulighed for at finde ud af, hvilket kort der kommer næste gang i spillet.

Inde i vores metoder kalder vi følgende metoder i Stack-klassen:

• push()— tilføjer et element til toppen af ​​stakken. Når vi sender et kort til kasseringsbunken, går det til toppen af ​​bunken
• pop()— fjerner det øverste element fra stakken og returnerer det. Denne metode er perfekt til at implementere handlinger, hvor spilleren trækker et kort.
• peek()— returnerer det øverste element i stakken, men fjerner det ikke fra stakken

Lad os se, hvordan vores spil vil fungere:

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

Vi tilføjede fem kort til vores bunke. Den første spiller tog 3 af dem. Hvilke kort fik hun? Konsoludgang:

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

Vær opmærksom på den rækkefølge, som kortene vises i på konsollen. "Edwin VanCleef"-kortet gik sidst i bunken (det var det femte kort), og det var det kort, som spilleren trak først. "Millhouse" var næstsidst i bunken, og spilleren trak den som nummer to. "Sylvanas" gik ind i bunken tredje fra toppen, og det var det tredje kort, som spilleren trak. Dernæst kasserer spilleren kortene. Først kasserer hun Edwin, derefter Millhouse og derefter Sylvanas. Så viser vi kortene i vores kasserede bunke et efter et: Konsol output:

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

Endnu en gang ser vi, hvordan en stak fungerer! I vores spil er kasseringsbunken også en stak (ligesom trækbunken). "Edwin VanCleef" blev kasseret først. Det andet kasserede kort var Millhouse Manastorm, og det blev placeret oven på Edwin i kasseringsbunken. Derefter blev Sylvanas kasseret, og dette kort blev placeret oven på Millhouse. Som du kan se, er der ikke noget kompliceret ved en stak. Alligevel skal du kende denne datastruktur — den bliver ofte spurgt om under jobsamtaler, og den er ofte grundlaget for at bygge mere komplekse datastrukturer.

Kø i Java

En kø er en anden almindelig datastruktur. Ud over stakke implementerer mange programmeringssprog, inklusive Java, også kødatastrukturen. Hvad er forskellen mellem en kø og en stak? En kø er ikke baseret på LIFO-princippet, men snarere på FIFO-princippet ("først ind, først ud"). Dette princip er let at forstå ved at overveje for eksempel en almindelig linje, eller kø, i det virkelige liv! For eksempel en kø ved købmanden. Hvis der er fem personer i kø, vil den første , der skal betjenes, være den, der kom først ind i køen . Hvis en anden person (udover fem allerede i kø) vil købe noget og stiller sig i kø, så bliver han serveret sidst, altså sjette. Når man arbejder med en kø, tilføjes nye elementer til halen (bagsiden), og hvis man ønsker at få et element, tages det fra hovedet (foran). Dette er hovedprincippet, du skal huske med hensyn til, hvordan en kø fungerer. En køs betjening er meget intuitiv, da vi ofte finder køer i det virkelige liv. Det er værd at bemærke separat, at i Java er en kø ikke repræsenteret af en klasse, men af ​​en grænseflade: Kø. Hvad mere er, er der mange implementeringer af denne kø-grænseflade i Java. Hvis vi ser på Oracle-dokumentationen, vil vi se, at 4 forskellige grænseflader, samt en ekstremt imponerende liste af klasser, arver Queue-grænsefladen:

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

Hvilken stor liste! Men du behøver selvfølgelig ikke huske alle disse klasser og grænseflader lige nu - dit hoved kan eksplodere :) Vi vil kun overveje et par af de vigtigste og mest interessante punkter. Lad os først være opmærksomme på en af ​​Køens fire "undergrænseflader": Deque . Hvad gør det så specielt? A Dequeer en dobbeltkø. Det udvider funktionaliteten af ​​en almindelig kø, så du kan tilføje elementer til begge ender (ved hovedet og halen) og tage elementer fra begge ender af køen. Dobbelt-endede køer er meget brugt i softwareudvikling. Vær opmærksom på listen over køklasser, som vi har angivet ovenfor. Listen er ret lang, men indeholder den noget kendt?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Her er vores gamle ven LinkedList! Så implementerer den kø-grænsefladen? Men hvordan kan det være en kø? Når alt kommer til alt, LinkedLister a en sammenkædet liste! Sandt nok, men det forhindrer det ikke i at være en kø :) Her er en liste over alle de grænseflader, som den implementerer:

All implemented interfaces:

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

Som du kan se, LinkedListimplementerer Dequegrænsefladen (igen betyder det dobbeltkø). Hvorfor er dette nødvendigt? Dette giver os mulighed for at få elementer fra begyndelsen og slutningen af ​​en LinkedList. Det giver os også mulighed for at tilføje elementer til begyndelsen og slutningen. Her er de metoder, der LinkedListkommer fra Dequegrænsefladen:

• peekFirst()— returnerer det første element (men fjerner det ikke fra køen).
• peekLast()— returnerer det sidste element (men fjerner det ikke fra køen).
• pollFirst()— returnerer det første element fra køen og fjerner det.
• pollLast()— returnerer den sidste vare fra køen og fjerner den.
• addFirst()— tilføjer et nyt element foran i køen.
• addLast()— tilføjer et element til slutningen af ​​køen.

Som du kan se, LinkedListimplementerer funktionaliteten i en dobbeltkø fuldt ud! Og du har brug for en sådan funktionalitet i dit program, du ved, hvor du kan finde det :) Dagens lektion er ved at være slut. Afslutningsvis vil jeg give dig et par links til yderligere læsning. Vær først opmærksom på denne artikel om PriorityQueue . Dette er en af ​​de mest interessante og nyttige Queueimplementeringer. Antag for eksempel, at der står 50 personer i kø i din butik, og 7 af dem er VIP-kunder. En PriorityQueue giver dig mulighed for at betjene dem først! Meget nyttige ting, ikke? :) For det andet ville det ikke skade endnu en gang at nævne Robert Lafores bog "Data Structures and Algorithms in Java". Når du læser denne bog, lærer du ikke kun mange datastrukturer (inklusive stak og kø), men du vil også implementere mange af dem selv! For eksempel, hvad hvis Java ikke havde en Stack-klasse? Hvad ville du gøre, hvis du havde brug for en sådan datastruktur til dit program? Du skal selvfølgelig skrive det selv. Når du læser Lafores bog , vil du ofte gøre netop det. Som et resultat vil din forståelse af datastrukturer være meget dybere, end hvad du ville få ved et simpelt studie af teorien :) Vi afslutter teorien for i dag, men teori uden praksis er ingenting! Opgaverne løser sig ikke af sig selv, så det er tid til at tage fat på dem! :)