Struktur Data dalam Java - Tindanan dan Baris Gilir

hello! Hari ini kita akan bercakap tentang perkara penting untuk mana-mana pengaturcara sebagai struktur data . Wikipedia berkata: Struktur data ( eng. struktur data ) ialah unit perisian yang membolehkan anda menyimpan dan memproses banyak jenis yang sama dan/atau data yang berkaitan secara logik dalam pengkomputeran. Definisinya sedikit mengelirukan, tetapi intipatinya jelas. Struktur data ialah sejenis storan tempat kami menyimpan data untuk kegunaan selanjutnya. Terdapat pelbagai jenis struktur data dalam pengaturcaraan. Selalunya, apabila menyelesaikan masalah tertentu, perkara yang paling penting ialah memilih struktur data yang paling sesuai untuk tujuan ini. Dan anda sudah biasa dengan banyak daripada mereka! Sebagai contoh, dengan tatasusunan . Dan juga dengan Map(yang biasanya diterjemahkan sebagai "kamus", "peta", atau "tatasusunan bersekutu"). Ia amat penting untuk difahami: struktur data tidak terikat dengan mana-mana bahasa tertentu . Ini hanyalah "cetak biru" abstrak yang mengikutnya setiap bahasa pengaturcaraan mencipta kelasnya sendiri - pelaksanaan struktur ini. Sebagai contoh, salah satu struktur data yang paling terkenal ialah senarai terpaut . Anda boleh pergi ke Wikipedia, membaca tentang cara ia berfungsi, apakah kelebihan dan kekurangannya. Anda mungkin mendapati takrifnya biasa :) "Senarai terpaut ialah struktur data dinamik asas dalam sains komputer, yang terdiri daripada nod, setiap satunya mengandungi kedua-dua data itu sendiri dan satu atau dua pautan ("pautan") ke seterusnya dan/atau senarai nod sebelumnya” Jadi ini milik kita LinkedList! Betul, begitulah keadaannya :) Struktur data senarai terpaut dilaksanakan dalam bahasa Java dalam kelas LinkedList. Tetapi bahasa lain juga melaksanakan senarai terpaut! Dalam Python ia dipanggil " llist", dalam Scala ia dipanggil sama seperti dalam Java - " LinkedList". Senarai terpaut ialah salah satu struktur data biasa asas, jadi anda boleh mencari pelaksanaannya dalam mana-mana bahasa pengaturcaraan moden. Perkara yang sama dengan tatasusunan bersekutu. Berikut ialah definisinya daripada Wikipedia: Tatasusunan bersekutu ialah jenis data abstrak (antara muka kepada stor data) yang membenarkan menyimpan pasangan bentuk "(kunci, nilai)" dan menyokong operasi menambah pasangan, serta mencari dan memadamkan pasangan dengan kunci. Tidak mengingatkan anda tentang apa-apa? :) Tepat sekali, bagi kami Javais, tatasusunan bersekutu ialah antara mukaMap. Tetapi struktur data ini dilaksanakan dalam bahasa lain juga! Sebagai contoh, pengaturcara C# mengetahuinya di bawah nama "Kamus". Dan dalam bahasa Ruby ia dilaksanakan dalam kelas yang dipanggil "Hash". Secara umum, anda secara kasarnya memahami maksudnya: struktur data adalah perkara biasa kepada semua pengaturcaraan, yang dilaksanakan secara berbeza dalam setiap bahasa tertentu. Hari ini kita akan mengkaji dua struktur sedemikian dan melihat bagaimana ia dilaksanakan dalam Java - tindanan dan giliran.

Timbunan di Jawa

Tindanan ialah struktur data yang diketahui. Ia sangat mudah dan agak banyak objek dari kehidupan seharian kita "dilaksanakan" sebagai timbunan. Bayangkan situasi mudah: anda tinggal di sebuah hotel, dan pada siang hari anda menerima surat perniagaan. Memandangkan anda tiada di dalam bilik ketika itu, pekerja hotel itu hanya meletakkan surat masuk di atas meja anda. Mula-mula dia meletakkan huruf pertama di atas meja. Kemudian yang kedua datang dan dia meletakkannya di atas yang pertama. Dia meletakkan huruf ketiga yang tiba di atas yang kedua, dan yang keempat di atas yang ketiga. Sekarang, jawab soalan mudah: surat apakah yang akan anda baca dahulu apabila anda datang ke bilik anda dan melihat timbunan di atas meja? Betul, anda akan membaca huruf atas . Iaitu, yang datang terakhir pada masanya . Beginilah cara tindanan berfungsi. Prinsip operasi ini dipanggil LIFO - “masuk terakhir - keluar dahulu” (“masuk terakhir, keluar dahulu”). Untuk apa timbunan boleh berguna? Contohnya, anda sedang mencipta sejenis permainan kad dalam Java. Dek kad terletak di atas meja. Kad yang dimainkan dibuang. Anda boleh melaksanakan kedua-dua dek dan buangan menggunakan dua tindanan. Pemain menarik kad dari bahagian atas dek - prinsip yang sama seperti dengan huruf. Apabila pemain membuang kad, kad baharu diletakkan di atas kad lama. Begini rupa draf pertama permainan kami, dilaksanakan menggunakan tindanan:

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

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

