Mga istruktura ng data: stack at queue

Hi! Ngayon ay pag-uusapan natin ang tungkol sa isang bagay na sobrang mahalaga para sa sinumang programmer: mga istruktura ng data. Sabi ng Wikipedia: "Ang istruktura ng data ay isang organisasyon ng data, pamamahala, at format ng imbakan na nagbibigay-daan sa mahusay na pag-access at pagbabago. inilapat sa data." Ang kahulugan ay medyo nakakalito, ngunit ang diwa nito ay malinaw. Ang istruktura ng data ay isang uri ng repositoryo kung saan kami nag-iimbak ng data para magamit sa hinaharap. Sa programming, mayroong isang malaking pagkakaiba-iba ng mga istruktura ng data. Kapag nilulutas ang mga partikular na problema, kadalasan ang pinakamahalagang bagay ay ang piliin ang pinaka-angkop na istraktura ng data para sa problema. At pamilyar ka na sa marami sa kanila! Halimbawa, alam mo ang tungkol sa mga array. At pamilyar ka rinMap(ang istruktura ng data na ito ay maaari ding tukuyin bilang isang "diksyonaryo" o "nag-uugnay na hanay"). Napakahalagang maunawaan na ang mga istruktura ng data ay hindi nakatali sa anumang partikular na wika. Ang mga ito ay simpleng abstract na "mga blueprint" na ginagamit ng bawat programming language upang lumikha ng sarili nitong mga klase o pagpapatupad ng isang partikular na istraktura. Halimbawa, ang isa sa mga pinakatanyag na istruktura ng data ay isang naka-link na listahan. Maaari kang pumunta sa Wikipedia at basahin ang tungkol sa kung paano ito gumagana at kung ano ang mga pakinabang at disadvantages nito. Marahil ay tila pamilyar sa iyo ang kahulugan nito :) "Ang isang naka-link na listahan ay isang linear na koleksyon ng mga elemento ng data, na ang pagkakasunud-sunod ay hindi ibinibigay ng kanilang pisikal na pagkakalagay sa memorya. Sa halip, ang bawat elemento ay tumuturo sa susunod." Iyon ay naglalarawan sa ating minamahal LinkedList, hindi ba? Oo, at iyon lang iyon :) Sa Java, ang istraktura ng data na "naka-link na listahan" ay ipinatupad ng LinkedListklase. Ngunit ang ibang mga wika ay nagpapatupad din ng mga naka-link na listahan! Sa Python, ang istruktura ng data na ito ay tinatawag na " llist". Sa Scala ito ay tinatawag na " LinkedList", tulad ng sa Java. Ang isang naka-link na listahan ay isa sa mga pangunahing karaniwang istruktura ng data, kaya makikita mo na ito ay ipinatupad sa anumang modernong programming language. Ang parehong bagay ay totoo sa mga nag-uugnay na array. Narito ang kahulugan mula sa Wikipedia: "Ang nag-uugnay na hanay, mapa, talahanayan ng simbolo, o diksyunaryo ay isang abstract na uri ng data na binubuo ng isang koleksyon ng mga pares ng (key, value), upang ang bawat posibleng key ay lilitaw nang hindi hihigit sa isang beses sa koleksyon." May naaalala ba iyon sa iyo? :) Oo. Para sa amin na mga developer ng Java, ang isang associative array ay angMapinterface. 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 Ruby, ito ay ipinatupad sa isang klase na tinatawag na "Hash". Well, nakuha mo ang punto: ang mga istruktura ng data ay mga pangkalahatang konsepto sa programming, at ang bawat programming language ay nagpapatupad ng mga ito sa sarili nitong paraan. Ngayon ay pag-aaralan natin ang dalawang ganoong istruktura — ang stack at ang pila — at tingnan kung paano ito ipinapatupad sa Java.

Mga stack sa Java

