Struktur Data ing Jawa - Tumpukan lan Antrian

Hello! Dina iki kita bakal ngomong babagan perkara sing penting kanggo programer apa wae minangka struktur data . Wikipedia ngandika: Struktur data ( eng. struktur data ) iku sawijining unit piranti lunak sing ngijini sampeyan kanggo nyimpen lan proses akèh jinis padha lan / utawa data logis related ing komputerisasi. Definisi rada mbingungake, nanging intine jelas. Struktur data minangka jinis panyimpenan ing ngendi kita nyimpen data kanggo panggunaan luwih lanjut. Ana macem-macem struktur data ing pemrograman. Asring banget, nalika ngrampungake masalah tartamtu, sing paling penting yaiku milih struktur data sing paling cocok kanggo tujuan iki. Lan sampeyan wis kenal karo akeh wong! Contone, karo arrays . Lan uga karo Map(sing biasane diterjemahake minangka "kamus", "peta", utawa "array asosiatif"). Penting banget kanggo mangerteni: struktur data ora disambungake karo basa tartamtu . Iki mung abstrak "cetak biru" miturut saben basa pamrograman nggawe kelas dhewe - implementasi struktur iki. Contone, salah sawijining struktur data sing paling misuwur yaiku dhaptar sing disambung . Sampeyan bisa pindhah menyang Wikipedia, maca babagan cara kerjane, apa kaluwihan lan kekurangane. Sampeyan bisa nemokake definisi kasebut akrab :) "Dhaptar sing disambung minangka struktur data dinamis dhasar ing ilmu komputer, sing dumadi saka simpul, sing saben-saben ngemot data dhewe lan siji utawa loro pranala ("pranala") menyang sabanjure lan / utawa dhaptar simpul sadurunge" Dadi iki duweke LinkedList! Persis kaya ngono :) Struktur data linked list diimplementasikake nganggo basa Jawa ing kelas LinkedList. Nanging basa liyane uga ngetrapake dhaptar sing disambung! Ing Python diarani " llist", ing Scala diarani padha karo ing Jawa - " LinkedList". Dhaptar sing disambung minangka salah sawijining struktur data umum dhasar, supaya sampeyan bisa nemokake implementasine ing basa pemrograman modern. Bab sing padha karo array asosiatif. Mangkene definisi saka Wikipedia: Array asosiatif yaiku jinis data abstrak (antarmuka menyang toko data) sing ngidini nyimpen pasangan saka formulir "(kunci, nilai)" lan ndhukung operasi nambah pasangan, uga nggoleki. lan mbusak pasangan kanthi tombol. Apa ora ngelingake sampeyan apa-apa? :) Persis, kanggo kita wong Jawa, array asosiatif minangka antarmukaMap. Nanging struktur data iki uga ditrapake ing basa liya! Contone, programer C # ngerti kanthi jeneng "Kamus". Lan ing basa Ruby dileksanakake ing kelas sing diarani "Hash". Umumé, sampeyan kira-kira ngerti apa tegese: struktur data minangka bab sing umum kanggo kabeh program, sing diimplementasikake kanthi beda ing saben basa tartamtu. Dina iki kita bakal sinau loro struktur kuwi lan ndeleng carane padha dileksanakake ing Jawa - tumpukan lan antrian.

Tumpukan ing Jawa

