Structuri de date: stivă și coadă

Bună! Astăzi vom vorbi despre ceva care este foarte important pentru orice programator: structurile de date. Wikipedia spune: „O structură de date este un format de organizare, gestionare și stocare a datelor care permite accesul și modificarea eficient. Mai precis, o structură de date este o colecție de valori de date, relațiile dintre acestea și funcțiile sau operațiunile care pot fi aplicate datelor.” Definiția este puțin confuză, dar esenta ei este clară. O structură de date este un fel de depozit în care stocăm datele pentru utilizare ulterioară. În programare, există o mare varietate de structuri de date. Când rezolvați probleme specifice, de foarte multe ori cel mai important lucru este să alegeți cea mai potrivită structură de date pentru problemă. Și ești deja familiarizat cu multe dintre ele! De exemplu, știți despre matrice. Și ești, de asemenea, familiarizatMap(această structură de date poate fi denumită și „dicționar” sau „matrice asociativă”). Este foarte important să înțelegeți că structurile de date nu sunt legate de niciun limbaj anume. Sunt pur și simplu „planuri” abstracte pe care fiecare limbaj de programare le folosește pentru a-și crea propriile clase sau implementări ale unei anumite structuri. De exemplu, una dintre cele mai cunoscute structuri de date este o listă legată. Puteți merge pe Wikipedia și puteți citi despre cum funcționează și ce avantaje și dezavantaje are. Poate că definiția sa vă va părea familiară :) „O listă legată este o colecție liniară de elemente de date, a căror ordine nu este dată de plasarea lor fizică în memorie. În schimb, fiecare element indică următorul.” Asta o descrie pe iubita noastră LinkedList, nu-i așa? Da, și asta este :) În Java, structura de date „listă legată” este implementată de clasă LinkedList. Dar și alte limbi implementează liste legate! În Python, această structură de date se numește " llist". În Scala se numește " LinkedList", la fel ca în Java. O listă legată este una dintre structurile de date comune de bază, așa că veți descoperi că este implementată în orice limbaj de programare modern. Același lucru este valabil și pentru tablourile asociative. Iată definiția de la Wikipedia: „O matrice asociativă, o hartă, un tabel de simboluri sau un dicționar este un tip de date abstract compus dintr-o colecție de perechi (cheie, valoare), astfel încât fiecare cheie posibilă apare cel mult o dată în colecție”. Asta îți amintește de ceva? :) Da. Pentru noi, dezvoltatorii Java, o matrice asociativă esteMapinterfata. Dar această structură de date este implementată și în alte limbi! De exemplu, programatorii C# îl cunosc sub numele de „Dicționar”. Și în Ruby, este implementat într-o clasă numită „Hash”. Ei bine, înțelegeți ideea: structurile de date sunt concepte universale în programare și fiecare limbaj de programare le implementează în felul său. Astăzi vom studia două astfel de structuri — stiva și coada — și vom vedea cum sunt implementate în Java.

Stive în Java

O stivă este o structură de date binecunoscută. Este foarte simplu. Destul de multe articole din viața noastră de zi cu zi sunt „implementate” ca o stivă. Imaginați-vă această situație simplă: vă cazați la un hotel și de-a lungul zilei ați primit niște scrisori de afaceri. Nu erai în camera ta în acel moment, așa că funcționarul hotelului a pus pur și simplu scrisorile primite pe biroul tău. Mai întâi, a pus prima scrisoare pe birou. Apoi a sosit o a doua scrisoare și a pus-o deasupra primei. A pus a treia literă peste a doua, iar a patra peste a treia. Și acum, răspunde la o întrebare simplă: ce scrisoare vei citi prima când te vei întoarce în camera ta și vei vedea teancul de pe masă? Corect, vei citi cel mai de susscrisoare. Adică cel care a sosit cel mai recent . Exact așa funcționează o stivă. Acest principiu se numește „ultimul intrat, primul ieșit” (LIFO) . La ce sunt bune stivele? Ei bine, să presupunem că creezi un fel de joc de cărți în Java. Un pachet de cărți se află pe masă. Cărțile jucate sunt aruncate. Puteți folosi două stive pentru a implementa atât pachetul de tragere, cât și teancul de aruncare. Jucătorii își iau cărțile din partea de sus a pachetului, urmând același principiu ca și în cazul scrisorilor tale de afaceri. Când jucătorii pun cărți în teancul de decartare, cărțile nou aruncate sunt plasate deasupra celor vechi. Iată prima noastră încercare de joc, implementată pe baza unui stivă:

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

