Struktur data: tindanan dan baris gilir

Hai! Hari ini kita akan bercakap tentang sesuatu yang sangat penting untuk mana-mana pengaturcara: struktur data. Wikipedia berkata: " Struktur data ialah organisasi data, pengurusan dan format storan yang membolehkan capaian dan pengubahsuaian yang cekap. Lebih tepat lagi, struktur data ialah himpunan nilai data, perhubungan antara mereka dan fungsi atau operasi yang boleh digunakan pada data." Takrifannya agak mengelirukan, tetapi intipatinya jelas. Struktur data ialah sejenis repositori tempat kami menyimpan data untuk kegunaan masa hadapan. Dalam pengaturcaraan, terdapat pelbagai jenis struktur data. Apabila menyelesaikan masalah tertentu, selalunya perkara yang paling penting ialah memilih struktur data yang paling sesuai untuk masalah tersebut. Dan anda sudah biasa dengan banyak daripada mereka! Sebagai contoh, anda tahu tentang tatasusunan. Dan anda juga biasa denganMap(struktur data ini juga boleh dirujuk sebagai "kamus" atau "tatasusunan bersekutu"). Adalah sangat penting untuk memahami bahawa struktur data tidak terikat dengan mana-mana bahasa tertentu. Ia hanyalah "cetak biru" abstrak yang digunakan oleh setiap bahasa pengaturcaraan untuk mencipta kelas sendiri atau pelaksanaan struktur tertentu. Sebagai contoh, salah satu struktur data yang paling terkenal ialah senarai terpaut. Anda boleh pergi ke Wikipedia dan membaca tentang cara ia berfungsi dan apakah kelebihan dan kekurangannya. Mungkin takrifnya kelihatan biasa kepada anda :) "Senarai terpaut ialah koleksi linear elemen data, yang susunannya tidak diberikan oleh peletakan fizikalnya dalam ingatan. Sebaliknya, setiap elemen menghala ke seterusnya." Itu menggambarkan kekasih kita LinkedList, bukan? Ya, dan itulah sebenarnya :) Di Jawa, struktur data "senarai terpaut" dilaksanakan oleh kelas LinkedList. Tetapi bahasa lain juga melaksanakan senarai terpaut! Dalam Python, struktur data ini dipanggil " llist". Dalam Scala ia dipanggil " LinkedList", sama seperti di Jawa. Senarai terpaut ialah salah satu daripada struktur data biasa asas, jadi anda akan mendapati bahawa ia dilaksanakan dalam mana-mana bahasa pengaturcaraan moden. Perkara yang sama berlaku untuk tatasusunan bersekutu. Berikut ialah definisi dari Wikipedia: "Susun tatasusunan bersekutu, peta, jadual simbol atau kamus ialah jenis data abstrak yang terdiri daripada koleksi pasangan (kunci, nilai), supaya setiap kunci yang mungkin muncul paling banyak sekali dalam koleksi." Adakah itu mengingatkan anda tentang apa-apa? :) Ya. Bagi kami pembangun Java, tatasusunan bersekutu ialahMapantara muka. Tetapi struktur data ini juga dilaksanakan dalam bahasa lain! Sebagai contoh, pengaturcara C# mengetahuinya di bawah nama "Kamus". Dan dalam Ruby, ia dilaksanakan dalam kelas yang dipanggil "Hash". Nah, anda faham maksudnya: struktur data ialah konsep universal dalam pengaturcaraan, dan setiap bahasa pengaturcaraan melaksanakannya dengan cara tersendiri. Hari ini kita akan mengkaji dua struktur sedemikian - tindanan dan baris gilir - dan melihat bagaimana ia dilaksanakan di Jawa.

Timbunan di Jawa

Tindanan ialah struktur data yang terkenal. Ia sangat mudah. Beberapa perkara dalam kehidupan seharian kita "dilaksanakan" sebagai timbunan. Bayangkan situasi mudah ini: anda menginap di sebuah hotel, dan sepanjang hari anda menerima beberapa surat perniagaan. Anda tiada di dalam bilik pada masa itu, jadi kerani hotel hanya meletakkan surat masuk di atas meja anda. Pertama, dia meletakkan huruf pertama di atas meja. Kemudian surat kedua tiba, dan dia meletakkannya di atas yang pertama. Dia meletakkan huruf ketiga di atas yang kedua, dan yang keempat di atas yang ketiga. Dan sekarang, jawab soalan mudah: apakah surat yang akan anda baca dahulu apabila anda kembali ke bilik anda dan melihat timbunan di atas meja? Betul, anda akan membaca yang paling atassurat. Iaitu, yang paling baru tiba . Beginilah cara tindanan berfungsi. Prinsip ini dipanggil "keluar dahulu yang terakhir" (LIFO) . Apakah tindanan yang baik untuk? Baiklah, katakan anda sedang mencipta sejenis permainan kad di Jawa. Dek kad terletak di atas meja. Kad yang dimainkan dibuang. Anda boleh menggunakan dua tindanan untuk melaksanakan kedua-dua dek seri dan longgokan buang. Pemain mengambil kad mereka dari bahagian atas dek, mengikut prinsip yang sama seperti dengan surat perniagaan anda. Apabila pemain meletakkan kad ke dalam longgokan buang, kad yang baru dibuang diletakkan di atas yang lama. Inilah percubaan pertama kami pada permainan, dilaksanakan berdasarkan timbunan:

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

