Adatszerkezetek: verem és sor

Szia! Ma valamiről fogunk beszélni, ami minden programozó számára rendkívül fontos: az adatstruktúrákról. A Wikipédia ezt írja: "Az adatstruktúra olyan adatszervezési, kezelési és tárolási formátum, amely lehetővé teszi a hatékony hozzáférést és módosítást. Pontosabban, az adatstruktúra adatértékek gyűjteménye, a köztük lévő kapcsolatok, valamint a kezelhető funkciók vagy műveletek. alkalmazva az adatokra." A meghatározás kissé zavaros, de a lényege egyértelmű. Az adatstruktúra egyfajta adattár, ahol adatokat tárolunk későbbi felhasználás céljából. A programozásban nagyon sokféle adatstruktúra létezik. Konkrét problémák megoldása során nagyon gyakran az a legfontosabb, hogy a problémának leginkább megfelelő adatszerkezetet válasszunk. És sokukat már ismeri! Például ismeri a tömböket. És azt is ismeredMap(ezt az adatstruktúrát "szótárnak" vagy "asszociatív tömbnek" is nevezhetjük). Nagyon fontos megérteni, hogy az adatstruktúrák nem kötődnek egyetlen nyelvhez sem. Ezek egyszerűen absztrakt "tervrajzok", amelyeket minden programozási nyelv arra használ, hogy létrehozza saját osztályait vagy egy adott struktúra megvalósítását. Például az egyik leghíresebb adatstruktúra a linkelt lista. Felkeresheti a Wikipédiát, és elolvashatja, hogyan működik, és milyen előnyei és hátrányai vannak. Talán ismerősnek tűnik a definíciója :) "A linkelt lista adatelemek lineáris gyűjteménye, amelyek sorrendjét nem a memóriában való fizikai elhelyezkedésük adja meg. Ehelyett minden elem a következőre mutat." Ez jellemzi a kedvesünket LinkedList, nem? Igen, és pont erről van szó :) Java-ban a "linked list" adatstruktúrát az LinkedListosztály valósítja meg. De más nyelvek is megvalósítanak linkelt listákat! A Pythonban ennek az adatszerkezetnek a neve " llist". A Scalában " "-nek hívják LinkedList, akárcsak a Java-ban. A linkelt lista az egyik alapvető általános adatstruktúra, így azt tapasztalhatja, hogy bármely modern programozási nyelven megvalósítható. Ugyanez igaz az asszociatív tömbökre is. Íme a definíció a Wikipédiából: "Az asszociatív tömb, térkép, szimbólumtábla vagy szótár egy absztrakt adattípus, amely (kulcs, érték) párok gyűjteményéből áll, úgy, hogy minden lehetséges kulcs legfeljebb egyszer jelenik meg a gyűjteményben." Emlékeztet ez valamire? :) Igen. Nekünk, Java fejlesztőknek az asszociatív tömb azMapfelület. De ez az adatstruktúra más nyelveken is megvalósul! Például a C# programozók "Szótár" néven ismerik. Rubyban pedig a "Hash" nevű osztályban van megvalósítva. Nos, érted a lényeget: az adatstruktúrák univerzális fogalmak a programozásban, és minden programozási nyelv a maga módján valósítja meg őket. Ma két ilyen struktúrát fogunk tanulmányozni – a verem és a várólista –, és meglátjuk, hogyan valósulnak meg a Java-ban.

Stackek Java nyelven

A verem egy jól ismert adatstruktúra. Ez nagyon egyszerű. A mindennapi életünkben jó néhány elemet halomként "valósítunk meg". Képzelje el ezt az egyszerű helyzetet: Ön egy szállodában száll meg, és a nap folyamán üzleti leveleket kapott. Ön éppen nem volt a szobájában, ezért a szállodai alkalmazott egyszerűen az asztalára tette a beérkező leveleket. Először az első levelet tette le az asztalra. Aztán érkezett egy második levél, és az első tetejére tette . A harmadik betűt a másodikra, a negyediket a harmadikra ​​tette. És most válaszoljon egy egyszerű kérdésre: melyik levelet olvassa el először , amikor visszatér a szobájába, és meglátja a kupacot az asztalon? Rendben, a legfelsőt fogod olvasnilevél. Vagyis az, amelyik legutóbb érkezett . Pontosan így működik egy verem. Ezt az elvet „utolsó az elsőben” (LIFO) nevezik . Mire jók a stackek? Nos, tegyük fel, hogy valamilyen kártyajátékot készít Java nyelven. Egy pakli kártya hever az asztalon. A kijátszott kártyákat eldobjuk. A húzópakli és a dobópakli megvalósításához két verem használható. A játékosok a pakli tetejéről veszik fel kártyáikat, ugyanazt az elvet követve, mint az üzleti leveleknél. Amikor a játékosok kártyákat tesznek a dobott pakliba, az újonnan eldobott kártyák a régiek tetejére kerülnek. Íme az első próbálkozásunk a játékkal, egy verem alapján megvalósítva:

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

