Datastrukturer: stack och kö

Hej! Idag ska vi prata om något som är superviktigt för alla programmerare: datastrukturer. Wikipedia säger: "En datastruktur är en dataorganisation, hantering och lagringsformat som möjliggör effektiv åtkomst och modifiering. Närmare bestämt är en datastruktur en samling av datavärden, relationerna mellan dem och de funktioner eller operationer som kan vara tillämpas på uppgifterna." Definitionen är lite förvirrande, men dess innebörd är tydlig. En datastruktur är ett slags arkiv där vi lagrar data för framtida bruk. Inom programmering finns det ett stort utbud av datastrukturer. När man löser specifika problem är det väldigt ofta det viktigaste att välja den mest lämpliga datastrukturen för problemet. Och du är redan bekant med många av dem! Till exempel vet du om arrayer. Och du är också bekant medMap(denna datastruktur kan också hänvisas till som en "ordbok" eller "associativ array"). Det är mycket viktigt att förstå att datastrukturer inte är knutna till något speciellt språk. De är helt enkelt abstrakta "blueprints" som varje programmeringsspråk använder för att skapa sina egna klasser eller implementeringar av en viss struktur. Till exempel är en av de mest kända datastrukturerna en länkad lista. Du kan gå in på Wikipedia och läsa om hur det fungerar och vilka för- och nackdelar det har. Kanske kommer dess definition att verka bekant för dig :) "En länkad lista är en linjär samling av dataelement, vars ordning inte ges av deras fysiska placering i minnet. Istället pekar varje element till nästa." Det beskriver vår älskade LinkedList, eller hur? Ja, och det är precis vad det är :) I Java implementeras "linked list"-datastrukturen av klassen LinkedList. Men andra språk implementerar också länkade listor! I Python kallas denna datastruktur " llist". I Scala heter det " LinkedList", precis som i Java. En länkad lista är en av de grundläggande vanliga datastrukturerna, så du kommer att upptäcka att den är implementerad i alla moderna programmeringsspråk. Samma sak gäller för associativa arrayer. Här är definitionen från Wikipedia: "En associativ array, karta, symboltabell eller ordbok är en abstrakt datatyp som består av en samling (nyckel, värde) par, så att varje möjlig nyckel visas högst en gång i samlingen." Påminner det dig om något? :) Japp. För oss Java-utvecklare är en associativ arrayMapgränssnitt. Men denna datastruktur är även implementerad på andra språk! Till exempel känner C#-programmerare till det under namnet "Dictionary". Och i Ruby är det implementerat i en klass som heter "Hash". Tja, du förstår poängen: datastrukturer är universella begrepp inom programmering, och varje programmeringsspråk implementerar dem på sitt eget sätt. Idag ska vi studera två sådana strukturer — stacken och kön — och se hur de implementeras i Java.

Stackar i Java