Seperti yang kami katakan sebelum ini, kami mempunyai dua timbunan: dek seri dan longgokan buang. Di Java, struktur data tindanan dilaksanakan dalam java.util.Stackkelas. Permainan kad kami mempunyai 3 kaedah yang menerangkan tindakan pemain:

• ambil kad dari dek ( getCardFromDeck()kaedah)
• buang kad ( discard()kaedah)
• lihat pada kad atas ( lookAtTopCard()kaedah). Katakan ini ialah bonus "Kecerdasan" yang membolehkan pemain mengetahui kad yang akan datang seterusnya dalam permainan.

Di dalam kaedah kami, kami memanggil kaedah kelas Stack berikut:

• push()— menambah item pada bahagian atas timbunan. Apabila kami menghantar kad ke longgokan buang, ia pergi ke bahagian atas longgokan
• pop()— mengalih keluar elemen teratas daripada timbunan dan mengembalikannya. Kaedah ini sesuai untuk melaksanakan tindakan di mana pemain menarik kad.
• peek()— mengembalikan elemen atas timbunan, tetapi tidak mengeluarkannya daripada timbunan

Mari lihat bagaimana permainan kami akan berfungsi:

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

Kami menambah lima kad pada dek kami. Pemain pertama mengambil 3 daripadanya. Kad mana yang dia dapat? Output konsol:

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

Beri perhatian kepada susunan kad dipaparkan pada konsol. Kad "Edwin VanCleef" masuk ke geladak terakhir (ia adalah kad kelima), dan ia adalah kad yang pemain lukis dahulu. "Millhouse" berada di tempat kedua selepas yang terakhir di geladak, dan pemain itu mendapat tempat kedua. "Sylvanas" masuk ke geladak ketiga dari atas, dan ia adalah kad ketiga yang dilukis oleh pemain itu. Seterusnya, pemain membuang kad. Pertama, dia membuang Edwin, kemudian Millhouse, kemudian Sylvanas. Kemudian kami memaparkan kad dalam longgokan buang kami satu demi satu: Output konsol:

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

Sekali lagi, kita melihat bagaimana tindanan berfungsi! Dalam permainan kami, longgokan buang juga adalah timbunan (sama seperti dek seri). "Edwin VanCleef" dibuang dahulu. Pembuangan kad kedua ialah Millhouse Manastorm, dan ia diletakkan di atas Edwin dalam longgokan buangan. Kemudian Sylvanas dibuang, dan kad ini diletakkan di atas Millhouse. Seperti yang anda lihat, tidak ada yang rumit tentang timbunan. Namun, anda perlu mengetahui struktur data ini — ia sering ditanya semasa temu duga kerja, dan ia sering menjadi asas untuk membina struktur data yang lebih kompleks.

Beratur di Jawa

Baris gilir ialah satu lagi struktur data biasa. Selain timbunan, banyak bahasa pengaturcaraan, termasuk Java, juga melaksanakan struktur data baris gilir. Apakah perbezaan antara baris gilir dan timbunan? Barisan gilir bukan berdasarkan prinsip LIFO, tetapi lebih kepada prinsip FIFO ("masuk dahulu, keluar dahulu"). Prinsip ini mudah difahami dengan mempertimbangkan, sebagai contoh, garis biasa, atau baris gilir, dalam kehidupan sebenar! Contohnya, barisan di kedai runcit. Jika terdapat lima orang dalam barisan, yang pertama dihidangkan ialah orang yang memasuki barisan terlebih dahulu . Jika orang lain (selain lima yang sudah beratur) ingin membeli sesuatu dan masuk barisan, maka dia akan dilayan terakhir, iaitu keenam. Apabila bekerja dengan baris gilir, elemen baru ditambahkan pada ekor (belakang), dan jika anda ingin mendapatkan elemen, ia akan diambil dari kepala (depan). Ini adalah prinsip utama yang perlu anda ingat tentang cara baris gilir berfungsi. Operasi baris gilir adalah sangat intuitif, kerana kami sering menemui baris gilir dalam kehidupan sebenar. Perlu diperhatikan secara berasingan bahawa dalam Java baris gilir diwakili bukan oleh kelas, tetapi oleh antara muka: Queue. Lebih-lebih lagi, terdapat banyak pelaksanaan antara muka baris gilir ini di Jawa. Jika kita melihat dokumentasi Oracle, kita akan melihat bahawa 4 antara muka yang berbeza, serta senarai kelas yang sangat mengagumkan, mewarisi antara muka 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

