Struktur data: tumpukan dan antrian

Hai! Hari ini kita akan berbicara tentang sesuatu yang sangat penting bagi pemrogram mana pun: struktur data. Wikipedia mengatakan: " Struktur data adalah organisasi data, manajemen, dan format penyimpanan yang memungkinkan akses dan modifikasi yang efisien. Lebih tepatnya, struktur data adalah kumpulan nilai data, hubungan di antara mereka, dan fungsi atau operasi yang dapat diterapkan pada data." Definisinya agak membingungkan, tetapi intinya jelas. Struktur data adalah sejenis repositori tempat kami menyimpan data untuk digunakan di masa mendatang. Dalam pemrograman, ada berbagai macam struktur data. Saat memecahkan masalah tertentu, seringkali hal terpenting adalah memilih struktur data yang paling cocok untuk masalah tersebut. Dan Anda sudah familiar dengan banyak dari mereka! Misalnya, Anda tahu tentang array. Dan Anda juga akrab denganMap(struktur data ini juga dapat disebut sebagai "kamus" atau "array asosiatif"). Sangat penting untuk dipahami bahwa struktur data tidak terikat pada bahasa tertentu. Mereka hanyalah "cetak biru" abstrak yang digunakan setiap bahasa pemrograman untuk membuat kelasnya sendiri atau implementasi dari struktur tertentu. Misalnya, salah satu struktur data yang paling terkenal adalah linked list. Anda dapat pergi ke Wikipedia dan membaca tentang cara kerjanya dan kelebihan dan kekurangan apa yang dimilikinya. Mungkin definisinya tidak asing bagi Anda :) "Daftar tertaut adalah kumpulan elemen data linier, yang urutannya tidak diberikan oleh penempatan fisiknya di memori. Sebaliknya, setiap elemen menunjuk ke yang berikutnya." Itu menggambarkan kekasih kita LinkedList, bukan? Ya, dan memang seperti itu :) Di Java, struktur data "daftar tertaut" diimplementasikan oleh kelas LinkedList. Tetapi bahasa lain juga menerapkan daftar tertaut! Di Python, struktur data ini disebut " llist". Di Scala disebut " LinkedList", seperti di Jawa. Daftar tertaut adalah salah satu struktur data dasar yang umum, sehingga Anda akan menemukan bahwa itu diimplementasikan dalam bahasa pemrograman modern apa pun. Hal yang sama berlaku untuk array asosiatif. Berikut adalah definisi dari Wikipedia: "Array asosiatif, peta, tabel simbol, atau kamus adalah tipe data abstrak yang terdiri dari kumpulan pasangan (kunci, nilai), sehingga setiap kunci yang mungkin muncul paling banyak sekali dalam kumpulan." Apakah itu mengingatkan Anda pada sesuatu? :) Yap. Bagi kami pengembang Java, array asosiatif adalahMapantarmuka. Tetapi struktur data ini juga diimplementasikan dalam bahasa lain! Misalnya, pemrogram C# mengetahuinya dengan nama "Dictionary". Dan di Ruby, itu diimplementasikan dalam kelas yang disebut "Hash". Nah, Anda mengerti maksudnya: struktur data adalah konsep universal dalam pemrograman, dan setiap bahasa pemrograman mengimplementasikannya dengan caranya sendiri. Hari ini kita akan mempelajari dua struktur seperti itu — tumpukan dan antrian — dan melihat bagaimana penerapannya di Java.

Tumpukan di Jawa

