Mga Structure ng Data sa Java - Stack at Queue

Kamusta! Ngayon ay pag-uusapan natin ang mga mahahalagang bagay para sa sinumang programmer bilang mga istruktura ng data . Sabi ng Wikipedia: Ang istraktura ng data ( eng. istruktura ng data ) ay isang yunit ng software na nagbibigay-daan sa iyong mag-imbak at magproseso ng maraming parehong uri at/o data na nauugnay sa lohikal na pag-compute. Ang kahulugan ay medyo nakakalito, ngunit ang kakanyahan nito ay malinaw. Ang istraktura ng data ay isang uri ng imbakan kung saan kami nag-iimbak ng data para sa karagdagang paggamit. Mayroong isang malaking pagkakaiba-iba ng mga istruktura ng data sa programming. Kadalasan, kapag nilulutas ang isang partikular na problema, ang pinakamahalagang bagay ay ang pagpili ng pinaka-angkop na istraktura ng data para sa layuning ito. At pamilyar ka na sa marami sa kanila! Halimbawa, may mga arrays . At gayundin sa Map(na karaniwang isinasalin bilang "diksyonaryo", "mapa", o "nag-uugnay na hanay"). Napakahalagang maunawaan: ang mga istruktura ng data ay hindi nakatali sa anumang partikular na wika . Ang mga ito ay simpleng abstract na "mga blueprint" ayon sa kung saan ang bawat programming language ay lumilikha ng sarili nitong mga klase - mga pagpapatupad ng istrukturang ito. Halimbawa, ang isa sa mga pinakatanyag na istruktura ng data ay ang naka-link na listahan . Maaari kang pumunta sa Wikipedia, basahin ang tungkol sa kung paano ito gumagana, kung ano ang mga pakinabang at disadvantages nito. Maaaring pamilyar ang kahulugan nito :) "Ang naka-link na listahan ay isang pangunahing dynamic na istruktura ng data sa computer science, na binubuo ng mga node, na ang bawat isa ay naglalaman ng parehong data mismo at isa o dalawang link ("mga link") sa susunod at/o nakaraang listahan ng node” Kaya ito ay atin LinkedList! Eksakto, ganyan yan :) Ang naka-link na istraktura ng data ng listahan ay ipinatupad sa wikang Java sa klase LinkedList. Ngunit ang ibang mga wika ay nagpapatupad din ng mga naka-link na listahan! Sa Python ito ay tinatawag na " llist", sa Scala ito ay tinatawag na katulad ng sa Java - " LinkedList". Ang isang naka-link na listahan ay isa sa mga pangunahing karaniwang istruktura ng data, kaya makikita mo ang pagpapatupad nito sa anumang modernong programming language. Parehong bagay sa isang associative array. Narito ang kahulugan nito mula sa Wikipedia: Ang associative array ay isang abstract na uri ng data (isang interface sa isang data store) na nagbibigay-daan sa pag-imbak ng mga pares ng form na "(key, value)" at sumusuporta sa mga operasyon ng pagdaragdag ng isang pares, pati na rin ang paghahanap at pagtanggal ng isang pares sa pamamagitan ng key. Hindi nagpapaalala sa iyo ng kahit ano? :) Eksakto, para sa aming mga Javaist, ang isang associative array ay isang interfaceMap. Ngunit ang istraktura ng data na ito ay ipinatupad din sa ibang mga wika! Halimbawa, alam ito ng mga programmer ng C# sa ilalim ng pangalang "Diksyunaryo". At sa wikang Ruby ito ay ipinatupad sa isang klase na tinatawag na "Hash". Sa pangkalahatan, halos nauunawaan mo kung ano ang kahulugan: ang istraktura ng data ay isang bagay na karaniwan sa lahat ng programming, na ipinapatupad nang iba sa bawat partikular na wika. Ngayon ay pag-aaralan natin ang dalawang ganoong istruktura at tingnan kung paano ito ipinatupad sa Java - stack at queue.

Stack sa Java

Ang stack ay isang kilalang istruktura ng data. Ito ay napaka-simple at medyo maraming mga bagay mula sa ating pang-araw-araw na buhay ay "ipinatupad" bilang isang stack. Isipin ang isang simpleng sitwasyon: nakatira ka sa isang hotel, at sa araw na nakatanggap ka ng mga liham pangnegosyo. Dahil wala ka sa kwarto noon, inilagay lang ng empleyado ng hotel ang mga papasok na letra sa iyong mesa. Una niyang inilagay ang unang letra sa mesa. Pagkatapos ay dumating ang pangalawa at inilagay niya ito sa ibabaw ng una. Inilagay niya ang ikatlong titik na dumating sa ibabaw ng pangalawa, at ang pang-apat sa ibabaw ng pangatlo. Ngayon, sagutin ang isang simpleng tanong: anong liham ang una mong babasahin pagdating mo sa iyong silid at makakita ng isang salansan sa mesa? Tama, babasahin mo ang pinakataas na titik. Ibig sabihin, ang huling dumating sa oras . Ito ay eksakto kung paano gumagana ang isang stack. Ang prinsipyo ng operasyon na ito ay tinatawag na LIFO - "huling in - unang lumabas" ("huling pumasok, unang lumabas"). Ano ang maaaring maging kapaki-pakinabang ng isang stack? Halimbawa, gumagawa ka ng ilang uri ng laro ng card sa Java. Isang deck ng mga baraha ang nakalatag sa mesa. Ang mga nilalaro na card ay itinatapon. Maaari mong ipatupad ang parehong deck at ang discard gamit ang dalawang stack. Ang mga manlalaro ay gumuhit ng mga card mula sa tuktok ng deck - ang parehong prinsipyo tulad ng sa mga titik. Kapag itinapon ng mga manlalaro ang mga card, ang mga bagong card ay inilalagay sa ibabaw ng mga luma. Narito kung ano ang magiging hitsura ng unang draft ng aming laro, na ipinatupad gamit ang isang 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 {

   //  колода
   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();
   }

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

