Antarmuka Antrian Java dan implementasinya

Di sini kita akan membahas antarmuka Java Queue. Anda akan mengetahui apa itu struktur data Antrian , bagaimana itu direpresentasikan dalam Java, metode apa yang paling penting untuk semua antrean. Juga, apa implementasi Antrian dalam bahasa Jawa. Setelah itu, kami melihat lebih dekat implementasi yang paling penting dan mempelajarinya dengan contoh.

Struktur data antrian

Antrean adalah struktur data abstrak linier dengan urutan tertentu dalam melakukan operasi — First In First Out (FIFO). Itu berarti Anda dapat menambahkan elemen (atau enqueue, masukkan ke dalam antrian) hanya di akhir struktur, dan ambil elemen (dequeue atau hapus dari antrian) hanya dari awal. Anda dapat membayangkan struktur data Queue dengan sangat mudah. Sepertinya antrian atau garis pelanggan dalam kehidupan nyata. Pelanggan yang datang lebih dulu, akan dilayani lebih dulu juga. Jika Anda memiliki empat orang dalam antrean di McDonalds atau di tempat lain, yang pertama berbaris akan menjadi yang pertama mendapatkan toko. Jika pelanggan baru datang, dia akan berada di urutan ke-5 untuk mendapatkan hamburger. Jadi, saat bekerja dengan antrian, elemen baru ditambahkan di bagian akhir, dan jika Anda ingin mendapatkan elemen, elemen tersebut akan diambil dari awal. Ini adalah prinsip utama kerja struktur data antrian klasik.

Antrean di Jawa

Antrian di Jawa adalah antarmuka. Menurut dokumentasi Oracle, antarmuka Queue memiliki 2 antarmuka super, 4 antarmuka berbeda yang diwarisi dari antrian, dan daftar kelas yang sangat mengesankan. Apa artinya? Pertama-tama, Java Queue adalah bagian dari Collection Framework dan mengimplementasikan antarmuka Collection. Jadi itu mendukung semua metode antarmuka Koleksi seperti penyisipan, penghapusan, dan sebagainya. Antrean mengimplementasikan antarmuka Iterable, yang memungkinkan objek menjadi target pernyataan "untuk setiap loop".

Metode Antrian Java

Queue mendeklarasikan sejumlah metode. Sebagai metode antarmuka, mereka harus direpresentasikan di semua kelas yang mengimplementasikan Queue. Metode Antrian yang paling penting, Java:

• Boolean offer() – menyisipkan elemen baru ke dalam antrian jika memungkinkan
• Boolean add(E e) – menyisipkan elemen baru ke dalam antrian jika memungkinkan. Mengembalikan true jika berhasil dan melontarkan IllegalStateException jika tidak ada ruang.
• Object poll() – mengambil dan menghapus elemen dari kepala. Mengembalikan null jika antrian kosong.
• Penghapusan objek () – mengambil dan menghapus elemen dari kepala antrian.
• Object peek() – mengambil, tetapi tidak menghapus elemen dari kepala antrean. Mengembalikan null jika antrian kosong.
• Elemen objek () – mengambil, tetapi tidak menghapus elemen dari kepala antrean.

Subinterface dari Java Queue

Antarmuka antrian diwarisi oleh 4 subantarmuka – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Anda dapat membaginya menjadi 3 grup: Deques, Blocking Queues, dan Transfer Queues dengan BlockingDeque milik keduanya terlebih dahulu. Mari kita lihat sekilas kelompok-kelompok ini.

Deques

Deque berarti Double - Ended Queue dan mendukung penambahan atau penghapusan dari salah satu ekor data sebagai antrian (first-in-first-out/FIFO) atau dari kepala sebagai struktur data populer lainnya yang disebut stack ( last - in- keluar pertama/LIFO). Kelas yang mengimplementasikan Antarmuka Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Memblokir Antrian

Antrean pemblokiran adalah antrean yang memblokir utas dalam dua kasus:

• utas mencoba mendapatkan elemen dari antrean kosong
• utas mencoba memasukkan elemen ke dalam antrean penuh