Tumpukan minangka struktur data sing dikenal. Gampang banget lan cukup akeh obyek saka urip saben dina sing "dilaksanakake" minangka tumpukan. Mbayangno kahanan sing prasaja: sampeyan manggon ing hotel, lan ing wayah awan sampeyan nampa surat bisnis. Amarga sampeyan ora ana ing kamar nalika iku, karyawan hotel mung nyelehake surat sing mlebu ing meja sampeyan. Pisanan dheweke nyelehake huruf pisanan ing meja. Banjur sing nomer loro teka lan dipasang ing ndhuwur sing pertama. Dhèwèké nglebokaké layang katelu sing ana ing ndhuwur sing nomer loro, lan sing nomer papat ing ndhuwur sing nomer telu. Saiki, wangsulana pitakonan sing prasaja: huruf apa sing bakal diwaca dhisik nalika teka ing kamar lan ndeleng tumpukan ing meja? Bener, sampeyan bakal maca huruf ndhuwur . Yaiku, sing teka pungkasan ing wektu . Iki persis carane tumpukan bisa. Prinsip operasi iki diarani LIFO - "last in - first out" ("last in, first out"). Apa tumpukan bisa migunani? Contone, sampeyan nggawe sawetara jinis game kertu ing Jawa. A kelompok kertu dumunung ing meja. Kertu sing diputer dibuwak. Sampeyan bisa ngleksanakake loro dek lan discard nggunakake rong tumpukan. Pemain nggambar kertu saka ndhuwur dek - prinsip sing padha karo huruf. Nalika pemain mbuwang kertu, kertu anyar diselehake ing ndhuwur sing lawas. Mangkene apa draf pisanan game kita, sing diimplementasikake nggunakake 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 {

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

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

Kaya sing wis dingerteni sadurunge, kita duwe rong tumpukan: dek lan mbuwang. Struktur data tumpukan dileksanakake ing Jawa ing java.util.Stack. Ing game kertu kita ana 3 cara sing nggambarake tumindak para pemain:

• njupuk kertu saka dek (cara getCardFromDeck());
• kertu discard (cara discard());
• katon ing kertu ndhuwur (cara lookTopCard()). Ayo dadi ngomong iki bakal bonus mekanik "Intelligence", kang bakal ngidini pamuter kanggo mangerteni kang kertu bakal teka menyang muter sabanjuré.

Ing metode kita, metode kelas diarani Stack:

• push()- nambah unsur ing ndhuwur tumpukan. Nalika kita discard kertu, dadi ing ndhuwur kertu sadurunge dibuwak;
• pop()- mbusak unsur ndhuwur saka tumpukan lan bali. Cara iki becik kanggo ngleksanakake mekanik "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) {

       //  создаем колоду и добавляем в нее карты
       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());
   }
}

Dadi, kita wis nambahake limang kertu menyang dek. Pamuter pisanan njupuk 3 wong. Kertu apa dheweke entuk? Output konsol:

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

Pay manungsa waé menyang urutan kang kertu padha output kanggo console. Kertu "Edwin Van Cleiff" minangka sing pungkasan sing kena ing dek (kalima ing saurutan), lan kertu kasebut sing dijupuk pemain pisanan. "Michhlaus" minangka sing nomer loro ing dek, lan pemain kasebut njupuk nomer loro. "Sylvanas" tekan dek katelu saka mburi, lan pindhah menyang pemain katelu. Sabanjure, pemain mbuwang kertu. Pisanan dheweke nyelehake Edwin, banjur Millhouse, banjur Sylvanas. Sawisé iku, siji-siji metu menyang konsol kertu sing dibuwang: Output menyang konsol:

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

Lan maneh kita waca carane tumpukan dianggo! Buang ing game kita uga tumpukan (kaya deck). "Edwin Van Clyffe" minangka sing pisanan diluncurake. Kapindho bakal dropped ana "Millhouse Manastorm" - lan lay ing ndhuwur Edwin ing discard. Sabanjure, Sylvanas dibuwang - lan kertu iki ana ing ndhuwur Millhouse. Nalika sampeyan bisa ndeleng, ana apa-apa rumit bab carane tumpukan bisa. Nanging, perlu ngerti struktur data iki - asring ditakoni babagan wawancara, lan struktur data sing luwih rumit asring dibangun kanthi basis.

antri