Gaya ng sinabi namin kanina, mayroon kaming dalawang stack: ang deck at ang discard. Ang stack data structure ay ipinatupad sa Java sa java.util.Stack. Sa aming card game mayroong 3 pamamaraan na naglalarawan sa mga aksyon ng mga manlalaro:

• kumuha ng card mula sa deck (paraan getCardFromDeck());
• itapon ang card (paraan discard());
• tingnan ang itaas na card (paraan lookTopCard()). Sabihin nating ito ang magiging bonus na mekaniko na “Intelligence”, na magbibigay-daan sa manlalaro na malaman kung aling card ang susunod na papasok.

Sa loob ng aming mga pamamaraan, ang mga pamamaraan ng klase ay tinatawag na Stack:

• push()— nagdaragdag ng elemento sa tuktok ng stack. Kapag itinapon namin ang isang card, napupunta ito sa ibabaw ng mga dati nang itinapon na card;
• pop()— inaalis ang tuktok na elemento mula sa stack at ibinabalik ito. Ang pamamaraang ito ay mainam para sa pagpapatupad ng mekaniko na "gumuguhit ng card ang manlalaro.
• peek()- ibinabalik ang tuktok na elemento ng stack, ngunit hindi ito inaalis mula sa stack

Tingnan natin kung paano gagana ang aming laro:

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

Kaya nagdagdag kami ng limang card sa aming deck. Kinuha ng unang manlalaro ang 3 sa kanila. Anong mga card ang nakuha niya? Output ng console:

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

Bigyang-pansin ang pagkakasunud-sunod kung saan ang mga card ay na-output sa console. Ang card na "Edwin Van Cleiff" ang huling tumama sa deck (ikalima sa isang hilera), at ito ang card na unang kinuha ng manlalaro. Ang "Michhlaus" ay tumama sa deck ng pangalawa hanggang sa huli, at ang manlalaro nito ay pumangalawa. Ang "Sylvanas" ay tumama sa deck na pangatlo mula sa dulo, at napunta sa ikatlong manlalaro. Susunod, itinatapon ng manlalaro ang kanyang mga card. Una niyang binitawan si Edwin, pagkatapos ay Millhouse, pagkatapos ay si Sylvanas. Pagkatapos nito, isa-isa naming inilabas sa console ang mga card na nasa aming itinatapon: Output sa console:

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

At muli nakita natin kung paano gumagana ang stack! Ang pagtatapon sa aming laro ay isang stack din (tulad ng deck). Si "Edwin Van Clyffe" ang unang na-drop. Ang pangalawang ibinaba ay ang "Millhouse Manastorm" - at humiga sa ibabaw ni Edwin sa itinapon. Susunod, itinapon si Sylvanas - at ang card na ito ay nakahiga sa ibabaw ng Millhouse. Tulad ng nakikita mo, walang kumplikado tungkol sa kung paano gumagana ang stack. Gayunpaman, kinakailangang malaman ang istraktura ng data na ito - madalas itong itanong sa mga panayam, at ang mas kumplikadong mga istruktura ng data ay madalas na itinayo sa batayan nito.

Nakapila

Ang queue (o, sa English, “Queue”) ay isa pang karaniwang istruktura ng data. Tulad ng isang stack, ito ay ipinatupad sa maraming mga programming language, kabilang ang Java. Ano ang pagkakaiba sa pagitan ng isang pila at isang stack? Ang pila nito ay hindi batay sa LIFO, ngunit sa isa pang prinsipyo - FIFO (“first in - first out”, “first in - first out”) . Madaling maunawaan, kunin bilang isang halimbawa... o hindi bababa sa isang ordinaryong, totoong pila mula sa totoong buhay! Halimbawa, isang pila sa tindahan. Kung mayroong limang tao sa linya, ang unang tao sa linya ay papasok sa tindahan . Kung ang isa pang tao (maliban sa limang nasa linya) ay gustong bumili ng isang bagay at pumila, pagkatapos ay papasok siya sa tindahan huling , iyon ay, ikaanim. Kapag nagtatrabaho sa isang queue, ang mga bagong elemento ay idinagdag sa dulo, at kung nais mong makakuha ng isang elemento, ito ay kukunin mula sa simula. Ito ang pangunahing prinsipyo ng pagpapatakbo nito, na kailangan mong tandaan. Ang prinsipyo ng queue ay napakadaling maunawaan nang intuitive, dahil madalas itong nakatagpo sa totoong buhay. Ito ay nagkakahalaga ng noting nang hiwalay na sa Java ang isang queue ay kinakatawan hindi ng isang klase, ngunit sa pamamagitan ng isang interface - Queue. Ngunit sa parehong oras, ang isang queue sa Java ay isang interface na may maraming mga pagpapatupad. Kung titingnan natin ang dokumentasyon ng Oracle, makikita natin na 4 na magkakaibang mga interface at isang napaka-kahanga-hangang listahan ng mga klase ay minana mula sa pila:

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