Tumpukan adalah struktur data yang terkenal. Ini sangat sederhana. Cukup banyak item dalam kehidupan kita sehari-hari yang "diimplementasikan" sebagai tumpukan. Bayangkan situasi sederhana ini: Anda menginap di sebuah hotel, dan sepanjang hari itu Anda menerima beberapa surat bisnis. Anda tidak berada di kamar Anda saat itu, jadi petugas hotel hanya meletakkan surat masuk di meja Anda. Pertama, dia meletakkan surat 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 pertanyaan sederhana: surat apa yang akan Anda baca pertama kali saat kembali ke kamar dan melihat tumpukan di atas meja? Benar, Anda akan membaca yang paling atassurat. Yaitu, yang paling baru tiba . Ini persis bagaimana tumpukan bekerja. Prinsip ini disebut “last in first out” (LIFO) . Apa gunanya tumpukan? Nah, misalkan Anda membuat semacam permainan kartu di Jawa. Setumpuk kartu terletak di atas meja. Kartu yang dimainkan dibuang. Anda dapat menggunakan dua tumpukan untuk mengimplementasikan dek undian dan tumpukan buangan. Pemain mengambil kartu mereka dari atas dek, mengikuti prinsip yang sama dengan surat bisnis Anda. Saat pemain memasukkan kartu ke dalam tumpukan buangan, kartu yang baru dibuang ditempatkan di atas yang lama. Inilah upaya pertama kami dalam permainan, diimplementasikan berdasarkan 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.
}

Seperti yang kami katakan sebelumnya, kami memiliki dua tumpukan: tumpukan undian dan tumpukan buangan. Di Java, struktur data tumpukan diimplementasikan di java.util.Stackkelas. Permainan kartu kami memiliki 3 metode yang menjelaskan tindakan para pemain:

• ambil kartu dari dek ( getCardFromDeck()metode)
• membuang kartu ( discard()metode)
• lihat kartu teratas ( lookAtTopCard()metode). Katakanlah ini adalah bonus "Kecerdasan" yang memungkinkan pemain mengetahui kartu mana yang akan datang berikutnya dalam permainan.

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

• push()— menambahkan item ke bagian atas tumpukan. Saat kami mengirim kartu ke tumpukan buangan, kartu itu masuk ke tumpukan paling atas
• pop()- menghapus elemen teratas dari tumpukan dan mengembalikannya. Metode ini sangat cocok untuk menerapkan tindakan di mana pemain menarik kartu.
• peek()— mengembalikan elemen teratas tumpukan, tetapi tidak menghapusnya dari tumpukan

Mari kita lihat bagaimana permainan kita akan bekerja:

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

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

Perhatikan urutan kartu yang ditampilkan di konsol. Kartu "Edwin VanCleef" masuk ke dek terakhir (itu adalah kartu kelima), dan itu adalah kartu yang ditarik pemain terlebih dahulu. "Millhouse" berada di urutan kedua terakhir di geladak, dan pemain menggambarnya di urutan kedua. "Sylvanas" masuk ke dek ketiga dari atas, dan itu adalah kartu ketiga yang ditarik pemain. Selanjutnya, pemain membuang kartu. Pertama, dia membuang Edwin, lalu Millhouse, lalu Sylvanas. Kemudian kami menampilkan kartu di tumpukan buangan kami satu per satu: Keluaran konsol:

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

Sekali lagi, kita melihat cara kerja stack! Dalam permainan kami, tumpukan buangan juga merupakan tumpukan (seperti tumpukan undian). "Edwin VanCleef" dibuang lebih dulu. Buang kartu kedua adalah Millhouse Manastorm, dan ditempatkan di atas Edwin di tumpukan buangan. Kemudian Sylvanas dibuang, dan kartu ini diletakkan di atas Millhouse. Seperti yang Anda lihat, tidak ada yang rumit tentang tumpukan. Namun, Anda perlu mengetahui struktur data ini — ini sering ditanyakan selama wawancara kerja, dan seringkali menjadi dasar untuk membangun struktur data yang lebih kompleks.

Antrean di Jawa

