Struktur Data di Java - Stack dan Queue

Halo! Hari ini kita akan membicarakan hal-hal penting bagi programmer mana pun seperti struktur data . Wikipedia mengatakan: Struktur data ( eng. struktur data ) adalah unit perangkat lunak yang memungkinkan Anda menyimpan dan memproses banyak data dengan tipe yang sama dan/atau terkait secara logis dalam komputasi. Definisinya agak membingungkan, namun esensinya jelas. Struktur data adalah semacam penyimpanan tempat kita menyimpan data untuk digunakan lebih lanjut. Ada berbagai macam struktur data dalam pemrograman. Seringkali, ketika memecahkan masalah tertentu, hal terpenting adalah memilih struktur data yang paling sesuai untuk tujuan ini. Dan Anda sudah familiar dengan banyak di antaranya! Misalnya saja dengan array . Dan juga dengan Map(yang biasanya diterjemahkan sebagai “kamus”, “peta”, atau “array asosiatif”). Sangat penting untuk dipahami: struktur data tidak terikat pada bahasa tertentu . Ini hanyalah “cetak biru” abstrak yang dengannya setiap bahasa pemrograman membuat kelasnya sendiri - implementasi dari struktur ini. Misalnya, salah satu struktur data yang paling terkenal adalah daftar tertaut . Anda bisa pergi ke Wikipedia, membaca tentang cara kerjanya, apa kelebihan dan kekurangannya. Anda mungkin familiar dengan definisinya :) “Daftar tertaut adalah struktur data dinamis dasar dalam ilmu komputer, yang terdiri dari node, yang masing-masing berisi data itu sendiri dan satu atau dua tautan (“tautan”) ke yang berikutnya dan/atau daftar simpul sebelumnya” Jadi ini milik kita LinkedList! Tepat sekali :) Struktur data daftar tertaut diimplementasikan dalam bahasa Java di kelas LinkedList. Namun bahasa lain juga menerapkan daftar tertaut! Di Python disebut “ llist”, di Scala disebut sama seperti di Java - “ LinkedList“. Daftar tertaut adalah salah satu struktur data dasar yang umum, sehingga Anda dapat menemukan implementasinya dalam bahasa pemrograman modern apa pun. Hal yang sama dengan array asosiatif. Berikut definisinya dari Wikipedia: Array asosiatif adalah tipe data abstrak (antarmuka ke penyimpanan data) yang memungkinkan penyimpanan pasangan dalam bentuk “(kunci, nilai)” dan mendukung operasi penambahan pasangan, serta pencarian. dan menghapus pasangan dengan kunci. Tidak mengingatkanmu pada apa pun? :) Tepatnya, bagi kami para Javaist, array asosiatif adalah sebuah antarmukaMap. Namun struktur data ini juga diterapkan dalam bahasa lain! Misalnya, pemrogram C# mengetahuinya dengan nama “Kamus”. Dan dalam bahasa Ruby diimplementasikan dalam kelas yang disebut “Hash”. Secara umum, Anda secara kasar memahami apa artinya: struktur data adalah hal yang umum untuk semua pemrograman, yang diimplementasikan secara berbeda di setiap bahasa tertentu. Hari ini kita akan mempelajari dua struktur tersebut dan melihat bagaimana penerapannya di Java - stack dan queue.

Tumpukan di Jawa

Tumpukan adalah struktur data yang dikenal. Ini sangat sederhana dan cukup banyak objek dari kehidupan kita sehari-hari yang “diimplementasikan” sebagai tumpukan. Bayangkan sebuah situasi sederhana: Anda tinggal di sebuah hotel, dan pada siang hari Anda menerima surat bisnis. Karena saat itu Anda tidak ada di kamar, petugas hotel cukup meletakkan surat masuk di meja Anda. Pertama dia meletakkan huruf pertama di atas meja. Kemudian datanglah yang kedua dan dia menaruhnya di atas yang pertama. Dia menempatkan huruf ketiga di atas huruf kedua, dan huruf keempat di atas huruf ketiga. Sekarang, jawablah pertanyaan sederhana: surat apa yang akan Anda baca pertama kali ketika Anda masuk ke kamar Anda dan melihat tumpukan di atas meja? Benar sekali, Anda akan membaca huruf paling atas . Artinya, yang datang terakhir pada waktunya . Ini adalah cara kerja tumpukan. Prinsip operasi ini disebut LIFO - “masuk terakhir - keluar pertama” (“masuk terakhir, keluar pertama”). Apa kegunaan tumpukan? Misalnya, Anda membuat semacam permainan kartu di Java. Setumpuk kartu terletak di atas meja. Kartu yang dimainkan dibuang. Anda dapat menerapkan dek dan kartu buangan menggunakan dua tumpukan. Pemain menggambar kartu dari atas tumpukan - prinsip yang sama seperti huruf. Saat pemain membuang kartu, kartu baru ditempatkan di atas kartu lama. Inilah tampilan draf pertama game kami, yang diimplementasikan menggunakan 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();
   }

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

