Struktur data: tumpukan lan antrian

Hi! Dina iki kita bakal ngomong babagan sing penting banget kanggo programer: struktur data. Wikipedia ngandika: " Struktur data minangka organisasi data, manajemen, lan format panyimpenan sing ngidini akses lan modifikasi sing efisien. Luwih tepat, struktur data minangka kumpulan nilai data, hubungan ing antarane, lan fungsi utawa operasi sing bisa ditindakake. ditrapake kanggo data." Definisi rada mbingungake, nanging intine jelas. Struktur data minangka jinis repositori ing ngendi kita nyimpen data kanggo panggunaan ing mangsa ngarep. Ing pemrograman, ana macem-macem struktur data. Nalika ngrampungake masalah tartamtu, asring banget sing paling penting yaiku milih struktur data sing paling cocok kanggo masalah kasebut. Lan sampeyan wis kenal karo akeh wong! Contone, sampeyan ngerti babagan array. Lan sampeyan uga menowoMap(struktur data iki bisa uga diarani minangka "kamus" utawa "array asosiatif"). Penting banget kanggo mangerteni yen struktur data ora ana gandhengane karo basa tartamtu. Iku mung abstrak "blueprints" sing saben basa program digunakake kanggo nggawe kelas dhewe utawa implementasine saka struktur tartamtu. Contone, salah sawijining struktur data sing paling misuwur yaiku dhaptar sing disambung. Sampeyan bisa pindhah menyang Wikipedia lan maca babagan cara kerjane lan apa kaluwihan lan kekurangane. Mbok menawa definisi kasebut bakal katon akrab karo sampeyan :) "Dhaptar sing disambung minangka koleksi linier saka unsur data, sing urutane ora diwenehake dening panggonan fisik ing memori. Nanging, saben unsur nuding menyang sabanjure." Iki nggambarake kekasih kita LinkedList, ta? Ya, lan mung iku :) Ing Jawa, struktur data "daftar sing disambung" diimplementasikake dening kelas LinkedList. Nanging basa liyane uga ngetrapake dhaptar sing disambung! Ing Python, struktur data iki diarani " llist". Ing Scala diarani " LinkedList", kaya ing Jawa. Dhaptar sing digandhengake minangka salah sawijining struktur data umum dhasar, supaya sampeyan bakal nemokake manawa diimplementasikake ing basa pamrograman modern. Bab sing padha karo susunan asosiatif. Mangkene definisi saka Wikipedia: "Larik asosiatif, peta, tabel simbol, utawa kamus yaiku jinis data abstrak sing kasusun saka kumpulan pasangan (kunci, nilai), saengga saben kunci bisa katon paling akeh sapisan ing koleksi." Apa sing ngelingake sampeyan apa wae? :) Ya wis. Kanggo kita pangembang Jawa, array asosiatif yaikuMapantarmuka. Nanging struktur data iki uga diterapake ing basa liya! Contone, programer C # ngerti kanthi jeneng "Kamus". Lan ing Ruby, dileksanakake ing kelas sing diarani "Hash". Ya, sampeyan entuk titik: struktur data minangka konsep universal ing pemrograman, lan saben basa pamrograman ngetrapake kanthi cara dhewe. Dina iki kita bakal sinau loro struktur kuwi - tumpukan lan antrian - lan ndeleng carane padha dileksanakake ing Jawa.

Tumpukan ing Jawa

Tumpukan minangka struktur data sing kondhang. Iku banget prasaja. Cukup sawetara item ing urip kita saben dina "dilaksanakake" minangka tumpukan. Bayangake kahanan sing prasaja iki: sampeyan lagi nginep ing hotel, lan sajrone dina sampeyan nampa sawetara surat bisnis. Sampeyan ora ana ing kamar nalika iku, dadi petugas hotel mung nyelehake surat sing mlebu ing meja sampeyan. Kaping pisanan, dheweke nyelehake huruf pisanan ing meja. Banjur ana layang kapindho teka, lan diselehake ing ndhuwur sing pisanan. Huruf kaping telu dilebokake ing ndhuwur sing nomer loro, lan sing nomer papat ing ndhuwur nomer telu. Lan saiki, wangsulana pitakonan sing prasaja: huruf apa sing bakal diwaca dhisik nalika bali menyang kamar lan ndeleng tumpukan ing meja? Bener, sampeyan bakal maca sing paling dhuwurlayang. Yaiku sing teka paling anyar . Iki persis carane tumpukan bisa. Prinsip iki diarani "last in first out" (LIFO) . Apa tumpukan apik kanggo? Inggih, umpamane sampeyan nggawe sawetara jinis game kertu ing Jawa. A kelompok kertu dumunung ing meja. Kertu sing diputer dibuwang. Sampeyan bisa nggunakake rong tumpukan kanggo ngetrapake dek tarik lan tumpukan tumpukan. Pemain njupuk kertu saka ndhuwur dek, miturut prinsip sing padha karo surat bisnis sampeyan. Nalika pemain sijine kertu menyang tumpukan discard, kertu mentas dibuwak diselehake ing ndhuwur lawas. Mangkene upaya pertama ing game kasebut, diimplementasikake kanthi basis tumpukan:

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

