Antrian

Bagi kebanyakan orang, kata "antrean" mengingatkan sedikit asosiasi yang menyenangkan. Tapi hari ini kita berbicara tentang antrian yang berbeda — antrian Java. Di Java, antrian adalah segala sesuatu yang mewarisi antarmuka Antrean , yang pada gilirannya memperluas antarmuka Koleksi . Itu berarti antrian dapat diperlakukan seperti koleksi.

Antrian di Java mendukung dua prinsip operasi: FIFO dan LIFO .

Prinsip FIFO (First In, First Out) mengatur antrean reguler — elemen pertama yang ditambahkan ke antrean adalah yang pertama meninggalkannya.

Prinsip LIFO (Last In, First Out) menjelaskan perilaku stack — elemen terakhir yang ditambahkan ke antrian adalah yang pertama meninggalkannya. Misalnya, ini adalah cara Anda bekerja dengan setumpuk kartu: Anda mengambil kartu dari atas satu per satu sampai Anda mencapai bagian bawah tumpukan.

Hierarki antrian di Java terlihat seperti ini:

Di sini Anda dapat melihat bahwa Queue memiliki 3 kelas implementasi: LinkedList , ArrayDeque dan PriorityQueue . LinkedList dan ArrayDeque secara langsung mewarisi bukan Queue , tapi Deque .

Deque adalah antarmuka yang ditambahkan di Java 6. Ini mencakup beberapa metode yang berguna untuk antrian dan memungkinkan antrian berfungsi sebagai antrian ujung ganda (atau dua arah). Artinya bisaFIFOdanLIFO.

Salah satu dari dua keturunan antarmuka Deque adalah ArrayDeque . Ini mendukung antrian ujung ganda yang memungkinkan Anda memasukkan dan menghapus elemen dari kedua ujungnya. Ini juga merupakan larik dinamis yang ukurannya bertambah secara otomatis.

Ada juga kelas PriorityQueue , yang merupakan keturunan langsung dari Queue : perilakunya berbeda dari kelas yang mengimplementasikan Deque .

PriorityQueue adalah antrean prioritas yang mengatur elemen sesuai urutan alaminya secara default. Di sini penyortiran menggunakan antarmuka Sebanding dan Komparator . Prinsipnya sama dengan TreeSet atau TreeMap — kelas yang menggunakan antarmuka Sebanding dan memiliki tata urutannya sendiri.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Jika Anda menjalankan contoh ini, inilah yang akan Anda lihat di konsol:

Karena kami bekerja dengan antrian dan bukan koleksi biasa, kami perlu menghapus elemen dari daftar. Untuk melakukan ini, kami menggunakan konstruk ini:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

Antarmuka Deque mewarisi metode Queue dan menambahkan beberapa metode menariknya sendiri:

Sekarang mari kita lihat beberapa metode ini dalam praktiknya.

Pertama, mari tambahkan elemen ke antrean:

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue

        System.out.println(deque);

Sekarang mari kita dapatkan nilai dari antrian:

Deque<String> deque = new ArrayDeque<>();

deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");


        System.out.println("The first element is: "+ deque.getFirst());

        System.out.println("The last element is: " + deque.getLast());

    }

Kode ini menampilkan elemen pertama dan terakhir dari antrian.

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);

Menjalankan kode ini, kita mendapatkan:

Perbedaan antara pop() dan poll() adalah bahwa pop() akan memunculkan NoSuchElementException jika daftarnya adalah daftar kosong, tetapi poll() akan mengembalikan null .

Sekarang kita akan mempertimbangkan metode pollFirst() dan pollLast() .

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);

Kedua metode mengembalikan dan menghapus nilai dari antrian.

Berikut adalah contoh penggunaan metode peekFirst() dan peekLast() :

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);

Kedua metode mengembalikan elemen pertama/terakhir dari antrian dan tidak menghapusnya. Jika antrian kosong, null akan dikembalikan.

Bagus sekali! Hari ini kita belajar bagaimana bekerja dengan antrian di Java. Sekarang Anda tahu cara menggunakannya dalam praktik.