Seperti yang kami katakan sebelumnya, kami memiliki dua tumpukan: dek dan kartu buangan. Struktur data tumpukan diimplementasikan di Java dalam format java.util.Stack. Dalam permainan kartu kami ada 3 metode yang menggambarkan tindakan para pemain:

• ambil kartu dari dek (metode getCardFromDeck());
• kartu buang (metode discard());
• lihat kartu paling atas (metode lookTopCard()). Katakanlah ini akan menjadi bonus mekanik "Intelijen", yang memungkinkan pemain mengetahui kartu mana yang akan dimainkan selanjutnya.

Di dalam metode kami, metode kelas disebut Stack:

• push()— menambahkan elemen ke bagian atas tumpukan. Saat kita membuang sebuah kartu, kartu tersebut berada di atas kartu yang sebelumnya dibuang;
• pop()— menghapus elemen teratas dari tumpukan dan mengembalikannya. Metode ini ideal untuk menerapkan mekanisme “pemain menarik kartu”.
• peek()- mengembalikan elemen teratas tumpukan, tetapi tidak menghapusnya dari tumpukan

Mari kita lihat cara kerja game kita:

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 menambahkan lima kartu ke dek kami. Pemain pertama mengambil 3 dari mereka. Kartu apa yang dia dapat? Keluaran konsol:

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

Perhatikan urutan keluaran kartu ke konsol. Kartu “Edwin Van Cleiff” adalah kartu terakhir yang mengenai dek (kelima berturut-turut), dan merupakan kartu yang diambil pemain terlebih dahulu. “Michhlaus” adalah yang kedua dari yang terakhir di dek, dan pemainnya menempati posisi kedua. “Sylvanas” mencapai dek ketiga dari akhir, dan pergi ke pemain ketiga. Selanjutnya, pemain membuang kartunya. Pertama dia menjatuhkan Edwin, lalu Millhouse, lalu Sylvanas. Setelah itu kita satu per satu output ke konsol kartu-kartu yang ada di buangan kita: Output ke konsol:

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

Dan sekali lagi kita melihat cara kerja tumpukan! Buangan dalam permainan kami juga berupa tumpukan (sama seperti dek). "Edwin Van Clyffe" adalah orang pertama yang dijatuhkan. Yang kedua dijatuhkan adalah “Millhouse Manastorm” - dan diletakkan di atas Edwin di tempat pembuangan. Selanjutnya, Sylvanas dibuang - dan kartu ini terletak di atas Millhouse. Seperti yang Anda lihat, tidak ada yang rumit dalam cara kerja tumpukan. Namun, struktur data ini perlu diketahui - struktur data ini sering ditanyakan dalam wawancara, dan struktur data yang lebih kompleks sering kali dibangun berdasarkan struktur tersebut.

Antre

Antrian (atau, dalam bahasa Inggris, “Antrian”) adalah struktur data umum lainnya. Sama seperti stack, ini diimplementasikan dalam banyak bahasa pemrograman, termasuk Java. Apa perbedaan antara antrian dan tumpukan? Antriannya tidak didasarkan pada LIFO, tetapi pada prinsip lain - FIFO (“masuk pertama - keluar pertama”, “masuk pertama - keluar pertama”) . Sangat mudah untuk memahaminya, dengan mengambil contoh... atau setidaknya antrian biasa dan nyata dari kehidupan nyata! Misalnya antrian ke toko. Jika ada lima orang yang mengantri, orang pertama yang mengantri akan masuk ke toko . Jika satu orang lagi (selain lima orang yang mengantri) ingin membeli sesuatu dan mengantri, maka dia masuk ke toko terakhir , yaitu yang keenam. Saat bekerja dengan antrian, elemen baru ditambahkan di akhir, dan jika Anda ingin mendapatkan elemen, elemen tersebut akan diambil dari awal. Inilah prinsip dasar pengoperasiannya yang perlu Anda ingat.Prinsip antrian sangat mudah dipahami secara intuitif, karena sering dijumpai dalam kehidupan nyata. Perlu dicatat secara terpisah bahwa di Java antrian tidak diwakili oleh kelas, tetapi oleh antarmuka - Queue. Namun pada saat yang sama, antrian di Java adalah antarmuka yang memiliki banyak implementasi. Jika kita melihat dokumentasi Oracle, kita akan melihat bahwa 4 antarmuka berbeda dan daftar kelas yang sangat mengesankan diwarisi dari 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

