Java-da maglumat gurluşlary - Stack we nobat

Salam! Bu gün maglumat gurluşlary ýaly islendik programmist üçin möhüm zatlar hakda gürleşeris . Wikipediýa şeýle diýýär: Maglumatlaryň gurluşy ( iňlis maglumat gurluşy ) hasaplaýyşda birmeňzeş we / ýa-da logiki taýdan baglanyşykly maglumatlary köp saklamaga we gaýtadan işlemäge mümkinçilik berýän programma üpjünçiligi bölümi. Kesgitleme birneme bulaşyk, ýöne manysy aýdyň. Maglumat gurluşy, mundan beýläk ulanmak üçin maglumatlary saklaýan bir görnüşdir. Programmirlemekde maglumatlaryň dürli-dürli bolmagy bar. Belli bir meseläni çözmekde köplenç iň möhüm zat, bu maksat üçin iň amatly maglumat gurluşyny saýlamakdyr. Olaryň köpüsi bilen eýýäm tanyş! Mysal üçin, massiwler bilen . Şeýle hem Map(köplenç “sözlük”, “karta” ýa-da “assosiatiw massiw” hökmünde terjime edilýär). Düşünmek gaty möhümdir: maglumat gurluşlary haýsydyr bir dile bagly däl . Bular diňe abstrakt “meýilnamalar” bolup, her bir programmirleme dili öz synplaryny döredýär - bu gurluşyň durmuşa geçirilmegi. Mysal üçin, iň meşhur maglumat gurluşlaryndan biri baglanyşdyrylan sanawdyr . Wikipediýa girip, onuň nähili işleýändigini, haýsy artykmaçlyklaryny we kemçiliklerini okap bilersiňiz. Onuň kesgitlemesini tanyş tapyp bilersiňiz :) “Baglanan sanaw, düwünlerden ybarat kompýuter biliminde esasy dinamiki maglumatlar gurluşy bolup, olaryň hersinde maglumatlaryň özi we indiki we / ýa-da bir ýa-da iki baglanyşyk (“ baglanyşyk ”) bar. öňki düwün sanawy ” Diýmek, bu biziňki LinkedList! Takyk, ine şeýle bolýar :) Baglanan sanaw maglumat gurluşy synpda Java dilinde amala aşyrylýar LinkedList. Otheröne beýleki diller hem baglanyşyk sanawlaryny durmuşa geçirýärler! Pythonda "" llist", Scala-da Java-daky ýaly" - LinkedList"diýilýär. Baglanan sanaw esasy umumy maglumat gurluşlaryndan biridir, şonuň üçin ony häzirki zaman programmirleme dilinde tapyp bilersiňiz. Assosiatiw massiw bilen birmeňzeş zat. Wikipediýadan onuň kesgitlemesi: Assosiatiw massiw abstrakt maglumat görnüşidir (maglumat dükanyna interfeýs), jübütleri “(açar, baha)” saklamaga mümkinçilik berýär we jübüt goşmak amallaryny goldaýar, şeýle hem gözleg. we jübüti açar bilen pozmak. Size hiç zady ýatlatmaýarmy? :) Takyk, biziň üçin Javaistler üçin assosiatiw massiw interfeýsdirMap. Emma bu maglumat gurluşy beýleki dillerde-de amala aşyrylýar! Mysal üçin, C # programmistler muny "Sözlük" ady bilen bilýärler. Ruby dilinde bolsa “Haş” atly synpda durmuşa geçirilýär. Umuman aýdanyňda, manysynyň nämedigine takmynan düşünýärsiňiz: maglumatlar gurluşy, her belli bir dilde başgaça ýerine ýetirilýän ähli programmirleme üçin umumy zat. Bu gün şeýle iki gurluşy öwreneris we olaryň Java-da nähili ýerine ýetirilýändigini göreris - stack we nobat.

Java-da saklaň

Ackygyndy belli maglumatlar gurluşydyr. Bu gaty ýönekeý we gündelik durmuşymyzdan köp zatlar stak hökmünde “durmuşa geçirilýär”. Simpleönekeý ýagdaýy göz öňüne getiriň: myhmanhanada ýaşaýarsyňyz we gündizine iş hatlaryny alarsyňyz. Şol wagt otagda däldigiňiz üçin myhmanhananyň işgäri gelýän hatlary stoluňyza goýdy. Ilki bilen birinji haty stoluň üstünde goýdy. Soň ikinjisi gelip, birinjisiniň üstünde goýdy. Ikinji harpy ikinji, dördünji harpy bolsa üçünji hatyň üstünde goýdy. Indi ýönekeý bir soraga jogap beriň: otagyňyza gelip, stoluň üstünde bir bölek göreniňizde ilki haýsy harpy okarsyňyz ? Dogry, ýokarky harpy okarsyňyz. Lastagny, soňky gezek gelen . Stakanyň işleýşi şu. Bu iş prinsipine LIFO diýilýär - “iň soňky - ilki çykýar” (“iň soňkusy, ilki çykýar”). Stak näme üçin peýdaly bolup biler? Mysal üçin, Java-da haýsydyr bir kart oýny döredýärsiňiz. Stoluň üstünde kartoçkalaryň bir bölegi ýatyr. Oýnalan kartlar taşlanýar. Iki palta ulanyp, palubany we taşlamagy amala aşyryp bilersiňiz. Oýunçylar palubanyň ýokarsyndan kartoçkalar çekýärler - harplar bilen deň prinsip. Oýunçylar kartoçkalary taşlanda, köne kartoçkalaryň üstünde täze kartoçkalar goýulýar. Ine, oýunjagymyzyň ilkinji görnüşi nähili bolar:

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 {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       graveyard.push(card);
   }

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