Ahogy korábban is mondtuk, két kupacunk van: egy húzópakli és egy dobópakli. A Java-ban a verem adatstruktúra az osztályban van megvalósítva java.util.Stack. Kártyajátékunk 3 módszerrel írja le a játékosok cselekedeteit:

• vegyél ki egy kártyát a pakliból ( getCardFromDeck()módszer)
• kártya eldobása ( discard()módszer)
• nézd meg a felső kártyát ( lookAtTopCard()módszer). Tegyük fel, hogy ez egy „Intelligencia” bónusz, amely lehetővé teszi a játékos számára, hogy megtudja, melyik kártya következik a következő játékban.

Metódusainkon belül a Stack osztály következő metódusait hívjuk:

• push()— hozzáad egy elemet a köteg tetejéhez. Amikor egy kártyát küldünk a dobott pakliba, az a pakli tetejére kerül
• pop()— eltávolítja a felső elemet a kötegből, és visszaadja. Ez a módszer tökéletes olyan akciók végrehajtására, amelyek során a játékos kártyát húz.
• peek()— visszaadja a verem legfelső elemét, de nem távolítja el a veremből

Lássuk, hogyan fog működni a játékunk:

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

Öt lapot adtunk a paklinkba. Az első játékos 3-at vett belőlük. Milyen kártyákat kapott? Konzol kimenet:

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

Ügyeljen arra, hogy a kártyák milyen sorrendben jelenjenek meg a konzolon. Az "Edwin VanCleef" kártya utoljára került a pakliba (ez volt az ötödik lap), és ezt a kártyát húzta először a játékos. "Malomház" az utolsó előtti helyen végzett a pakliban, a játékos pedig másodikként húzta be. "Sylvanas" felülről harmadikként ment be a pakliba, és ez volt a harmadik kártya, amit a játékos húzott. Ezután a játékos eldobja a kártyákat. Először Edwint, majd Millhouse-t, majd Sylvanast dobja el. Ezután egyesével megjelenítjük a dobott pakliban lévő kártyákat: Konzol kimenet:

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

Ismét látjuk, hogyan működik a verem! A mi játékunkban a dobópakli is egy halom (akárcsak a húzópakli). Először "Edwin VanCleef"-et dobták ki. A második eldobott kártya a Millhouse Manastorm volt, és Edwin tetejére került a dobópakliba. Aztán Sylvanast eldobták, és ezt a kártyát a Millhouse tetejére helyezték. Amint látja, a veremben nincs semmi bonyolult. Ennek ellenére ismernie kell ezt az adatstruktúrát – gyakran kérdezik rá az állásinterjúkon, és gyakran ez az alapja az összetettebb adatstruktúrák felépítésének.

Sor Java nyelven

A sor egy másik gyakori adatstruktúra. A veremeken kívül számos programozási nyelv, köztük a Java is megvalósítja a soradat-struktúrát. Mi a különbség a sor és a verem között? A sor nem a LIFO elven, hanem inkább a FIFO elven alapul ("first in, first out"). Ez az alapelv könnyen megérthető, ha például egy közönséges vonalat vagy sort a valóságban figyelembe veszünk! Például egy sor az élelmiszerboltban. Ha öt ember van a sorban, akkor az lesz az első, aki először lépett be a sorba . Ha egy másik személy (a már sorban álló öten kívül) vásárolni akar valamit és beáll a sorba, akkor őt szolgálják ki utoljára, azaz hatodik. A sorral való munka során új elemeket adnak a farokhoz (hátul), és ha elemet akarunk kapni, akkor azt a fejből (elöl) veszik. Ez a fő elv, amelyet emlékeznie kell a sor működésére vonatkozóan. A várólisták működése nagyon intuitív, mivel a való életben gyakran találkozunk sorokkal. Külön érdemes megjegyezni, hogy a Java-ban a queue-t nem egy osztály, hanem egy interfész reprezentálja: Queue. Sőt, ennek a várólista felületnek számos implementációja létezik Java nyelven. Ha megnézzük az Oracle dokumentációját, látni fogjuk, hogy 4 különböző interfész, valamint egy rendkívül lenyűgöző osztálylista örökli a Queue felületet:

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