Saat utas mencoba mengambil item dari antrean kosong, utas akan menunggu hingga beberapa utas lain memasukkan item ke dalam antrean. Demikian pula, ketika sebuah utas mencoba memasukkan elemen ke dalam antrean penuh, ia menunggu hingga beberapa utas lain mengeluarkan elemen dari antrean untuk mendapatkan ruang kosong untuk elemen tersebut. Tentu, konsep "antrean penuh" menyiratkan bahwa antrean memiliki ukuran terbatas, yang biasanya ditentukan dalam konstruktor. Antrean Pemblokiran Standar termasuk LinkedBlockingQueue, SynchronousQueue, dan ArrayBlockingQueue. Menerapkan kelas antarmuka BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeadalah subantarmuka untuk BlockingQueue. BlockingDeque seperti BlockingQueue adalah antrian pemblokiran, tetapi dua arah. Jadi itu mewarisi properti antarmuka Deque. Ini berorientasi pada eksekusi multi-utas, tidak mengizinkan elemen nol dan kapasitas dapat dibatasi. Implementasi antarmuka BlockingDeque memblokir operasi mendapatkan elemen jika antrean kosong, dan menambahkan elemen ke antrean jika penuh.

Antrian Transfer

Antarmuka TransferQueue memperluas antarmuka BlockingQueue. Namun tidak seperti penerapan antrean antarmuka BlockingQueue, di mana utas dapat diblokir jika antrean kosong (membaca), atau jika antrean penuh (menulis), antrean antarmuka TransferQueue memblokir aliran tulis hingga aliran lain mengambil elemen. Gunakan metode transfer untuk ini. Dengan kata lain, implementasi BlockingQueue menjamin bahwa elemen yang dibuat oleh Producer harus berada dalam antrian, sedangkan implementasi TransferQueue menjamin bahwa elemen Producer "diterima" oleh Konsumen. Hanya ada satu implementasi Java resmi dari antarmuka TransferQueue — LinkedTransferQueue.

Implementasi Antrian Java

Ada banyak kelas yang mengimplementasikan antarmuka Queue:

• AbstractQueue menurut dokumen Queue Java 8, kelas abstrak ini menyediakan implementasi dasar dari beberapa operasi Queue. Itu tidak mengizinkan elemen nol. Ada 3 metode lagi tambah, hapus, dan elemen berdasarkan Queue klasik masing- masing offer , poll , dan peek . Namun mereka membuang pengecualian alih-alih menunjukkan kegagalan melalui pengembalian palsu atau nol.
• ArrayBlockingQueue — antrean pemblokiran FIFO ukuran tetap yang didukung oleh larik
• ArrayDeque — implementasi array yang dapat diubah ukurannya dari antarmuka Deque
• ConcurrentLinkedDeque — deque bersamaan tanpa batas berdasarkan node yang ditautkan.
• ConcurrentLinkedQueue — antrean thread-safe tanpa batas berdasarkan node tertaut.
• DelayQueue — antrean penjadwalan berbasis waktu yang didukung oleh heap
• LinkedBlockingDeque — implementasi bersamaan dari antarmuka Deque.
• LinkedBlockingQueue — antrean pemblokiran FIFO yang dibatasi secara opsional yang didukung oleh node tertaut
• LinkedList — implementasi daftar tertaut ganda dari antarmuka List dan Deque. Menerapkan semua operasi daftar opsional, dan mengizinkan semua elemen (termasuk nol)
• LinkedTransferQueue — TransferQueue tak terbatas berdasarkan node tertaut
• PriorityBlockingQueue — antrean prioritas pemblokiran tanpa batas yang didukung oleh heap
• PriorityQueue — antrean prioritas berdasarkan struktur data heap
• SynchronousQueue — antrean pemblokiran di mana setiap operasi penyisipan harus menunggu operasi penghapusan terkait oleh utas lain, dan sebaliknya.

Implementasi yang paling populer adalah LinkedList, ArrayBlockingQueue, dan PriorityQueue. Mari kita lihat dan lakukan beberapa contoh untuk pemahaman yang lebih baik.

LinkedList

Class LinkedList di Java mengimplementasikan antarmuka List dan Deque. Jadi, ini adalah kombinasi dari List dan Deque, antrian dua arah, yang mendukung penambahan dan penghapusan elemen dari kedua sisi. Dalam Java LinkedList adalah Daftar tertaut ganda: setiap elemen Daftar memanggil Node dan berisi objek dan referensi ke dua objek tetangga — sebelumnya dan berikutnya. Anda mungkin mengatakan bahwa LinkedList tidak terlalu efektif dalam hal penggunaan memori. Itu benar, tetapi struktur data ini dapat berguna dalam kasus kinerja operasi penyisipan dan penghapusan. Namun itu terjadi hanya jika Anda menggunakan iterator untuk mereka (dalam hal ini terjadi dalam waktu yang konstan). Operasi akses berdasarkan indeks dilakukan dengan mencari dari awal hingga akhir (mana yang lebih dekat) ke elemen yang diinginkan. Namun, jangan lupakan biaya tambahan untuk menyimpan referensi antar elemen. Jadi, LinkedList adalah implementasi antrian paling populer di Jawa. Ini juga merupakan implementasi dari List dan Deque dan memungkinkan kita membuat antrian dua arah yang terdiri dari objek apa pun termasuk null. LinkedList adalah kumpulan elemen.