După cum am spus mai devreme, avem două stive: un pachet de tragere și un teanc de debarasuri. În Java, structura de date a stivei este implementată în java.util.Stackclasă. Jocul nostru de cărți are 3 metode care descriu acțiunile jucătorilor:

• ia o carte din pachet ( getCardFromDeck()metoda)
• aruncați un card ( discard()metoda)
• uită-te la cardul de sus ( lookAtTopCard()metoda). Să presupunem că acesta este un bonus de „Inteligentă” care permite jucătorului să afle ce carte va urma în joc.

În cadrul metodelor noastre, numim următoarele metode ale clasei Stack:

• push()— adaugă un articol în partea de sus a stivei. Când trimitem o carte în teancul de aruncare, aceasta merge în vârful teancului
• pop()— îndepărtează elementul superior din stivă și îl returnează. Această metodă este perfectă pentru implementarea acțiunilor în care jucătorul trage o carte.
• peek()— returnează elementul superior al stivei, dar nu îl scoate din stivă

Să vedem cum va funcționa jocul nostru:

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

Am adăugat cinci cărți la pachetul nostru. Primul jucător a luat 3 dintre ele. Ce carduri a primit? Ieșire din consolă:

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

Fiți atenți la ordinea în care sunt afișate cărțile pe consolă. Cartea „Edwin VanCleef” a intrat ultima în pachet (a fost a cincea carte) și a fost cartea pe care jucătorul a extras-o primul. „Millhouse” a fost penul ultimul în pachet, iar jucătorul l-a atras pe locul doi. „Sylvanas” a intrat în pachetul a treia din partea de sus și a fost a treia carte pe care jucătorul a extras-o. Apoi, jucătorul aruncă cărți. Mai întâi, îl aruncă pe Edwin, apoi pe Millhouse, apoi pe Sylvanas. Apoi afișăm cărțile din teancul nostru de aruncare unul câte unul: Ieșirea consolei:

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

Încă o dată, vedem cum funcționează o stivă! În jocul nostru, teancul de debarasuri este, de asemenea, un teanc (la fel ca pachetul de extragere). „Edwin VanCleef” a fost aruncat primul. A doua carte aruncată a fost Millhouse Manastorm și a fost plasată deasupra lui Edwin în teancul de debarasare. Apoi Sylvanas a fost aruncată, iar această carte a fost plasată deasupra Millhouse. După cum puteți vedea, nu este nimic complicat la o stivă. Totuși, trebuie să cunoașteți această structură de date - este adesea întrebat despre ea în timpul interviurilor de angajare și este adesea baza pentru construirea unor structuri de date mai complexe.

Coadă în Java

O coadă este o altă structură de date comună. Pe lângă stive, multe limbaje de programare, inclusiv Java, implementează, de asemenea, structura de date a cozii. Care este diferența dintre o coadă și o stivă? O coadă nu se bazează pe principiul LIFO, ci mai degrabă pe principiul FIFO ("primul intrat, primul ieșit"). Acest principiu este ușor de înțeles luând în considerare, de exemplu, o linie obișnuită, sau coadă, în viața reală! De exemplu, o linie la magazinul alimentar. Dacă sunt cinci persoane la rând, primul care va fi servit va fi cel care a intrat primul pe linie . Dacă o altă persoană (în plus față de cinci deja la coadă) vrea să cumpere ceva și se pune la coadă, atunci el este servit ultimul, adică al șaselea. Când lucrați cu o coadă, elemente noi sunt adăugate la coadă (spate), iar dacă doriți să obțineți un element, acesta va fi luat din cap (față). Acesta este principiul principal pe care trebuie să-l rețineți cu privire la modul în care funcționează o coadă. Funcționarea unei cozi este foarte intuitivă, deoarece găsim cozi de multe ori în viața reală. Este de remarcat separat faptul că în Java o coadă este reprezentată nu de o clasă, ci de o interfață: Queue. În plus, există o mulțime de implementări ale acestei interfețe de coadă în Java. Dacă ne uităm la documentația Oracle, vom vedea că 4 interfețe diferite, precum și o listă extrem de impresionantă de clase, moștenesc interfața Queue:

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