Antrian adalah struktur data umum lainnya. Selain tumpukan, banyak bahasa pemrograman, termasuk Java, juga menerapkan struktur data antrian. Apa perbedaan antara antrian dan tumpukan? Antrian tidak didasarkan pada prinsip LIFO, melainkan pada prinsip FIFO ("masuk pertama, keluar pertama"). Prinsip ini mudah dipahami dengan mempertimbangkan, misalnya, garis biasa, atau antrian, dalam kehidupan nyata! Misalnya antrean di toko kelontong. Jika ada lima orang dalam antrean, yang pertama dilayani adalah orang yang masuk antrean terlebih dahulu . Jika orang lain (selain lima yang sudah mengantri) ingin membeli sesuatu dan mengantri, maka dia dilayani terakhir, yaitu keenam. Saat bekerja dengan antrian, elemen baru ditambahkan ke ekor (belakang), dan jika Anda ingin mendapatkan elemen, itu akan diambil dari kepala (depan). Ini adalah prinsip utama yang perlu Anda ingat tentang cara kerja antrian. Operasi antrean sangat intuitif, karena sering kali kita menemukan antrean di kehidupan nyata. Perlu dicatat secara terpisah bahwa dalam Java, antrian direpresentasikan bukan oleh kelas, tetapi oleh antarmuka: Queue. Terlebih lagi, ada banyak implementasi antarmuka antrian ini di Jawa. Jika kita melihat dokumentasi Oracle, kita akan melihat bahwa 4 antarmuka berbeda, serta daftar kelas yang sangat mengesankan, mewarisi antarmuka 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

Daftar yang sangat besar! Tapi, tentu saja, Anda tidak perlu menghafal semua kelas dan antarmuka ini sekarang — kepala Anda mungkin meledak :) Kami hanya akan mempertimbangkan beberapa poin yang paling penting dan menarik. Pertama, mari perhatikan salah satu dari empat "subantarmuka" Queue: Deque . Apa yang membuatnya begitu istimewa? A Dequeadalah antrian ujung ganda. Ini memperluas fungsionalitas antrean biasa, memungkinkan Anda menambahkan elemen ke kedua ujungnya (di kepala dan ekor) dan mengambil elemen dari kedua ujung antrean. Antrean ujung ganda banyak digunakan dalam pengembangan perangkat lunak. Perhatikan daftar kelas antrian yang kami berikan di atas. Daftarnya cukup panjang, tetapi apakah berisi sesuatu yang familier?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Inilah teman lama kita LinkedList! Jadi, ini mengimplementasikan antarmuka Queue? Tapi bagaimana itu bisa menjadi antrian? Lagipula, a LinkedListadalah linked list! Benar, tapi itu tidak menghentikannya menjadi antrean :) 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, LinkedListmengimplementasikan Dequeantarmuka (sekali lagi, ini berarti antrian ujung ganda). Mengapa ini dibutuhkan? Ini memungkinkan kita untuk mendapatkan elemen dari awal dan akhir file LinkedList. Itu juga memungkinkan kita untuk menambahkan elemen ke awal dan akhir. Berikut adalah metode yang LinkedListdidapat dari Dequeantarmuka:

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

Seperti yang Anda lihat, LinkedListmengimplementasikan sepenuhnya fungsi antrian ujung ganda! Dan Anda memerlukan fungsionalitas seperti itu dalam program Anda, Anda akan tahu di mana menemukannya :) Pelajaran hari ini akan segera berakhir. Sebagai kesimpulan, saya akan memberi Anda beberapa tautan untuk bacaan tambahan. Pertama, perhatikan artikel ini tentang PriorityQueue . Ini adalah salah satu Queueimplementasi yang paling menarik dan berguna. Misalnya, ada 50 orang mengantri di toko Anda, dan 7 di antaranya adalah pelanggan VIP. PriorityQueue akan membiarkan Anda melayani mereka terlebih dahulu! Barang yang sangat berguna bukan? :) Kedua, tidak ada salahnya untuk sekali lagi menyebut buku Robert Lafore "Data Structures and Algorithms in Java". Membaca buku ini, Anda tidak hanya akan mempelajari banyak struktur data (termasuk stack dan queue), tetapi Anda juga akan mengimplementasikannya sendiri! Misalnya, bagaimana jika Java tidak memiliki kelas Stack? Apa yang akan Anda lakukan jika Anda membutuhkan struktur data seperti itu untuk program Anda? Anda harus menulisnya sendiri, tentu saja. Saat Anda membaca buku Lafore , Anda akan sering melakukannya. Akibatnya, pemahaman Anda tentang struktur data akan jauh lebih dalam daripada apa yang akan Anda dapatkan dari studi teori sederhana :) Kami sedang menyelesaikan teori untuk hari ini, tetapi teori tanpa praktik bukanlah apa-apa! Tugas tidak akan selesai dengan sendirinya, jadi inilah saatnya untuk menanganinya! :)