Konstruktor LinkedList

LinkedList() tanpa parameter digunakan untuk membuat daftar kosong. LinkedList(Collection<? extends E> c) adalah untuk membuat daftar yang berisi elemen dari koleksi yang ditentukan, agar dikembalikan oleh iterator koleksi.

Metode LinkedList Utama:

• add(E element) Menambahkan elemen yang ditentukan ke akhir daftar ini;
• add(int index, E element) Menyisipkan elemen pada indeks posisi yang ditentukan;
• get(int index) Mengembalikan elemen pada posisi yang ditentukan dalam daftar ini;
• remove(int index) Menghapus elemen yang berada pada indeks posisi;
• remove(Object o) Menghapus kemunculan pertama elemen ?o dari daftar ini jika ada.
• remove() Mengambil dan menghapus elemen pertama dari daftar.
• addFirst(), addLast() menambahkan elemen ke awal/akhir daftar
• clear() menghapus semua elemen dari daftar
• berisi(Objek o) mengembalikan nilai true jika daftar berisi elemen o.
• indexOf(Object o) mengembalikan indeks kemunculan pertama elemen o, atau -1 jika tidak ada dalam daftar.
• set(int index, elemen E) mengganti elemen pada posisi indeks dengan elemen
• size()Mengembalikan jumlah elemen dalam daftar.
• toArray() mengembalikan array yang berisi semua elemen daftar dari elemen pertama hingga elemen terakhir.
• pop() yang memunculkan elemen dari tumpukan (diwakili oleh daftar)
• push(E e) yang mendorong elemen ke tumpukan (diwakili oleh daftar ini)

Contoh Antrean Java — LinkedList (menempatkan dan menghapus elemen dengan cara yang berbeda)

import java.util.*;
 
public class LinkedListTest {
 