Antrian (utawa, ing basa Inggris, "Queue") minangka struktur data umum liyane. Kaya tumpukan, diimplementasikake ing pirang-pirang basa pamrograman, kalebu Jawa. Apa bedane antarane antrian lan tumpukan? Antrian kasebut ora adhedhasar LIFO, nanging ing prinsip liyane - FIFO ("first in - first out", "first in - first out") . Iku gampang kanggo mangerteni, njupuk minangka conto ... utawa ing paling biasa, antrian nyata saka urip nyata! Contone, antrian menyang toko. Yen antrian ana lima, wong sing antri sepisanan bakal mlebu toko . Yen ana wong siji liyane (liyane lima baris) pengin tuku barang lan mlebu baris, banjur mlebu ing toko pungkasan , yaiku nomer enem. Nalika nggarap antrian, unsur anyar ditambahake ing pungkasan, lan yen sampeyan pengin entuk unsur, bakal dijupuk saka wiwitan. Iki minangka prinsip dhasar operasi, sing kudu dieling-eling. Prinsip antrian gampang banget dingerteni kanthi intuisi, amarga asring ditemokake ing urip nyata. Wigati dicathet yen ing Jawa antrian ora diwakili dening kelas, nanging antarmuka - Queue. Nanging ing wektu sing padha, antrian ing Jawa minangka antarmuka sing akeh implementasine. Yen kita ndeleng dokumentasi Oracle, kita bakal weruh manawa 4 antarmuka sing beda-beda lan dhaptar kelas sing apik banget diwarisake saka 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, mesthine, sampeyan ora perlu ngeling-eling kabeh kelas lan antarmuka iki saiki - sirah sampeyan bisa njeblug :) Kita bakal ndeleng mung sawetara poin sing paling penting lan menarik. Pisanan, ayo menehi perhatian marang salah siji saka papat "sub-antarmuka" antrian - Deque. Apa istimewane? Deque- Iki antrian loro-lorone. Iku ngluwihi fungsi saka antrian biasa dening ngijini sampeyan kanggo nambah unsur kanggo loro ends (wiwit lan pungkasan antrian) lan njupuk unsur saka loro ends saka antrian. Deque digunakake akeh ing pembangunan. Priksa dhaptar kelas antrian sing diwenehake ing ndhuwur. Dhaptar iki cukup dawa, nanging ana apa-apa sing akrab karo kita?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, dadi kanca lawas kita ing kene LinkedList! Sing, iku ngleksanakake antarmuka Queue? Nanging kepiye dheweke bisa dadi antrian? Sawise kabeh LinkedList, iki dhaptar sing disambungake! Bener, nanging ora mandheg dadi antrian :) Ing ngisor 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, LinkedListiku ngleksanakake antarmuka Deque- antrian loro-cara. Yagene iki perlu? Thanks kanggo iki, kita bisa entuk unsur saka awal lan pungkasan LinkedList. Lan uga - nambah unsur ing wiwitan lan pungkasan. Mangkene metode sing diwarisake LinkedListsaka antarmuka Deque:

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

Nalika sampeyan bisa ndeleng, LinkedListiku kebak ngleksanakake fungsi saka antrian loro-cara! Lan yen fungsi kasebut dibutuhake ing program kasebut, sampeyan bakal ngerti manawa bisa digunakake :) Lan kuliah kita saiki wis rampung. Pungkasan, aku bakal menehi sawetara tautan kanggo maca luwih lanjut. Pisanan, mbayar manungsa waé menyang artikel darmabakti kanggo PriorityQueue - "antri prioritas". Iki minangka salah sawijining implementasi Queue sing paling menarik lan migunani. Contone, yen ana 50 wong ing baris ing toko, lan 7 saka wong-wong mau minangka klien VIP, PriorityQueueiku bakal ngidini sampeyan kanggo ngawula pisanan! Bab sing migunani banget, apa sampeyan ora setuju? :) Kapindho, ora perlu maneh nyebutake buku Robert Laforet "Struktur Data lan Algoritma ing Jawa" . Nalika maca buku, sampeyan ora mung bakal sinau akeh struktur data (kalebu tumpukan lan antrian), nanging sampeyan uga bakal ngleksanakake akeh mau dhewe! Contone, mbayangno yen Jawa ora duwe kelas Stack. Apa sing bakal sampeyan lakoni yen sampeyan butuh struktur data kasebut kanggo program sampeyan? Mesthi, aku kudu nulis dhewe. Nalika maca buku Laforet, iki asring sampeyan bakal nindakake. Thanks kanggo iki, pangerten sampeyan babagan struktur data bakal luwih jembar tinimbang nalika mung sinau teori :) Kita wis rampung karo teori kanggo dina iki, nanging teori tanpa praktik ora ana apa-apa! Masalah ora bakal ngrampungake dhewe, mula saiki iki wektu kanggo ngatasi! :)