Ang stack ay isang kilalang istruktura ng data. Ito ay napaka-simple. Medyo ilang mga bagay sa ating pang-araw-araw na buhay ay "ipinatupad" bilang isang stack. Isipin ang simpleng sitwasyong ito: nananatili ka sa isang hotel, at sa paglipas ng araw ay nakatanggap ka ng ilang liham pangnegosyo. Wala ka sa iyong silid noong panahong iyon, kaya inilagay na lamang ng klerk ng hotel ang mga papasok na sulat sa iyong mesa. Una, inilagay niya ang unang letra sa mesa. Pagkatapos ay dumating ang pangalawang liham, at inilagay niya ito sa ibabaw ng una. Inilagay niya ang ikatlong titik sa ibabaw ng pangalawa, at ang ikaapat sa ibabaw ng pangatlo. At ngayon, sagutin ang isang simpleng tanong: anong liham ang una mong babasahin kapag bumalik ka sa iyong silid at nakita ang salansan sa mesa? Tama, babasahin mo ang pinakamataassulat. Ibig sabihin, ang pinakahuling dumating . Ito ay eksakto kung paano gumagana ang isang stack. Ang prinsipyong ito ay tinatawag na "last in first out" (LIFO) . Ano ang mabuti para sa mga stack? Well, ipagpalagay na gumagawa ka ng ilang uri ng card game sa Java. Isang deck ng mga baraha ang nakalatag sa mesa. Ang mga nilalaro na baraha ay itinatapon. Maaari kang gumamit ng dalawang stack upang ipatupad ang parehong draw deck at ang discard pile. Kinukuha ng mga manlalaro ang kanilang mga card mula sa tuktok ng deck, na sinusunod ang parehong prinsipyo tulad ng sa iyong mga liham ng negosyo. Kapag ang mga manlalaro ay naglagay ng mga card sa discard pile, ang mga bagong itinapon na card ay inilalagay sa ibabaw ng luma. Narito ang aming unang pagtatangka sa laro, na ipinatupad batay sa 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 {

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

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

• kumuha ng card mula sa deck ( getCardFromDeck()paraan)
• itapon ang isang card ( discard()pamamaraan)
• tingnan ang tuktok na card ( lookAtTopCard()pamamaraan). Sabihin nating ito ay isang "Intelligence" na bonus na nagbibigay-daan sa manlalaro na malaman kung aling card ang susunod na darating sa laro.

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

• push()— nagdaragdag ng item sa tuktok ng stack. Kapag nagpadala kami ng card sa discard pile, papunta ito sa tuktok ng pile
• pop()— inaalis ang tuktok na elemento mula sa stack at ibinabalik ito. Ang pamamaraang ito ay perpekto para sa pagpapatupad ng mga aksyon kung saan ang manlalaro ay gumuhit ng isang card.
• 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) {

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

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

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

Bigyang-pansin ang pagkakasunud-sunod kung saan ipinapakita ang mga card sa console. Ang card na "Edwin VanCleef" ay huling pumasok sa deck (ito ang ikalimang card), at ito ang card na unang iginuhit ng manlalaro. Ang "Millhouse" ay pangalawa sa huli sa deck, at iginuhit ito ng player na pangalawa. Si "Sylvanas" ay pumasok sa deck na pangatlo mula sa itaas, at ito ang ikatlong card na iginuhit ng manlalaro. Susunod, itinatapon ng manlalaro ang mga card. Una, itinapon niya si Edwin, pagkatapos ay Millhouse, pagkatapos ay si Sylvanas. Pagkatapos ay ipinapakita namin ang mga card sa aming discard pile isa-isa: Console output:

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

Muli, nakikita natin kung paano gumagana ang isang stack! Sa aming laro, ang discard pile ay isang stack din (tulad ng draw deck). Tinapon muna ang "Edwin VanCleef". Ang pangalawang card discard ay Millhouse Manastorm, at ito ay inilagay sa ibabaw ni Edwin sa discard pile. Pagkatapos ay itinapon si Sylvanas, at ang card na ito ay inilagay sa ibabaw ng Millhouse. Tulad ng nakikita mo, walang kumplikado tungkol sa isang stack. Gayunpaman, kailangan mong malaman ang istraktura ng data na ito - madalas itong itanong sa panahon ng mga panayam sa trabaho, at madalas itong batayan para sa pagbuo ng mas kumplikadong mga istruktura ng data.

Pila sa Java

Ang queue ay isa pang karaniwang istraktura ng data. Bilang karagdagan sa mga stack, maraming mga programming language, kabilang ang Java, ang nagpapatupad din ng queue data structure. Ano ang pagkakaiba sa pagitan ng isang pila at isang stack? Ang isang queue ay hindi nakabatay sa prinsipyo ng LIFO, ngunit sa halip sa prinsipyo ng FIFO ("first in, first out"). Ang prinsipyong ito ay madaling maunawaan sa pamamagitan ng pagsasaalang-alang, halimbawa, isang ordinaryong linya, o pila, sa totoong buhay! Halimbawa, isang linya sa grocery store. Kung limang tao ang nakapila, ang unang ihain ay ang unang pumasok sa linya . Kung may ibang tao (bukod pa sa lima na nakapila) na gustong bumili ng isang bagay at pumila, pagkatapos ay siya ang huling magsisilbi, iyon ay, ikaanim. Kapag nagtatrabaho sa isang queue, ang mga bagong elemento ay idinagdag sa buntot (likod), at kung nais mong makakuha ng isang elemento, ito ay kukunin mula sa ulo (harap). Ito ang pangunahing prinsipyo na kailangan mong tandaan tungkol sa kung paano gumagana ang isang pila. Napaka-intuitive ng operasyon ng isang queue, dahil madalas kaming nakakahanap ng mga queue sa totoong buhay. Kapansin-pansing hiwalay na sa Java ang isang queue ay kinakatawan hindi ng isang klase, ngunit ng isang interface: Queue. Higit pa rito, maraming mga pagpapatupad ng interface ng queue na ito sa Java. Kung titingnan natin ang dokumentasyon ng Oracle, makikita natin na ang 4 na magkakaibang mga interface, pati na rin ang isang napaka-kahanga-hangang listahan ng mga klase, ay nagmamana ng interface ng 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

Napakalaking listahan! Ngunit, siyempre, hindi mo kailangang kabisaduhin ang lahat ng mga klase at interface na ito sa ngayon — maaaring sumabog ang iyong ulo :) Isasaalang-alang lamang namin ang ilan sa pinakamahalaga at kawili-wiling mga punto. Una, bigyang-pansin natin ang isa sa apat na "subinterface" ng Queue: Deque . Ano ang ginagawa nitong napakaespesyal? Ang A Dequeay isang double-ended na pila. Pinapalawak nito ang functionality ng isang regular na pila, na nagbibigay-daan sa iyong magdagdag ng mga elemento sa magkabilang dulo (sa ulo at buntot) at kumuha ng mga elemento mula sa magkabilang dulo ng pila. Ang mga double-ended queue ay malawakang ginagamit sa pagbuo ng software. Bigyang-pansin ang listahan ng mga klase ng queue na ibinigay namin sa itaas. Ang listahan ay medyo mahaba, ngunit naglalaman ba ito ng anumang pamilyar?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Nandito ang dati nating kaibigan LinkedList! Kaya, ipinapatupad nito ang interface ng Queue? Ngunit paano ito magiging isang pila? Pagkatapos ng lahat, ang a LinkedListay isang naka-link na 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, LinkedListipinapatupad ang Dequeinterface (muli, nangangahulugan ito ng double-ended queue). Bakit kailangan ito? Nagbibigay-daan ito sa amin na makakuha ng mga elemento mula sa simula at dulo ng isang LinkedList. Nagbibigay-daan din ito sa amin na magdagdag ng mga elemento sa simula at wakas. Narito ang mga pamamaraan na LinkedListnakukuha mula sa Dequeinterface:

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