Öň hem aýdyşymyz ýaly, iki sany stakanymyz bar: paluba we taşlamak. Stack maglumat gurluşy Java-da ýerine ýetirilýär java.util.Stack. Kart oýnumyzda oýunçylaryň hereketlerini suratlandyrýan 3 usul bar:

• palubadan kartoçka alyň (usul getCardFromDeck());
• kartoçkany taşlamak (usul discard());
• ýokarky karta (usul) serediň lookTopCard(). Bu oýnaýja indiki haýsy kartyň oýnajakdygyny anyklamaga mümkinçilik berýän “Akyl” bonus mehaniki boljakdygyny aýdalyň.

Usullarymyzyň içinde synp usullary diýilýär Stack:

• push()- stakanyň ýokarsyna bir element goşýar. Kartany taşlanymyzda, ozal taşlanan kartoçkalaryň üstünde durýar;
• pop()- ýokarky elementi stakadan aýyrýar we yzyna berýär. Bu usul “pleýer kartoçka çekýär” mehanikini durmuşa geçirmek üçin amatlydyr.
• peek()- stakanyň ýokarky elementini gaýtaryp berýär, ýöne ony stakadan aýyrmaýar

Oýnumyzyň nähili işlejekdigini göreliň:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

Şeýlelik bilen palubamyza bäş kartoçka goşduk. Ilkinji oýunçy olardan 3-sini aldy. Ol haýsy kartoçkalary aldy? Konsol çykyşy:

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

Kartlaryň konsola çykan tertibine üns beriň. “Edwin Wan Kleýf” kartoçkasyna iň soňky urlan kartoçka (yzly-yzyna bäşinji) we oýunçynyň birinji alan kartoçkasydy. “Miçlaus” paluba ikinji gezek degdi, oýunçy bolsa ikinji boldy. “Silwanas” palubanyň soňundan üçünji ýere degdi we üçünji oýunçynyň ýanyna gitdi. Soň bolsa, oýunçy kartoçkalaryny taşlaýar. Ilki Edwini, soň Millhouse, soň bolsa Silwanany taşlaýar. Ondan soň taşlan kartalarymyzy ýeke-ýekeden çykarýarys: Konsola çykyş:

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

Ackene-de stakanyň nähili işleýändigini görýäris! Oýnumyzdaky taşlamak hem palta (edil paluba ýaly). Ilkinji bolup düşen “Edwin Wan Klif”. Ikinjisi bolsa “Millhouse Manastorm” boldy we Edwiniň üstünde taşlandy. Soň Silwanas taşlandy - bu kartoçka Millhouseyň üstünde goýuldy. Görşüňiz ýaly, stakanyň işleýşinde çylşyrymly zat ýok. Şeýle-de bolsa, bu maglumat gurluşyny bilmek zerur - köplenç söhbetdeşliklerde soralýar we has çylşyrymly maglumat gurluşlary köplenç onuň esasynda gurulýar.

Nobat

Bir nobat (ýa-da iňlis dilinde “nobat”) başga bir umumy maglumat gurluşydyr. Stak ýaly, Java ýaly köp programma dillerinde ýerine ýetirilýär. Bir nobat bilen stakanyň arasynda näme tapawut bar? Onuň nobaty LIFO-a esaslanman, başga bir prinsipde - FIFO (“ilki bilen - ilki çykýar”, “ilki bilen - ilki çykýar”) esaslanýar . Muňa mysal hökmünde düşünmek aňsat ... ýa-da iň bolmanda hakyky durmuşdan adaty, hakyky nobat! Mysal üçin, dükana nobat. Eger nobatda bäş adam bar bolsa, nobatda duran ilkinji adam dükana girer . Moreene bir adam (nobatdaky bäşden başga) bir zat satyn almak islese we nobata dursa, dükana iň soňky , ýagny altynjy girýär . Bir nobat bilen işläniňizde, soňuna täze elementler goşulýar we bir element almak isleseňiz, başyndan alynar. Bu onuň işiniň esasy ýörelgesidir, ýadyňyzda saklamaly. Nobatyň ýörelgesine içgin düşünmek gaty aňsat, sebäbi hakyky durmuşda köplenç duş gelýär. Java-da nobatyň synp tarapyndan däl-de, interfeýs arkaly görkezilýändigini aýratyn bellemelidiris Queue. Theöne şol bir wagtyň özünde, Java-da nobat köp ýerine ýetirilýän interfeýsdir. Oracle resminamalaryna göz aýlasak, 4 dürli interfeýsiň we gaty täsirli synplaryň sanawynyň nobatdan miras galandygyny göreris:

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