Kaya sing wis dingerteni sadurunge, kita duwe rong tumpukan: dek tarik lan tumpukan tumpukan. Ing Jawa, struktur data tumpukan dileksanakake ing java.util.Stackkelas. Game kertu kita duwe 3 cara sing nggambarake tumindak para pemain:

• njupuk kertu saka dek ( getCardFromDeck()metode)
• mbuwang kertu ( discard()metode)
• deleng kertu ndhuwur ( lookAtTopCard()cara). Ayo dadi ngomong iki "Intelligence" bonus sing ngidini pamuter kanggo mangerteni kang kertu bakal teka sabanjuré ing game.

Ing metode kita, kita nyebut metode ing ngisor iki saka kelas Stack:

• push()- nambah item menyang ndhuwur tumpukan. Nalika kita ngirim kertu kanggo tumpukan discard, dadi menyang ndhuwur tumpukan
• pop()- mbusak unsur ndhuwur saka tumpukan lan bali. Cara iki sampurna kanggo ngleksanakake tumindak kang pamuter ndudohke kertu.
• peek()- ngasilake unsur ndhuwur tumpukan, nanging ora mbusak saka tumpukan

Ayo ndeleng carane game kita bakal bisa digunakake:

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

Kita nambahake limang kertu menyang dek. Pamuter pisanan njupuk 3 wong. Kertu apa dheweke entuk? Output konsol:

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

Pay manungsa waé menyang urutan kang kertu ditampilake ing console. Kertu "Edwin VanCleef" mlebu ing dek pungkasan (iku kertu kaping lima), lan kertu kasebut digambar luwih dhisik. "Millhouse" dadi kaloro ing dek, lan pemain kasebut narik nomer loro. "Sylvanas" tindak menyang kelompok katelu saka ndhuwur, lan iku kertu katelu sing pemain tarik. Sabanjure, pemain mbuwang kertu. Pisanan, dheweke mbuwang Edwin, banjur Millhouse, banjur Sylvanas. Banjur kita nampilake kertu ing tumpukan tumpukan siji-siji: Output konsol:

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

Sawise maneh, kita ndeleng carane tumpukan bisa digunakake! Ing game kita, tumpukan discard uga tumpukan (kaya deck draw). "Edwin VanCleef" dibuwang dhisik. Kapindho kertu discard ana Millhouse Manastorm, lan iki diselehake ing ndhuwur Edwin ing tumpukan discard. Banjur Sylvanas dibuwak, lan kertu iki diselehake ing ndhuwur Millhouse. Nalika sampeyan bisa ndeleng, ora ana sing rumit babagan tumpukan. Nanging, sampeyan kudu ngerti struktur data iki - asring ditakoni sajrone wawancara kerja, lan asring dadi basis kanggo mbangun struktur data sing luwih rumit.

Antri ing Jawa

Antrian minangka struktur data umum liyane. Saliyane tumpukan, akeh basa pamrograman, kalebu Jawa, uga ngetrapake struktur data antrian. Apa bedane antarane antrian lan tumpukan? Antrian ora adhedhasar prinsip LIFO, nanging adhedhasar prinsip FIFO ("first in, first out"). Prinsip iki gampang dingerteni kanthi nimbang, contone, garis biasa, utawa antrian, ing urip nyata! Contone, baris ing toko. Yen baris ana limang wong, sing pisanan dilayani yaiku sing mlebu baris luwih dhisik . Yen wong liya (saliyane lima sing wis antri) pengin tuku barang lan mlebu baris, banjur dilayani pungkasan., yaiku, kaping enem. Nalika nggarap antrian, unsur anyar ditambahake ing buntut (mburi), lan yen sampeyan pengin entuk unsur, bakal dijupuk saka sirah (ngarep). Iki minangka prinsip utama sing kudu sampeyan eling babagan cara antrian. A operasi antrian banget intuisi, awit kita temokake antrian asring ing urip nyata. Wigati dicathet yen ing Jawa antrian ora diwakili dening kelas, nanging antarmuka: Antrian. Apa maneh, ana akeh implementasi antarmuka antrian iki ing Jawa. Yen kita ndeleng dokumentasi Oracle, kita bakal weruh manawa 4 antarmuka sing beda-beda, uga dhaptar kelas sing nggumunake, entuk antarmuka Antrian:

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

