Datastrukturer: stabel og kø

Hei! I dag skal vi snakke om noe som er superviktig for enhver programmerer: datastrukturer. Wikipedia sier: "En datastruktur er en dataorganisasjon, administrasjon og lagringsformat som muliggjør effektiv tilgang og modifikasjon. Mer presist er en datastruktur en samling av dataverdier, relasjonene mellom dem og funksjonene eller operasjonene som kan være brukt på dataene." Definisjonen er litt forvirrende, men essensen er klar. En datastruktur er et slags depot hvor vi lagrer data for fremtidig bruk. I programmering er det et stort utvalg av datastrukturer. Når man skal løse spesifikke problemer, er det veldig ofte det viktigste å velge den best egnede datastrukturen for problemet. Og du er allerede kjent med mange av dem! For eksempel vet du om arrays. Og du er også kjent medMap(denne datastrukturen kan også bli referert til som en "ordbok" eller "assosiativ matrise"). Det er veldig viktig å forstå at datastrukturer ikke er knyttet til noe bestemt språk. De er ganske enkelt abstrakte "blåkopier" som hvert programmeringsspråk bruker for å lage sine egne klasser eller implementeringer av en bestemt struktur. For eksempel er en av de mest kjente datastrukturene en koblet liste. Du kan gå inn på Wikipedia og lese om hvordan det fungerer og hvilke fordeler og ulemper det har. Kanskje dens definisjon vil virke kjent for deg :) "En koblet liste er en lineær samling av dataelementer, hvis rekkefølge ikke er gitt av deres fysiske plassering i minnet. I stedet peker hvert element til neste." Det beskriver vår elskede LinkedList, ikke sant? Ja, og det er akkurat det det er :) I Java implementeres "linked list"-datastrukturen av klassen LinkedList. Men andre språk implementerer også koblede lister! I Python kalles denne datastrukturen " llist". I Scala heter det " LinkedList", akkurat som i Java. En koblet liste er en av de grunnleggende vanlige datastrukturene, så du vil finne at den er implementert i ethvert moderne programmeringsspråk. Det samme gjelder assosiative arrays. Her er definisjonen fra Wikipedia: "En assosiativ matrise, kart, symboltabell eller ordbok er en abstrakt datatype sammensatt av en samling av (nøkkel, verdi) par, slik at hver mulig nøkkel vises maksimalt én gang i samlingen." Minner det deg om noe? :) Jepp. For oss Java-utviklere er en assosiativ arrayMapgrensesnitt. Men denne datastrukturen er også implementert på andre språk! For eksempel kjenner C#-programmerere det under navnet "Ordbok". Og i Ruby er det implementert i en klasse kalt "Hash". Vel, du forstår poenget: datastrukturer er universelle konsepter innen programmering, og hvert programmeringsspråk implementerer dem på sin egen måte. I dag skal vi studere to slike strukturer — stabelen og køen — og se hvordan de er implementert i Java.

Stabler i Java

En stack er en velkjent datastruktur. Det er veldig enkelt. Ganske mange elementer i hverdagen vår er "implementert" som en stabel. Se for deg denne enkle situasjonen: du bor på et hotell, og i løpet av dagen mottok du noen forretningsbrev. Du var ikke på rommet ditt på det tidspunktet, så hotellets kontorist la ganske enkelt de innkommende brevene på skrivebordet ditt. Først la han den første bokstaven på skrivebordet. Så kom et annet brev, og han la det oppå det første. Han la den tredje bokstaven på toppen av den andre, og den fjerde på toppen av den tredje. Og nå, svar på et enkelt spørsmål: hvilken bokstav vil du lese først når du kommer tilbake til rommet ditt og ser stabelen på bordet? Greit, du vil lese det øverstebrev. Det vil si den som kom sist . Dette er nøyaktig hvordan en stack fungerer. Dette prinsippet kalles "sist inn først ut" (LIFO) . Hva er stabler bra for? Vel, anta at du lager et slags kortspill i Java. En kortstokk ligger på bordet. De spilte kortene kastes. Du kan bruke to stabler for å implementere både trekkdekket og kasseringshaugen. Spillerne tar kortene sine fra toppen av kortstokken, etter samme prinsipp som med forretningsbrevene dine. Når spillere legger kortene i bunken, legges de nylig kastede kortene på toppen av de gamle. Her er vårt første forsøk på spillet, implementert på grunnlag av en stabel:

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 sa tidligere, har vi to stabler: en trekkbunke og en kastbunke. I Java er stackdatastrukturen implementert i java.util.Stackklassen. Kortspillet vårt har 3 metoder som beskriver handlingene til spillerne:

• ta et kort fra kortstokken ( getCardFromDeck()metode)
• kaste et kort ( discard()metode)
• se på det øverste kortet ( lookAtTopCard()metode). La oss si at dette er en "Intelligence"-bonus som lar spilleren finne ut hvilket kort som kommer neste gang i spillet.

Inne i metodene våre kaller vi følgende metoder for Stack-klassen:

• push()— legger til et element på toppen av stabelen. Når vi sender et kort til kasseringsbunken, går det til toppen av bunken
• pop()— fjerner toppelementet fra stabelen og returnerer det. Denne metoden er perfekt for å implementere handlinger der spilleren trekker et kort.
• peek()— returnerer det øverste elementet i stabelen, men fjerner det ikke fra stabelen

La oss se hvordan spillet vårt 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 la til fem kort til kortstokken vår. Den første spilleren tok 3 av dem. Hvilke kort fikk hun? Konsoll utgang:

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