Bu nähili uly sanaw! , Öne, elbetde, indi bu synplaryň we interfeýsleriň hemmesini ýatda saklamagyň zerurlygy ýok - kelläňiz ýarylyp biler :) Iň möhüm we gyzykly nokatlaryň diňe ikisine serederis. Ilki bilen, nobatyň dört “kiçi interfeýsiniň” birine üns bereliň - Deque. Munuň üçin aýratyn näme bar? Deque- Bu iki taraplaýyn nobat. Iki ujuna (nobatyň başy we soňy) elementleri goşmaga we nobatyň iki ujundan elementleri almaga mümkinçilik bermek bilen yzygiderli nobatyň işleýşini giňeldýär. Deque ösüşde giňden ulanylýar. Aboveokarda beren nobat sapaklarymyzyň sanawyna üns beriň. Sanaw gaty uzyn, ýöne ol ýerde bize tanyş bir zat barmy?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, şonuň üçin köne dostumyz şu ýerde LinkedList! ? Agny, interfeýsi durmuşa geçirýärmi Queue? Heöne nädip nobata durup biler? Galyberse-de LinkedList, bu baglanyşykly sanaw! Dogry, ýöne bu nobata durmagyň öňüni almaýar :) Ine, ýerine ýetirýän ähli interfeýsleriň sanawy:

All Implemented Interfaces:

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

Görşüňiz ýaly, LinkedListol interfeýsi Deque- iki taraplaýyn nobaty amala aşyrýar. Bu näme üçin zerur? Munuň kömegi bilen, başyndan we ahyryndan elementleri alyp bileris LinkedList. Şeýle hem, başlangyja we ahyryna element goşuň. LinkedListIne, interfeýsden miras galan usullar Deque:

• peekFirst()- birinji elementi gaýtarýar (ýöne nobatdan aýyrmaýar).
• peekLast()- iň soňky elementi gaýtarýar (ýöne nobatdan aýyrmaýar).
• pollFirst()- birinji elementi nobatdan yzyna getirýär we aýyrýar.
• pollLast()- iň soňky elementi nobatdan yzyna getirýär we aýyrýar.
• addFirst()- nobatyň başyna täze element goşýar.
• addLast()- nobatyň soňuna bir element goşýar.

Görşüňiz ýaly, LinkedListbu iki taraplaýyn nobatyň işleýşini doly ýerine ýetirýär! Programmada şeýle işlemek zerur bolsa, ulanyp boljakdygyny bilersiňiz :) Şu günki leksiýamyz tamamlanýar. Ahyrynda, has giňişleýin okamak üçin size birnäçe baglanyşyk bererin. Ilki bilen “PriorityQueue ” - “ileri tutulýan nobat” bagyşlanan makala üns beriň . Bu nobatyň iň gyzykly we peýdaly durmuşa geçirişlerinden biridir. Mysal üçin, dükanyňyzda 50 adam nobata dursa we olaryň 7-si VIP müşderisi bolsa, PriorityQueuesize ilki bilen hyzmat etmäge mümkinçilik berer! Örän peýdaly zat, razy dälmi? :) Ikinjiden, Robert Laforetiň “Java-daky maglumatlar gurluşlary we algoritmleri” atly kitabyny ýene bir gezek ýatlamak artykmaç bolmaz . Kitaby okaýarkaňyz, diňe bir köp sanly maglumat strukturasyny öwrenmersiňiz (stakany we nobaty goşmak bilen), eýsem olaryň köpüsini özüňiz durmuşa geçirersiňiz! Mysal üçin, Java-da Stack synpynyň ýokdugyny göz öňüne getiriň. Programmaňyz üçin şeýle maglumat gurluşy gerek bolsa näme ederdiňiz? Elbetde, muny özüm ýazmaly bolardym. Laforetiň kitabyny okanyňda , köplenç seniň etjek zadyň şu. Munuň netijesinde maglumat gurluşlaryna düşünişiňiz diňe teoriýany öwrenmekden has giň bolar :) Biz şu günki gün teoriýa bilen tamamlandyk, ýöne tejribe bolmasa teoriýa hiç zat däl! Meseleler özlerini çözüp bilmez, şonuň üçin indi olary çözmegiň wagty geldi! :)