Apa dhaftar amba! Nanging, mesthi, sampeyan ora perlu apal kabeh kelas lan antarmuka iki sapunika — sirah bisa njeblug :) Kita mung bakal nimbang saperangan saka titik paling penting lan menarik. Pisanan, ayo padha nggatekake salah siji saka papat "subinterfaces" Antrian: Deque . Apa ndadekake iku istimewa? A Dequepunika antrian pindho rampung. Iku ngluwihi fungsi saka antrian biasa, ngijini sampeyan kanggo nambah unsur kanggo loro ends (ing sirah lan buntut) lan njupuk unsur saka loro ends saka antrian. Antrian kaping pindho digunakake akeh ing pangembangan piranti lunak. Priksa dhaptar kelas antrian sing diwenehake ing ndhuwur. Dhaptar kasebut cukup dawa, nanging ngemot apa wae sing akrab?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Iki kanca lawas kita LinkedList! Dadi, ngleksanakake antarmuka Antrian? Nanging kepiye carane bisa dadi antrian? Sawise kabeh, a LinkedListminangka dhaptar sing disambung! Bener, nanging ora mandheg dadi antrian :) Iki dhaptar kabeh antarmuka sing ditindakake:

All implemented interfaces:

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

Nalika sampeyan bisa ndeleng, LinkedListngleksanakake Dequeantarmuka (maneh, iki tegese antrian pindho rampung). Napa iki dibutuhake? Iki ngidini kita entuk unsur saka wiwitan lan pungkasan a LinkedList. Uga ngidini kita nambah unsur ing wiwitan lan pungkasan. Mangkene cara sing LinkedListentuk saka Dequeantarmuka:

• peekFirst()- ngasilake unsur pisanan (nanging ora mbusak saka antrian).
• peekLast()- ngasilake unsur pungkasan (nanging ora mbusak saka antrian).
• pollFirst()- ngasilake unsur pisanan saka antrian lan mbusak.
• pollLast()- ngasilake item pungkasan saka antrian lan mbusak.
• addFirst()- nambah item anyar ing ngarep antrian.
• addLast()- nambah item menyang mburi antrian.

Nalika sampeyan bisa ndeleng, LinkedListkanthi ngleksanakake fungsi saka antrian pindho rampung! Lan sampeyan butuh fungsi kasebut ing program sampeyan, sampeyan bakal ngerti ing ngendi sampeyan bisa nemokake :) Pelajaran dina iki bakal rampung. Pungkasan, aku bakal menehi sawetara tautan kanggo maca tambahan. Pisanan, priksa artikel iki babagan PriorityQueue . Iki minangka salah sawijining Queueimplementasine sing paling menarik lan migunani. Contone, umpamane ana 50 wong sing antri ing toko sampeyan, lan 7 saka wong-wong mau minangka pelanggan VIP. A PriorityQueue bakal ngidini sampeyan ngladeni dhisik! Barang sing migunani banget, ta? :) Kapindho, ora ana salahe yen maneh nyebutake buku Robert Lafore "Data Structures and Algorithm in Java". Maca buku iki, sampeyan ora mung bakal sinau akeh struktur data (kalebu tumpukan lan antrian), nanging sampeyan uga bakal nindakake akeh dhewe! Contone, yen Jawa ora duwe kelas Stack? Apa sing bakal sampeyan lakoni yen sampeyan butuh struktur data kasebut kanggo program sampeyan? Sampeyan kudu nulis dhewe, mesthi. Nalika maca buku Lafore , sampeyan bakal kerep nglakoni. Akibaté, pangerten sampeyan babagan struktur data bakal luwih jero tinimbang apa sing bakal sampeyan entuk saka sinau teori sing prasaja :) Kita mbungkus teori kanggo dina iki, nanging teori tanpa praktik ora ana apa-apa! Tugas ora bakal ngrampungake dhewe, dadi wektune kanggo ngatasi! :)