Seperti yang kami katakan sebelum ini, kami mempunyai dua timbunan: dek dan buang. Struktur data tindanan dilaksanakan dalam Java dalam java.util.Stack. Dalam permainan kad kami terdapat 3 kaedah yang menggambarkan tindakan pemain:

• ambil kad dari dek (kaedah getCardFromDeck());
• buang kad (kaedah discard());
• lihat pada kad atas (kaedah lookTopCard()). Katakan ini akan menjadi mekanik bonus "Kecerdasan", yang akan membolehkan pemain mengetahui kad yang akan dimainkan seterusnya.

Di dalam kaedah kami, kaedah kelas dipanggil Stack:

• push()— menambah elemen pada bahagian atas timbunan. Apabila kita membuang kad, ia akan berada di atas kad yang dibuang sebelum ini;
• pop()— mengalih keluar elemen teratas daripada timbunan dan mengembalikannya. Kaedah ini sesuai untuk melaksanakan mekanik "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) {

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

Jadi kami telah menambah lima kad pada dek kami. Pemain pertama mengambil 3 daripadanya. Apakah kad yang dia dapat? Output konsol:

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

Beri perhatian kepada susunan kad dikeluarkan ke konsol. Kad "Edwin Van Cleiff" adalah yang terakhir terkena dek (kelima berturut-turut), dan kad itu yang diambil oleh pemain terlebih dahulu. "Michhlaus" adalah yang kedua selepas yang terakhir di geladak, dan pemainnya menduduki tempat kedua. "Sylvanas" memukul dek ketiga dari akhir, dan pergi ke pemain ketiga. Seterusnya, pemain membuang kadnya. Mula-mula dia menjatuhkan Edwin, kemudian Millhouse, kemudian Sylvanas. Selepas itu kami satu demi satu mengeluarkan ke konsol kad yang ada dalam buang kami: Output ke konsol:

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

Dan sekali lagi kita melihat bagaimana timbunan berfungsi! Buangan dalam permainan kami juga adalah timbunan (sama seperti dek). "Edwin Van Clyffe" adalah yang pertama diturunkan. Yang kedua yang digugurkan ialah "Millhouse Manastorm" - dan berbaring di atas Edwin di tempat pembuangan. Seterusnya, Sylvanas telah dibuang - dan kad ini terletak di atas Millhouse. Seperti yang anda lihat, tidak ada yang rumit tentang cara timbunan berfungsi. Walau bagaimanapun, adalah perlu untuk mengetahui struktur data ini - ia sering ditanya dalam temu bual, dan struktur data yang lebih kompleks sering dibina berdasarkannya.

Beratur