Ce listă mare! Dar, bineînțeles, nu trebuie să memorezi toate aceste clase și interfețe chiar acum — ți-ar putea exploda capul :) Vom lua în considerare doar câteva dintre cele mai importante și interesante puncte. Mai întâi, să acordăm atenție uneia dintre cele patru „subinterfețe” ale Queue: Deque . Ce îl face atât de special? A Dequeeste o coadă dublă. Extinde funcționalitatea unei cozi obișnuite, permițându-vă să adăugați elemente la ambele capete (la cap și coadă) și să luați elemente de la ambele capete ale cozii. Cozile duble sunt utilizate pe scară largă în dezvoltarea de software. Acordați atenție listei de clase de coadă pe care am furnizat-o mai sus. Lista este destul de lungă, dar conține ceva familiar?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Iată vechiul nostru prieten LinkedList! Deci, implementează interfața Queue? Dar cum poate fi o coadă? La urma urmei, a LinkedListeste o listă legată! Adevărat, dar asta nu o împiedică să fie o coadă :) Iată o listă cu toate interfețele pe care le implementează:

All implemented interfaces:

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

După cum puteți vedea, LinkedListimplementează Dequeinterfața (din nou, aceasta înseamnă coadă dublă). De ce este nevoie de asta? Acest lucru ne permite să obținem elemente de la începutul și sfârșitul unui LinkedList. De asemenea, ne permite să adăugăm elemente la început și la sfârșit. Iată metodele care LinkedListprimesc din Dequeinterfață:

• peekFirst()— returnează primul element (dar nu îl elimină din coadă).
• peekLast()— returnează ultimul element (dar nu îl elimină din coadă).
• pollFirst()— returnează primul element din coadă și îl elimină.
• pollLast()— returnează ultimul element din coadă și îl elimină.
• addFirst()— adaugă un nou articol în partea din față a cozii.
• addLast()— adaugă un articol la sfârșitul cozii.

După cum puteți vedea, LinkedListimplementează pe deplin funcționalitatea unei cozi duble! Și ai nevoie de o astfel de funcționalitate în programul tău, vei ști unde să o găsești :) Lecția de astăzi se apropie de sfârșit. În concluzie, vă voi oferi câteva link-uri pentru lectură suplimentară. În primul rând, acordați atenție acestui articol despre PriorityQueue . Aceasta este una dintre cele mai interesante și utile Queueimplementări. De exemplu, să presupunem că există 50 de persoane care așteaptă la coadă la magazinul dvs. și 7 dintre ei sunt clienți VIP. Un PriorityQueue vă va permite să le serviți mai întâi! Lucruri foarte utile, nu? :) În al doilea rând, n-ar strica să menționăm încă o dată cartea lui Robert Lafore „Data Structures and Algorithms in Java”. Citind această carte, nu numai că veți învăța multe structuri de date (inclusiv stiva și coada), dar le veți implementa și dvs. multe dintre ele! De exemplu, ce se întâmplă dacă Java nu ar avea o clasă Stack? Ce ai face dacă ai avea nevoie de o astfel de structură de date pentru programul tău? Ar trebui să-l scrii singur, desigur. Pe măsură ce citiți cartea lui Lafore , veți face adesea exact asta. Ca rezultat, înțelegerea dvs. asupra structurilor de date va fi mult mai profundă decât ceea ce ați obține dintr-un simplu studiu al teoriei :) Încheiem teoria pentru astăzi, dar teoria fără practică este nimic! Sarcinile nu se vor rezolva de la sine, așa că este timpul să le abordăm! :)