Gaya ng nakikita mo, LinkedListganap na ipinapatupad ang functionality ng isang double-ended queue! At kailangan mo ng ganoong pag-andar sa iyong programa, malalaman mo kung saan ito mahahanap :) Matatapos na ang aralin ngayon. Sa konklusyon, bibigyan kita ng ilang link para sa karagdagang pagbabasa. Una, bigyang pansin ang artikulong ito tungkol sa PriorityQueue . Ito ay isa sa mga pinaka-kawili-wili at kapaki-pakinabang Queuena pagpapatupad. Halimbawa, ipagpalagay na mayroong 50 tao na nakapila sa iyong tindahan, at 7 sa kanila ay mga VIP na customer. Hahayaan ka ng PriorityQueue na pagsilbihan muna sila! Napaka-kapaki-pakinabang na bagay, tama ba? :) Pangalawa, hindi masakit na banggitin muli ang aklat ni Robert Lafore na "Data Structures and Algorithms in Java". Sa pagbabasa ng aklat na ito, hindi ka lamang matututo ng maraming istruktura ng data (kabilang ang stack at queue), ngunit ikaw mismo ang magpapatupad ng marami sa mga ito! Halimbawa, paano kung walang klase ng Stack ang Java? Ano ang gagawin mo kung kailangan mo ng ganoong istruktura ng data para sa iyong programa? Kailangan mong isulat ito sa iyong sarili, siyempre. Habang binabasa mo ang aklat ni Lafore , madalas mong gagawin iyon. Bilang resulta, ang iyong pag-unawa sa mga istruktura ng data ay magiging mas malalim kaysa sa kung ano ang makukuha mo mula sa isang simpleng pag-aaral ng teorya :) Tinatapos namin ang teorya para sa ngayon, ngunit ang teorya na walang kasanayan ay wala! Ang mga gawain ay hindi malulutas ang kanilang mga sarili, kaya oras na upang harapin ang mga ito! :)