Senarai yang besar! Tetapi, sudah tentu, anda tidak perlu menghafal semua kelas dan antara muka ini sekarang — kepala anda mungkin meletup :) Kami hanya akan mempertimbangkan beberapa perkara yang paling penting dan menarik. Mula-mula, mari kita perhatikan salah satu daripada empat "subantara muka" Queue: Deque . Apa yang membuatkan ia begitu istimewa? A Dequeialah baris gilir dua hujung. Ia memanjangkan fungsi baris gilir biasa, membolehkan anda menambah elemen pada kedua-dua hujung (di kepala dan ekor) dan mengambil elemen dari kedua-dua hujung baris gilir. Gilir dua hujung digunakan secara meluas dalam pembangunan perisian. Perhatikan senarai kelas giliran yang kami sediakan di atas. Senarainya agak panjang, tetapi adakah ia mengandungi sesuatu yang biasa?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Ini kawan lama kita LinkedList! Jadi, ia melaksanakan antara muka Baris Gilir? Tetapi bagaimana ia boleh beratur? Lagipun, a LinkedListialah senarai terpaut! Benar, tetapi itu tidak menghalangnya daripada menjadi baris gilir :) Berikut ialah senarai semua antara muka yang ia laksanakan:

All implemented interfaces:

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

Seperti yang anda lihat, LinkedListmelaksanakan Dequeantara muka (sekali lagi, ini bermakna baris gilir dua hujung). Mengapa ini diperlukan? Ini membolehkan kita mendapatkan elemen dari awal dan akhir LinkedList. Ia juga membolehkan kami menambah elemen pada permulaan dan akhir. Berikut ialah kaedah yang LinkedListdiperoleh daripada Dequeantara muka:

• peekFirst()— mengembalikan elemen pertama (tetapi tidak mengeluarkannya daripada baris gilir).
• peekLast()— mengembalikan elemen terakhir (tetapi tidak mengeluarkannya daripada baris gilir).
• pollFirst()— mengembalikan elemen pertama daripada baris gilir dan mengeluarkannya.
• pollLast()— mengembalikan item terakhir dari baris gilir dan mengeluarkannya.
• addFirst()— menambah item baharu di hadapan baris gilir.
• addLast()— menambah item pada penghujung baris gilir.

Seperti yang anda lihat, LinkedListmelaksanakan sepenuhnya fungsi baris gilir dua hujung! Dan anda memerlukan fungsi sedemikian dalam program anda, anda akan tahu di mana untuk mencarinya :) Pelajaran hari ini akan berakhir. Kesimpulannya, saya akan memberikan anda beberapa pautan untuk bacaan tambahan. Mula-mula, perhatikan artikel tentang PriorityQueue ini . Ini adalah salah satu Queuepelaksanaan yang paling menarik dan berguna. Sebagai contoh, katakan terdapat 50 orang menunggu dalam barisan di kedai anda, dan 7 daripada mereka adalah pelanggan VIP. PriorityQueue akan membenarkan anda melayan mereka terlebih dahulu! Perkara yang sangat berguna, bukan? :) Kedua, tidak salah untuk sekali lagi menyebut buku Robert Lafore "Struktur Data dan Algoritma di Jawa". Membaca buku ini, anda bukan sahaja akan mempelajari banyak struktur data (termasuk tindanan dan baris gilir), tetapi anda juga akan melaksanakan banyak daripadanya sendiri! Sebagai contoh, bagaimana jika Java tidak mempunyai kelas Stack? Apakah yang akan anda lakukan jika anda memerlukan struktur data sedemikian untuk program anda? Anda perlu menulisnya sendiri, sudah tentu. Semasa anda membaca buku Lafore , anda akan sering melakukan perkara itu. Akibatnya, pemahaman anda tentang struktur data akan menjadi lebih mendalam daripada apa yang anda akan perolehi daripada kajian mudah teori :) Kami sedang menggulung teori untuk hari ini, tetapi teori tanpa amalan bukanlah apa-apa! Tugasan tidak akan menyelesaikan sendiri, jadi sudah tiba masanya untuk menanganinya! :)