Vær oppmerksom på rekkefølgen kortene vises i på konsollen. "Edwin VanCleef"-kortet gikk sist inn i bunken (det var det femte kortet), og det var kortet som spilleren trakk først. "Millhouse" var nest sist inn i kortstokken, og spilleren trakk den som nummer to. «Sylvanas» gikk inn i kortstokken tredje fra toppen, og det var det tredje kortet som spilleren trakk. Deretter kaster spilleren kortene. Først forkaster hun Edwin, deretter Millhouse og deretter Sylvanas. Deretter viser vi kortene i kasseringshaugen vår ett etter ett: Konsollutgang:

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

Nok en gang ser vi hvordan en stack fungerer! I spillet vårt er forkastbunken også en stabel (akkurat som trekkstokken). "Edwin VanCleef" ble kastet først. Det andre kortet som ble kastet var Millhouse Manastorm, og det ble plassert på toppen av Edwin i kastebunken. Deretter ble Sylvanas kastet, og dette kortet ble plassert på toppen av Millhouse. Som du kan se, er det ikke noe komplisert med en stabel. Likevel må du kjenne til denne datastrukturen — den blir ofte spurt om under jobbintervjuer, og den er ofte grunnlaget for å bygge mer komplekse datastrukturer.

Kø i Java

En kø er en annen vanlig datastruktur. I tillegg til stabler, implementerer mange programmeringsspråk, inkludert Java, også kødatastrukturen. Hva er forskjellen mellom en kø og en stabel? En kø er ikke basert på LIFO-prinsippet, men heller på FIFO-prinsippet ("først inn, først ut"). Dette prinsippet er lett å forstå ved å vurdere for eksempel en vanlig linje, eller kø, i det virkelige liv! For eksempel en kø i matbutikken. Hvis det er fem personer i kø, vil den første som blir servert være den som kom først på køen . Hvis en annen person (i tillegg til fem som allerede står i kø) ønsker å kjøpe noe og stiller seg i kø, blir han servert sist, altså sjette. Når du jobber med en kø, legges nye elementer til i halen (bak), og hvis du ønsker å få et element, vil det bli tatt fra hodet (foran). Dette er hovedprinsippet du må huske på hvordan en kø fungerer. En køs operasjon er veldig intuitiv, siden vi ofte finner køer i det virkelige liv. Det er verdt å merke seg separat at i Java er en kø ikke representert av en klasse, men av et grensesnitt: Queue. Dessuten er det mange implementeringer av dette køgrensesnittet i Java. Hvis vi ser på Oracle-dokumentasjonen, vil vi se at 4 forskjellige grensesnitt, samt en ekstremt imponerende liste over klasser, arver Queue-grensesnittet:

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

For en stor liste! Men, selvfølgelig, du trenger ikke å huske alle disse klassene og grensesnittene akkurat nå – hodet ditt kan eksplodere :) Vi skal bare vurdere et par av de viktigste og mest interessante punktene. Først, la oss ta hensyn til et av Queues fire "undergrensesnitt": Deque . Hva gjør det så spesielt? A Dequeer en tosidig kø. Den utvider funksjonaliteten til en vanlig kø, slik at du kan legge til elementer i begge ender (ved hodet og halen) og ta elementer fra begge ender av køen. Dobbeltendede køer er mye brukt i programvareutvikling. Vær oppmerksom på listen over køklasser som vi ga ovenfor. Listen er ganske lang, men inneholder den noe kjent?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Her er vår gamle venn LinkedList! Så implementerer den kø-grensesnittet? Men hvordan kan det være en kø? Tross alt LinkedLister a en lenket liste! Riktignok, men det stopper ikke det fra å være en kø :) Her er en liste over alle grensesnittene som den implementerer:

All implemented interfaces:

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

Som du kan se, LinkedListimplementerer Dequegrensesnittet (igjen betyr dette dobbeltkø). Hvorfor er dette nødvendig? Dette gjør at vi kan få elementer fra begynnelsen og slutten av en LinkedList. Det lar oss også legge til elementer til begynnelsen og slutten. Her er metodene som LinkedListkommer fra Dequegrensesnittet:

• peekFirst()— returnerer det første elementet (men fjerner det ikke fra køen).
• peekLast()— returnerer det siste elementet (men fjerner det ikke fra køen).
• pollFirst()— returnerer det første elementet fra køen og fjerner det.
• pollLast()— returnerer det siste elementet fra køen og fjerner det.
• addFirst()— legger til et nytt element foran i køen.
• addLast()— legger til et element på slutten av køen.

Som du kan se, LinkedListimplementerer funksjonaliteten til en tosidig kø fullt ut! Og du trenger slik funksjonalitet i programmet ditt, du vet hvor du finner det :) Dagens leksjon nærmer seg slutten. Avslutningsvis vil jeg gi deg et par lenker for mer lesing. Vær først oppmerksom på denne artikkelen om PriorityQueue . Dette er en av de mest interessante og nyttige Queueimplementeringene. Anta for eksempel at det står 50 personer i kø i butikken din, og 7 av dem er VIP-kunder. En PriorityQueue lar deg betjene dem først! Veldig nyttige ting, ikke sant? :) For det andre ville det ikke skade å nok en gang nevne Robert Lafores bok "Data Structures and Algorithms in Java". Når du leser denne boken, vil du ikke bare lære mange datastrukturer (inkludert stack og kø), men du vil også implementere mange av dem selv! For eksempel, hva om Java ikke hadde en Stack-klasse? Hva ville du gjort hvis du trengte en slik datastruktur for programmet ditt? Du må selvfølgelig skrive det selv. Når du leser Lafores bok , vil du ofte gjøre nettopp det. Som et resultat vil din forståelse av datastrukturer være mye dypere enn det du ville fått fra en enkel studie av teorien :) Vi avslutter teorien for i dag, men teori uten praksis er ingenting! Oppgavene løser seg ikke av seg selv, så det er på tide å takle dem! :)