Barisan gilir (atau, dalam bahasa Inggeris, "Barisan") ialah satu lagi struktur data biasa. Sama seperti timbunan, ia dilaksanakan dalam banyak bahasa pengaturcaraan, termasuk Java. Apakah perbezaan antara baris gilir dan timbunan? Barisan gilirnya tidak berdasarkan LIFO, tetapi pada prinsip lain - FIFO (“masuk dahulu - keluar dahulu”, “masuk dahulu - keluar dahulu”) . Ia mudah difahami, mengambil sebagai contoh... atau sekurang-kurangnya barisan biasa yang sebenar dari kehidupan sebenar! Contohnya, beratur ke kedai. Jika terdapat lima orang dalam barisan, orang pertama dalam barisan akan masuk ke dalam kedai . Jika seorang lagi (selain lima barisan) ingin membeli sesuatu dan masuk barisan, maka dia masuk ke kedai terakhir , iaitu tempat keenam. Apabila bekerja dengan baris gilir, elemen baharu ditambahkan pada penghujung, dan jika anda ingin mendapatkan elemen, ia akan diambil dari awal. Ini adalah prinsip asas operasinya, yang perlu anda ingat. Prinsip baris gilir sangat mudah difahami secara intuitif, kerana ia sering ditemui dalam kehidupan sebenar. Perlu diperhatikan secara berasingan bahawa dalam Java baris gilir tidak diwakili oleh kelas, tetapi oleh antara muka - Queue. Tetapi pada masa yang sama, baris gilir dalam Java adalah antara muka yang mempunyai banyak pelaksanaan. Jika kita melihat dokumentasi Oracle, kita akan melihat bahawa 4 antara muka yang berbeza dan senarai kelas yang sangat mengagumkan diwarisi daripada baris gilir:

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 akan melihat hanya beberapa perkara yang paling penting dan menarik. Mula-mula, mari kita perhatikan salah satu daripada empat "sub-antara muka" baris gilir - Deque. Apa yang istimewanya? Deque- Ini adalah baris gilir dua hala. Ia memanjangkan kefungsian baris gilir biasa dengan membenarkan anda menambah elemen pada kedua-dua hujung (permulaan dan penghujung baris gilir) dan mengambil elemen dari kedua-dua hujung baris gilir. Deque digunakan secara meluas dalam pembangunan. Perhatikan senarai kelas giliran yang kami sediakan di atas. Senarainya agak panjang, tetapi adakah sesuatu yang biasa kepada kita di sana?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, jadi kawan lama kita ada di sini LinkedList! Iaitu, ia melaksanakan antara muka Queue? Tetapi bagaimana dia boleh menjadi barisan? Lagipun LinkedList, ini adalah senarai yang disambungkan! Benar, tetapi itu tidak menghalangnya daripada menjadi baris gilir :) Berikut ialah senarai semua antara muka yang dilaksanakannya:

All Implemented Interfaces:

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

Seperti yang anda lihat, LinkedListia melaksanakan antara muka Deque- baris gilir dua hala. Mengapa ini perlu? Terima kasih kepada ini, kita boleh mendapatkan elemen dari awal dan akhir LinkedList. Dan juga - tambah elemen pada kedua-dua permulaan dan akhir. Berikut ialah kaedah yang diwarisi LinkedListdaripada antara muka Deque:

• peekFirst()— mengembalikan (tetapi tidak mengalih keluar dari baris gilir) elemen pertama.
• peekLast()— mengembalikan (tetapi tidak mengalih keluar dari baris gilir) elemen terakhir.
• pollFirst()- mengembalikan elemen pertama daripada baris gilir dan mengeluarkannya.
• pollLast()- mengembalikan elemen terakhir dari baris gilir dan mengeluarkannya.
• addFirst()— menambah elemen baharu pada permulaan baris gilir.
• addLast()— menambah elemen pada penghujung baris gilir.

Seperti yang anda lihat, LinkedListia melaksanakan sepenuhnya fungsi baris gilir dua hala! Dan jika fungsi sedemikian diperlukan dalam program ini, anda akan tahu bahawa ia boleh digunakan :) Dan kuliah kami hari ini akan berakhir. Akhir sekali, saya akan memberikan anda beberapa pautan untuk bacaan selanjutnya. Mula-mula, perhatikan artikel yang dikhaskan untuk PriorityQueue - "gilir keutamaan". Ini adalah salah satu pelaksanaan Queue yang paling menarik dan berguna. Contohnya, jika terdapat 50 orang beratur di kedai anda, dan 7 daripada mereka adalah pelanggan VIP, PriorityQueueia akan membolehkan anda melayan mereka terlebih dahulu! Perkara yang sangat berguna, tidakkah anda bersetuju? :) Kedua, ia tidak akan berlebihan untuk sekali lagi menyebut buku Robert Laforet "Struktur Data dan Algoritma di Jawa" . Semasa membaca buku, anda bukan sahaja akan mempelajari banyak struktur data (termasuk tindanan dan baris gilir), tetapi anda juga akan melaksanakan banyak daripadanya sendiri! Sebagai contoh, bayangkan jika Java tidak mempunyai kelas Stack. Apakah yang akan anda lakukan jika anda memerlukan struktur data sedemikian untuk program anda? Sudah tentu, saya perlu menulisnya sendiri. Apabila membaca buku Laforet, ini selalunya anda akan lakukan. Terima kasih kepada ini, pemahaman anda tentang struktur data akan menjadi lebih luas daripada sekadar mempelajari teori :) Kami telah selesai dengan teori untuk hari ini, tetapi teori tanpa amalan bukanlah apa-apa! Masalah tidak akan menyelesaikan sendiri, jadi sekarang adalah masa untuk mengatasinya! :)