Micsoda nagy lista! De természetesen most nem kell ezeket az osztályokat és felületeket memorizálnia – felrobbanhat a feje :) Csak néhányat veszünk figyelembe a legfontosabb és legérdekesebb szempontok közül. Először is figyeljünk a Queue négy "alinterfésze" egyikére: a Deque . Mitől olyan különleges? Az A Dequeegy kétvégű sor. Kibővíti a normál várólisták funkcionalitását, lehetővé téve, hogy elemeket adjon hozzá a sor mindkét végéhez (az elejéhez és a végéhez), és vegyen át elemeket a sor mindkét végéről. A kétvégű várólisták széles körben használatosak a szoftverfejlesztésben. Ügyeljen a fent megadott sorosztályok listájára. A lista elég hosszú, de van benne valami ismerős?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Itt a régi barátunk LinkedList! Tehát megvalósítja a Queue felületet? De hogy lehet sor? Hiszen a egy LinkedListlinkelt lista! Ez igaz, de ez nem akadályozza meg, hogy sor legyen :) Íme egy lista az összes interfészről, amelyet megvalósít:

All implemented interfaces:

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

Mint látható, LinkedListmegvalósítja az Dequeinterfészt (ez ismét kétvégű queue-t jelent). Miért van erre szükség? Ez lehetővé teszi számunkra, hogy elemeket kapjunk az elejétől és a végétől LinkedList. Azt is lehetővé teszi, hogy elemeket adjunk hozzá az elejéhez és a végéhez. Íme LinkedLista felületről származó metódusok Deque:

• peekFirst()— visszaadja az első elemet (de nem távolítja el a sorból).
• peekLast()— visszaadja az utolsó elemet (de nem távolítja el a sorból).
• pollFirst()— visszaadja az első elemet a sorból, és eltávolítja azt.
• pollLast()— visszaadja a sor utolsó elemét, és eltávolítja azt.
• addFirst()— új elemet ad a sor elejére.
• addLast()— hozzáad egy elemet a sor végéhez.

Mint látható, LinkedListteljes mértékben megvalósítja a kétvégű sor funkcióit! És kell ilyen funkcionalitás a programodban, tudni fogod, hol találod :) A mai lecke a végéhez közeledik. Befejezésül adok néhány linket további olvasnivalókhoz. Először is figyeljen erre a PriorityQueue-ról szóló cikkre . Ez az egyik legérdekesebb és leghasznosabb Queuemegvalósítás. Tegyük fel például, hogy 50 ember áll sorban az üzletében, és közülük 7 VIP ügyfél. A PriorityQueue segítségével először kiszolgálhatja őket! Nagyon hasznos cucc, igaz? :) Másodszor, nem ártana még egyszer megemlíteni Robert Lafore "Data Structures and Algorithms in Java" című könyvét.. Ha elolvassa ezt a könyvet, nemcsak sok adatstruktúrát (beleértve a veremeket és a sorokat) ismerheti meg, hanem ezek közül sokat saját maga is megvalósíthat! Például mi van, ha a Java-nak nem lenne Stack osztálya? Mit tenne, ha szüksége lenne egy ilyen adatszerkezetre a programjához? Természetesen magának kell megírnia. Miközben Lafore könyvét olvassa , gyakran ezt teszi. Ennek eredményeképpen az adatstruktúrák megértése sokkal mélyebb lesz, mint amit egy egyszerű elmélettanulmányozással kapna :) Az elméletet mára lezárjuk, de az elmélet gyakorlat nélkül semmi! A feladatok nem oldódnak meg maguktól, úgyhogy ideje foglalkozni velük! :)