En stack är en välkänd datastruktur. Det är väldigt enkelt. En hel del saker i vårt dagliga liv "implementeras" som en stack. Föreställ dig den här enkla situationen: du bor på ett hotell och under dagen fick du några affärsbrev. Du var inte i ditt rum vid den tidpunkten, så hotelltjänstemannen placerade helt enkelt de inkommande breven på ditt skrivbord. Först lade han den första bokstaven på skrivbordet. Sedan kom ett andra brev, och han lade det ovanpå det första. Han lade den tredje bokstaven ovanpå den andra och den fjärde på den tredje. Och nu, svara på en enkel fråga: vilket brev kommer du att läsa först när du kommer tillbaka till ditt rum och ser högen på bordet? Okej, du kommer att läsa den överstabrev. Det vill säga den som kom senast . Det är precis så här en stack fungerar. Denna princip kallas "sist in först ut" (LIFO) . Vad är stack bra för? Tja, anta att du skapar något slags kortspel i Java. En kortlek ligger på bordet. De spelade korten slängs. Du kan använda två högar för att implementera både dragdäcket och kasseringshögen. Spelare tar sina kort från toppen av leken, enligt samma princip som med dina affärsbrev. När spelare lägger korten i slänghögen läggs de nyligen kasserade korten ovanpå de gamla. Här är vårt första försök med spelet, implementerat på basis av en 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 {

   // 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 tidigare har vi två stackar: en draglek och en kasthög. I Java är stackdatastrukturen implementerad i java.util.Stackklassen. Vårt kortspel har 3 metoder som beskriver spelarnas handlingar:

• ta ett kort från leken ( getCardFromDeck()metod)
• kasta ett kort ( discard()metod)
• titta på det översta kortet ( lookAtTopCard()metoden). Låt oss säga att detta är en "Intelligence"-bonus som låter spelaren ta reda på vilket kort som kommer härnäst i spelet.

Inuti våra metoder kallar vi följande metoder för Stack-klassen:

• push()— lägger till ett objekt överst i stapeln. När vi skickar ett kort till kasseringshögen hamnar det högst upp i högen
• pop()— tar bort det översta elementet från stapeln och returnerar det. Denna metod är perfekt för att genomföra åtgärder där spelaren drar ett kort.
• peek()— returnerar det översta elementet i stapeln, men tar inte bort det från stapeln

Låt oss se hur vårt spel kommer att fungera:

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 lade till fem kort till vår kortlek. Den första spelaren tog 3 av dem. Vilka kort fick hon? Konsolutgång:

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

Var uppmärksam på i vilken ordning korten visas på konsolen. "Edwin VanCleef"-kortet gick in i kortleken sist (det var det femte kortet), och det var kortet som spelaren drog först. "Millhouse" var näst sist i kortleken, och spelaren drog den andra. "Sylvanas" gick in i kortleken tredje från toppen, och det var det tredje kortet som spelaren drog. Därefter kastar spelaren korten. Först kastar hon Edwin, sedan Millhouse och sedan Sylvanas. Sedan visar vi korten i vår kasserade hög ett efter ett: Konsolutgång:

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

Återigen ser vi hur en stack fungerar! I vårt spel är utkasthögen också en stack (precis som dragleken). "Edwin VanCleef" kasserades först. Det andra kortet som kastades var Millhouse Manastorm, och det placerades ovanpå Edwin i kasthögen. Sedan kastades Sylvanas och detta kort placerades ovanpå Millhouse. Som du kan se är det inget komplicerat med en stack. Ändå måste du känna till denna datastruktur — den frågas ofta om under anställningsintervjuer, och den är ofta grunden för att bygga mer komplexa datastrukturer.

Kö i Java

En kö är en annan vanlig datastruktur. Förutom stackar implementerar många programmeringsspråk, inklusive Java, även ködatastrukturen. Vad är skillnaden mellan en kö och en stack? En kö baseras inte på LIFO-principen, utan snarare på FIFO-principen ("först in, först ut"). Denna princip är lätt att förstå genom att till exempel överväga en vanlig linje, eller kö, i verkligheten! Till exempel en kö i mataffären. Om det är fem personer i kö, kommer den första som serveras att vara den som kom först på kö . Om en annan person (utöver fem som redan står i kö) vill köpa något och ställer sig i kö, då blir han serverad sist, alltså sjätte. När man arbetar med en kö läggs nya element till i svansen (bakåt), och om man vill skaffa ett element så tas det från huvudet (framtill). Detta är huvudprincipen du måste komma ihåg om hur en kö fungerar. En kös funktion är mycket intuitiv, eftersom vi ofta hittar köer i verkligheten. Det är värt att notera separat att i Java representeras en kö inte av en klass, utan av ett gränssnitt: Queue. Dessutom finns det många implementeringar av detta kögränssnitt i Java. Om vi ​​tittar på Oracle-dokumentationen kommer vi att se att fyra olika gränssnitt, samt en extremt imponerande lista med klasser, ärver Queue-gränssnittet:

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

Vilken stor lista! Men, naturligtvis, du behöver inte memorera alla dessa klasser och gränssnitt just nu – ditt huvud kan explodera :) Vi kommer bara att överväga ett par av de viktigaste och mest intressanta punkterna. Låt oss först uppmärksamma ett av Queues fyra "undergränssnitt": Deque . Vad gör det så speciellt? A Dequeär en dubbelkö. Det utökar funktionaliteten hos en vanlig kö, så att du kan lägga till element i båda ändarna (vid huvudet och svansen) och ta element från båda ändarna av kön. Dubbla köer används i stor utsträckning inom mjukvaruutveckling. Var uppmärksam på listan över köklasser som vi tillhandahållit ovan. Listan är ganska lång, men innehåller den något bekant?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

ha! Här är vår gamla vän LinkedList! Så implementerar den kögränssnittet? Men hur kan det vara kö? När allt kommer omkring LinkedListär a en länkad lista! Sant, men det hindrar det inte från att vara en kö :) Här är en lista över alla gränssnitt som den implementerar:

All implemented interfaces:

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

Som du kan se, LinkedListimplementerar Dequegränssnittet (återigen betyder detta dubbelkö). Varför behövs detta? Detta gör att vi kan få element från början och slutet av en LinkedList. Det låter oss också lägga till element i början och slutet. Här är metoderna som LinkedListkommer från Dequegränssnittet:

• peekFirst()— returnerar det första elementet (men tar inte bort det från kön).
• peekLast()— returnerar det sista elementet (men tar inte bort det från kön).
• pollFirst()— returnerar det första elementet från kön och tar bort det.
• pollLast()— returnerar det sista objektet från kön och tar bort det.
• addFirst()— lägger till ett nytt objekt längst fram i kön.
• addLast()— lägger till ett objekt i slutet av kön.

Som du kan LinkedListse implementerar funktionaliteten i en dubbelkö! Och du behöver sådan funktionalitet i ditt program, du vet var du kan hitta den :) Dagens lektion närmar sig sitt slut. Avslutningsvis ska jag ge dig ett par länkar för ytterligare läsning. Var först uppmärksam på den här artikeln om PriorityQueue . Detta är en av de mest intressanta och användbara Queueimplementeringarna. Anta till exempel att det står 50 personer i kö i din butik och 7 av dem är VIP-kunder. En PriorityQueue låter dig servera dem först! Mycket användbara grejer, eller hur? :) För det andra skulle det inte skada att ännu en gång nämna Robert Lafores bok "Data Structures and Algorithms in Java". När du läser den här boken kommer du inte bara att lära dig många datastrukturer (inklusive stack och kö), utan du kommer också att implementera många av dem själv! Till exempel, vad händer om Java inte hade en Stack-klass? Vad skulle du göra om du behövde en sådan datastruktur för ditt program? Du måste självklart skriva det själv. När du läser Lafores bok kommer du ofta att göra just det. Som ett resultat kommer din förståelse av datastrukturer att bli mycket djupare än vad du skulle få från en enkel studie av teorin :) Vi avslutar teorin för idag, men teori utan praktik är ingenting! Uppgifterna löser sig inte av sig själva, så det är dags att ta itu med dem! :)