Daftar yang sangat besar! Namun, tentu saja, Anda tidak perlu menghafal semua kelas dan antarmuka ini sekarang - kepala Anda mungkin akan meledak :) Kami hanya akan melihat beberapa poin yang paling penting dan menarik. Pertama, mari kita perhatikan salah satu dari empat "sub-antarmuka" antrian - Deque. Apa istimewanya itu? Deque- Ini adalah antrian dua arah. Ini memperluas fungsionalitas antrian reguler dengan memungkinkan Anda menambahkan elemen ke kedua ujung (awal dan akhir antrian) dan mengambil elemen dari kedua ujung antrian. Deque banyak digunakan dalam pengembangan. Perhatikan daftar kelas antrian yang kami sediakan diatas. Daftarnya cukup panjang, tapi adakah yang familiar bagi kita di sana?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha, jadi teman lama kita ada di sini LinkedList! Artinya, ia mengimplementasikan antarmuka Queue? Tapi bagaimana dia bisa mengantri? Bagaimanapun LinkedList, ini adalah daftar yang terhubung! Benar, tapi itu tidak menghentikannya dari antrian :) Berikut daftar semua antarmuka yang diimplementasikannya:

All Implemented Interfaces:

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

Seperti yang Anda lihat, LinkedListini mengimplementasikan antarmuka Deque- antrian dua arah. Mengapa hal ini perlu? Berkat ini, kita bisa mendapatkan elemen dari awal dan akhir LinkedList. Dan juga - tambahkan elemen di awal dan akhir. Berikut adalah metode yang diwarisi LinkedListdari antarmuka Deque:

• peekFirst()— mengembalikan (tetapi tidak menghapus dari antrian) elemen pertama.
• peekLast()— mengembalikan (tetapi tidak menghapus dari antrian) elemen terakhir.
• pollFirst()- mengembalikan elemen pertama dari antrian dan menghapusnya.
• pollLast()- mengembalikan elemen terakhir dari antrian dan menghapusnya.
• addFirst()— menambahkan elemen baru ke awal antrian.
• addLast()— menambahkan elemen ke akhir antrian.

Seperti yang Anda lihat, LinkedListini sepenuhnya mengimplementasikan fungsi antrian dua arah! Dan jika fungsi seperti itu diperlukan dalam program, Anda akan tahu bahwa itu dapat digunakan :) Dan kuliah kita hari ini akan segera berakhir. Terakhir, saya akan memberi Anda beberapa tautan untuk bacaan lebih lanjut. Pertama, perhatikan artikel yang didedikasikan untuk PriorityQueue - “antrian prioritas”. Ini adalah salah satu implementasi Queue yang paling menarik dan berguna. Misalnya, jika ada 50 orang yang mengantri di toko Anda, dan 7 di antaranya adalah klien VIP, PriorityQueueAnda dapat melayani mereka terlebih dahulu! Suatu hal yang sangat berguna, setujukah Anda? :) Kedua, tidak berlebihan jika sekali lagi menyebutkan buku Robert Laforet “Data Structures and Algorithms in Java” . Saat membaca buku ini, Anda tidak hanya akan mempelajari banyak struktur data (termasuk tumpukan dan antrian), tetapi Anda juga akan mengimplementasikan banyak di antaranya sendiri! Misalnya, bayangkan jika Java tidak memiliki kelas Stack. Apa yang akan Anda lakukan jika Anda memerlukan struktur data seperti itu untuk program Anda? Tentu saja saya harus menulisnya sendiri. Saat membaca buku Laforet, hal ini sering kali Anda lakukan. Berkat ini, pemahaman Anda tentang struktur data akan jauh lebih luas daripada sekadar mempelajari teori :) Hari ini kita sudah selesai dengan teori, tetapi teori tanpa praktik bukanlah apa-apa! Masalah tidak akan terselesaikan dengan sendirinya, jadi sekaranglah waktunya untuk mengatasinya! :)