Napakalaking listahan! Ngunit, siyempre, hindi mo kailangang kabisaduhin ang lahat ng mga klase at interface na ito ngayon - maaaring sumabog ang iyong ulo :) Titingnan lamang natin ang ilang pinakamahalaga at kawili-wiling mga punto. Una, bigyang-pansin natin ang isa sa apat na "sub-interface" ng pila - Deque. Ano ang espesyal dito? Deque- Ito ay isang two-way queue. Pinapalawak nito ang functionality ng isang regular na pila sa pamamagitan ng pagpapahintulot sa iyong magdagdag ng mga elemento sa magkabilang dulo (sa simula at dulo ng queue) at kumuha ng mga elemento mula sa magkabilang dulo ng pila. Ang deque ay malawakang ginagamit sa pag-unlad. Bigyang-pansin ang listahan ng mga klase ng queue na ibinigay namin sa itaas. Ang listahan ay medyo mahaba, ngunit mayroon bang anumang bagay na pamilyar sa atin doon?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, kaya nandito ang dati nating kaibigan LinkedList! Iyon ay, ipinapatupad nito ang interface Queue? Pero paano siya magiging pila? Pagkatapos ng lahat LinkedList, ito ay isang konektadong listahan! Totoo, ngunit hindi nito pinipigilan ang pagiging isang queue :) Narito ang isang listahan ng lahat ng mga interface na ipinapatupad nito:

All Implemented Interfaces:

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

Tulad ng nakikita mo, LinkedListnagpapatupad ito ng interface Deque- isang two-way queue. Bakit kailangan ito? Salamat dito, makakakuha tayo ng mga elemento mula sa simula at sa wakas LinkedList. At din - magdagdag ng mga elemento sa parehong simula at wakas. Narito ang mga pamamaraan na minana LinkedListmula sa interface Deque:

• peekFirst()— ibinabalik (ngunit hindi inaalis mula sa pila) ang unang elemento.
• peekLast()— ibinabalik (ngunit hindi inaalis mula sa pila) ang huling elemento.
• pollFirst()- ibinabalik ang unang elemento mula sa pila at inaalis ito.
• pollLast()- ibinabalik ang huling elemento mula sa pila at inaalis ito.
• addFirst()— nagdaragdag ng bagong elemento sa simula ng pila.
• addLast()— nagdaragdag ng elemento sa dulo ng pila.

Gaya ng nakikita mo, LinkedListganap nitong ipinapatupad ang functionality ng isang two-way queue! At kung kailangan ang ganitong functionality sa programa, malalaman mo na magagamit ito :) At magtatapos na ang ating lecture ngayon. Sa wakas, bibigyan kita ng ilang link para sa karagdagang pagbabasa. Una, bigyang pansin ang artikulong nakatuon sa PriorityQueue - "priority queue". Ito ay isa sa mga pinakakawili-wili at kapaki-pakinabang na pagpapatupad ng Queue. Halimbawa, kung mayroong 50 tao sa linya sa iyong tindahan, at 7 sa kanila ay mga kliyenteng VIP, PriorityQueuepapayagan ka nitong pagsilbihan muna sila! Isang napaka-kapaki-pakinabang na bagay, hindi ka ba sumasang-ayon? :) Pangalawa, hindi magiging kalabisan na banggitin muli ang aklat ni Robert Laforet na "Mga Structure ng Data at Algorithm sa Java" . Habang nagbabasa ng libro, hindi ka lang matututo ng maraming istruktura ng data (kabilang ang stack at queue), ngunit ikaw mismo ang magpapatupad ng marami sa mga ito! Halimbawa, isipin kung ang Java ay walang klase ng Stack. Ano ang gagawin mo kung kailangan mo ng ganoong istruktura ng data para sa iyong programa? Siyempre, ako mismo ang magsulat nito. Kapag nagbabasa ng libro ni Laforet, ito ang madalas na gagawin mo. Dahil dito, ang iyong pag-unawa sa mga istruktura ng data ay magiging mas malawak kaysa sa simpleng pag-aaral ng teorya :) Tapos na tayo sa teorya para sa ngayon, ngunit ang teorya na walang kasanayan ay wala! Ang mga problema ay hindi malulutas sa kanilang sarili, kaya ngayon ang oras upang harapin ang mga ito! :)