       public static void main(String args[]){
 
           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

PriorityQueue

PriorityQueue bukanlah antrian dalam pengertian umum FIFO. Elemen-elemen antrian prioritas diurutkan sesuai urutan alaminya, atau oleh Pembanding yang disediakan pada waktu konstruksi antrian, bergantung pada konstruktor mana yang digunakan. Namun itu bukan urutan seperti itu bisa dalam struktur linier seperti daftar (dari yang terbesar ke yang terkecil atau sebaliknya). Antrean prioritas berdasarkan tumpukan min prioritas. Heap adalah struktur data berdasarkan pohon biner. Prioritas setiap orang tua lebih besar dari prioritas anak-anaknya. Sebuah pohon disebut biner lengkap jika setiap orang tua tidak memiliki lebih dari dua anak, dan pengisian level dilakukan dari atas ke bawah (dari level yang sama - dari kiri ke kanan). Tumpukan biner mengatur ulang dirinya sendiri setiap kali elemen baru ditambahkan atau dihapus darinya. Dalam kasus min-heap, elemen terkecil masuk ke root terlepas dari urutan penyisipannya. Antrean prioritas berdasarkan min-heap ini, jadi jika kita memiliki PriorityQueue bilangan bulat, elemen pertamanya adalah yang terkecil dari angka-angka ini. Jika Anda menghapus root, terkecil berikutnya menjadi root.

Metode Antrian Prioritas Utama:

• boolean add(object) menyisipkan elemen tertentu ke dalam antrian prioritas. Mengembalikan true jika berhasil. Jika antrean penuh, metode melontarkan pengecualian.
• boolean offer(object) menyisipkan elemen tertentu ke dalam antrian prioritas ini. Jika antrian sudah penuh, metode mengembalikan false.
• boolean remove(object) menghapus satu instance dari elemen yang ditentukan dari antrian ini, jika ada.
• Polling objek () mengambil dan menghapus kepala antrian ini. Mengembalikan null jika antrian kosong.
• void clear() menghapus semua elemen dari antrian prioritas.
• Elemen objek () mengambil kepala antrian ini tanpa menghapusnya. Melempar NoSuchElementException jika antrean kosong.
• Object peek() mengambil kepala antrian tanpa menghapusnya. Mengembalikan null jika antrian kosong.
• boolean berisi(Objek o) mengembalikan true jika antrian berisi elemen o.
• int size() mengembalikan jumlah elemen dalam antrian ini.

Contoh PriorityQueue

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Penting untuk dipahami bahwa antrian prioritas didasarkan pada tumpukan biner, sehingga mereka tidak menyimpan elemen dalam urutan terurut linier. Setiap jalan dari akar ke daun diurutkan, tetapi jalan yang berbeda dari akar tidak. Artinya, Anda bisa mendapatkan elemen antrean minimal dengan sangat cepat. Jika Anda menghapus kepala setiap saat, Anda akan mencetak struktur yang diurutkan.

ArrayBlockingQueue

Struktur data internal ArrayBlockingQueuedidasarkan pada array melingkar untuk menyimpan elemen. Ini adalah antrian tipikal (FIFO) jika elemen baru dimasukkan di bagian belakang antrian, dan operasi ekstraksi mengembalikan elemen dari kepala antrian. Kapasitas antrian yang dibuat tidak dapat diubah. Upaya untuk memasukkan (memasukkan) elemen ke dalam antrian penuh menyebabkan pemblokiran aliran; mencoba mengambil elemen dari antrean kosong juga memblokir utas. Seperti yang kami katakan sebelumnya, array ini berbentuk lingkaran. Itu berarti bahwa elemen pertama dan terakhir dari array diperlakukan berdekatan secara logis. Antrean memajukan indeks elemen kepala dan ekor setiap kali Anda memasukkan elemen ke dalam antrean atau menghapusnya dari antrean. Jika beberapa indeks memajukan elemen terakhir dari array, itu dimulai ulang dari 0. Oleh karena itu, antrian tidak harus menggeser semua elemen jika head dilepas (seperti pada larik biasa). Namun, jika menghapus elemen dari tengah (menggunakan Iterator.remove), elemen akan digeser. ArrayBlockingQueue mendukung kebijakan keadilan tambahan dengan parameter adil di konstruktor untuk mengatur pekerjaan alur menunggu produsen (memasukkan elemen) dan konsumen (mengekstrak elemen). Secara default, pesanan tidak dijamin. Namun jika antrean dibuat dengan "adil == benar", penerapan kelas ArrayBlockingQueue menyediakan akses utas dalam urutan FIFO. Ekuitas biasanya mengurangi bandwidth, tetapi juga mengurangi volatilitas dan mencegah kehabisan sumber daya.

ArrayBlockingQueue Class konstruktor

• ArrayBlockingQueue (int kapasitas) membuat antrian kapasitas tetap dan dengan kebijakan akses default.
• ArrayBlockingQueue (int capacity, boolean fair) membuat antrian dengan kapasitas tetap dan kebijakan akses yang ditentukan.
• ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) membuat antrian dengan kapasitas tetap yang ditentukan oleh kebijakan akses dan menyertakan elemen dalam antrian.

Di sini kita punya contoh BlockingQueueExample. Kami membuat antrian ArrayBlockingQueue dengan kapasitas satu elemen dan bendera yang adil. Dua utas dimulai. Yang pertama, Producer thread, mengantri pesan dari larik pesan menggunakan metode put. Yang kedua, Konsumen, utas membaca elemen dari antrean menggunakan metode take dan menampilkannya di konsol. Urutan elemen adalah yang alami untuk antrean.

import java.util.concurrent.*;
 
public class ArrayBlockingQueueExample {
 
   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};
  
       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }
 
       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

Outputnya adalah antrian dalam urutan alami; dua elemen pertama muncul dengan penundaan. Untuk memperkuat apa yang Anda pelajari, kami sarankan Anda menonton video pelajaran dari Kursus Java kami

Kesimpulan

• Queue digunakan untuk menyisipkan elemen di akhir antrian dan menghapus dari awal antrian. Ini mengikuti konsep FIFO.
• Java Queue adalah bagian dari Collection Framework dan mengimplementasikan antarmuka Collection. Jadi itu mendukung semua metode antarmuka Koleksi seperti penyisipan, penghapusan, dan sebagainya.
• Implementasi Queue yang paling sering digunakan adalah LinkedList, ArrayBlockingQueue, dan PriorityQueue.
• Elemen-elemen antrian prioritas diurutkan sesuai urutan alaminya, atau oleh Pembanding yang disediakan pada waktu konstruksi antrian, bergantung pada konstruktor mana yang digunakan.
• Jika ada operasi null yang dilakukan pada BlockingQueues, NullPointerException akan dilempar.