Antara Muka Gilir Java dan pelaksanaannya

Di sini kita akan membincangkan antara muka Java Queue. Anda akan mengetahui apakah struktur data Queue , bagaimana ia diwakili dalam Java, apakah kaedah yang paling penting untuk semua baris gilir. Juga, apakah pelaksanaan Queue dalam bahasa Java. Selepas itu, kami melihat dengan lebih dekat pelaksanaan yang paling penting dan mempelajarinya dengan contoh.

Struktur data baris gilir

Baris Gilir ialah struktur data abstrak linear dengan tertib tertentu melaksanakan operasi — Mula-mula Masuk Dahulu (FIFO). Ini bermakna anda boleh menambah elemen (atau enqueue, masukkan ke dalam baris gilir) hanya pada penghujung struktur, dan mengambil elemen (dequeue atau alih keluar dari baris gilir) hanya dari permulaannya. Anda mungkin membayangkan struktur data Baris dengan mudah. Ia kelihatan seperti barisan atau barisan pelanggan dalam kehidupan sebenar. Pelanggan yang datang dahulu, akan dilayan dahulu juga. Jika anda mempunyai empat orang dalam barisan di McDonalds atau di tempat lain, yang pertama beratur akan menjadi yang pertama mendapatkan kedai. Jika pelanggan baru datang, dia akan menjadi yang ke-5 dalam barisan untuk mendapatkan hamburger. Jadi, semasa bekerja dengan baris gilir, elemen baharu ditambahkan pada penghujung, dan jika anda ingin mendapatkan elemen, ia akan diambil dari awal. Ini adalah prinsip utama kerja struktur data baris gilir klasik.

Beratur di Jawa

Baris gilir dalam Java ialah antara muka. Menurut dokumentasi Oracle, antara muka Queue mempunyai 2 superinterface, 4 antara muka berbeza yang mewarisi daripada baris gilir, dan senarai kelas yang sangat mengagumkan. Apakah maksudnya? Pertama sekali, Java Queue ialah sebahagian daripada Rangka Kerja Koleksi dan melaksanakan antara muka Koleksi. Jadi ia menyokong semua kaedah antara muka Koleksi seperti sisipan, pemadaman dan sebagainya. Baris gilir melaksanakan antara muka Boleh Diterbalikkan, yang membolehkan objek menjadi sasaran pernyataan "untuk setiap gelung".

Kaedah Beratur Java

Barisan Gilir mengisytiharkan beberapa kaedah. Sebagai kaedah antara muka mereka harus diwakili dalam semua kelas yang melaksanakan Queue. Kaedah Gilir yang paling penting, Java:

• Tawaran Boolean() – memasukkan elemen baharu ke dalam baris gilir jika boleh
• Boolean add(E e) – memasukkan elemen baharu ke dalam baris gilir jika boleh. Mengembalikan benar sekiranya berjaya dan membuang IllegalStateException jika tiada ruang.
• Tinjauan objek() – mengambil dan mengalih keluar elemen daripada kepala. Mengembalikan batal jika baris gilir kosong.
• Object remove() – mengambil dan mengalih keluar elemen dari kepala baris gilir.
• Object peek() – mendapatkan semula, tetapi tidak mengalih keluar elemen daripada kepala baris gilir. Mengembalikan batal jika baris gilir kosong.
• Elemen objek() – mendapatkan semula, tetapi tidak mengalih keluar elemen daripada kepala baris gilir.

Subantara muka Java Queue

Antara muka baris gilir diwarisi oleh 4 subantara muka – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Anda boleh membahagikan mereka kepada 3 kumpulan: Deques, Blocking Queues dan Transfer Queues dengan BlockingDeque milik kedua-duanya dahulu. Mari kita lihat sekilas kumpulan ini.

Deques

Deque bermaksud D ouble- E nded Q ue dan menyokong penambahan atau penyingkiran daripada sama ada ekor data sebagai baris gilir (first-in-first-out/FIFO) atau dari head sebagai satu lagi struktur data popular yang dipanggil stack (last - in- keluar dahulu/LIFO). Kelas yang melaksanakan Antara Muka Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Menyekat Baris

Baris menyekat ialah baris gilir yang menyekat benang dalam dua kes:

• thread cuba mendapatkan elemen daripada baris gilir kosong
• benang cuba meletakkan elemen dalam baris gilir penuh

Apabila benang cuba mendapatkan item daripada baris gilir kosong, ia menunggu sehingga beberapa utas lain meletakkan item ke dalam baris gilir. Begitu juga, apabila benang cuba meletakkan elemen ke dalam baris gilir penuh, ia menunggu sehingga beberapa utas lain mengeluarkan elemen daripada baris gilir untuk mendapatkan ruang kosong untuk elemen. Pasti, konsep "baris gilir penuh" membayangkan bahawa baris gilir mempunyai saiz terhad, yang biasanya dinyatakan dalam pembina. Baris Sekatan Standard termasuk LinkedBlockingQueue, SynchronousQueue dan ArrayBlockingQueue. Melaksanakan kelas antara muka BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeialah subantara muka untuk BlockingQueue. BlockingDeque seperti BlockingQueue ialah baris gilir menyekat, tetapi dua arah. Jadi ia mewarisi sifat antara muka Deque. Ia berorientasikan kepada pelaksanaan berbilang benang, tidak membenarkan sifar elemen dan kapasiti boleh dihadkan. Pelaksanaan antara muka BlockingDeque menyekat operasi mendapatkan elemen jika baris gilir kosong, dan menambah elemen ke dalam baris gilir jika ia penuh.

Pindah Baris

Antara muka TransferQueue memanjangkan antara muka BlockingQueue. Bagaimanapun, tidak seperti pelaksanaan baris gilir antara muka BlockingQueue, di mana benang boleh disekat jika baris gilir kosong (membaca), atau jika baris gilir penuh (menulis), baris gilir antara muka TransferQueue menyekat aliran tulis sehingga aliran lain mendapatkan semula elemen tersebut. Gunakan kaedah pemindahan untuk ini. Dengan kata lain, pelaksanaan BlockingQueue menjamin bahawa elemen yang dicipta oleh Producer mesti berada dalam baris gilir, manakala pelaksanaan TransferQueue menjamin bahawa elemen Producer "diterima" oleh Pengguna. Terdapat hanya satu pelaksanaan Java rasmi antara muka TransferQueue — LinkedTransferQueue.

Pelaksanaan Java Queue

Terdapat banyak kelas yang melaksanakan antara muka Baris:

• AbstractQueue mengikut Queue Java 8 docs, kelas abstrak ini menyediakan pelaksanaan asas beberapa operasi Queue. Ia tidak membenarkan unsur nol. Terdapat 3 lagi kaedah tambah, alih keluar dan elemen berdasarkan Baris gilir tawaran klasik , tinjauan pendapat dan intip , masing-masing. Walau bagaimanapun, mereka membuang pengecualian dan bukannya menunjukkan kegagalan melalui pulangan palsu atau batal.
• ArrayBlockingQueue — baris gilir penyekat FIFO saiz tetap yang disokong oleh tatasusunan
• ArrayDeque — pelaksanaan tatasusunan boleh ubah saiz antara muka Deque
• ConcurrentLinkedDeque — deque serentak tanpa sempadan berdasarkan nod terpaut.
• ConcurrentLinkedQueue — baris gilir selamat benang tanpa sempadan berdasarkan nod terpaut.
• DelayQueue — baris gilir penjadualan berasaskan masa yang disokong oleh timbunan
• LinkedBlockingDeque — pelaksanaan serentak antara muka Deque.
• LinkedBlockingQueue — baris gilir penyekat FIFO bersempadan pilihan yang disokong oleh nod terpaut
• LinkedList — pelaksanaan senarai terpaut dua kali bagi antara muka Senarai dan Deque. Melaksanakan semua operasi senarai pilihan, dan membenarkan semua elemen (termasuk null)
• LinkedTransferQueue — TransferQueue tanpa sempadan berdasarkan nod terpaut
• PriorityBlockingQueue — baris gilir keutamaan menyekat tanpa had yang disokong oleh timbunan
• PriorityQueue — baris gilir keutamaan berdasarkan struktur data timbunan
• SynchronousQueue — baris gilir menyekat di mana setiap operasi sisipan mesti menunggu operasi alih keluar yang sepadan oleh utas lain, dan begitu juga sebaliknya.

Pelaksanaan yang paling popular ialah LinkedList, ArrayBlockingQueue dan PriorityQueue. Mari kita lihat mereka dan lakukan beberapa contoh untuk pemahaman yang lebih baik.

LinkedList

Class LinkedList dalam Java melaksanakan antara muka Senarai dan Deque. Jadi, ia adalah gabungan Senarai dan Deque, baris gilir dua hala, yang menyokong menambah dan mengalih keluar elemen dari kedua-dua belah pihak. Dalam Java LinkedList ialah Senarai terpaut dua kali: setiap elemen Senarai memanggil Nod dan mengandungi objek dan rujukan kepada dua objek bersebelahan — yang sebelumnya dan seterusnya. Anda mungkin mengatakan bahawa LinkedList tidak begitu berkesan dari segi penggunaan memori. Itu benar, tetapi struktur data ini boleh berguna sekiranya prestasi operasi memasukkan dan memadam. Walau bagaimanapun ia berlaku hanya jika anda menggunakan iterator untuk mereka (dalam kes ini ia berlaku dalam masa yang tetap). Operasi capaian mengikut indeks dilakukan dengan mencari dari awal penghujung (yang mana lebih dekat) kepada elemen yang dikehendaki. Walau bagaimanapun, jangan lupa tentang kos tambahan untuk menyimpan rujukan antara elemen. Jadi, LinkedList ialah pelaksanaan baris gilir yang paling popular di Jawa. Ia juga merupakan pelaksanaan Senarai dan Deque dan ia membolehkan kami membuat baris gilir dua arah yang terdiri daripada sebarang objek termasuk null. LinkedList ialah koleksi elemen.

Pembina LinkedList

LinkedList() tanpa parameter digunakan untuk membina senarai kosong. LinkedList(Collection<? extends E> c) adalah untuk mencipta senarai yang mengandungi unsur-unsur koleksi yang ditentukan, supaya ia dikembalikan oleh iterator koleksi.

Kaedah Senarai Pautan Utama:

• add(E element) Menambahkan elemen yang ditentukan pada penghujung senarai ini;
• add(int index, E element) Memasukkan elemen pada indeks kedudukan yang ditentukan;
• get(int index) Mengembalikan elemen pada kedudukan yang ditentukan dalam senarai ini;
• remove(int index) Mengeluarkan elemen yang berada pada indeks kedudukan;
• remove(Objek o) Mengalih keluar kejadian pertama unsur ?o daripada senarai ini jika ia ada.
• remove() Mengambil dan mengalih keluar elemen pertama senarai.
• addFirst(), addLast() menambah elemen pada permulaan/akhir senarai
• clear() mengalih keluar semua elemen daripada senarai
• mengandungi(Objek o) mengembalikan benar jika senarai mengandungi elemen o.
• indexOf(Objek o) mengembalikan indeks kejadian pertama unsur o, atau -1 jika ia tiada dalam senarai.
• set(int index, E element) menggantikan elemen pada kedudukan indeks dengan elemen
• size()Mengembalikan kuantiti elemen dalam senarai.
• toArray() mengembalikan tatasusunan yang mengandungi semua elemen senarai dari elemen pertama hingga terakhir.
• pop() yang memaparkan elemen dari timbunan (diwakili oleh senarai)
• push(E e) yang menolak elemen ke dalam timbunan (diwakili oleh senarai ini)

Contoh Java Queue — LinkedList (meletakkan dan mengalih keluar elemen dengan cara yang berbeza)

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 baris gilir dalam makna umum FIFO. Unsur-unsur baris gilir keutamaan disusun mengikut susunan semula jadinya, atau oleh Pembanding yang disediakan pada masa pembinaan baris gilir, bergantung pada pembina yang digunakan. Walau bagaimanapun, ia bukan susunan seperti dalam struktur linear seperti senarai (daripada yang terbesar kepada yang terkecil atau sebaliknya). Baris gilir keutamaan berdasarkan timbunan min keutamaan. Heap ialah struktur data berdasarkan pepohon binari. Keutamaan setiap ibu bapa adalah lebih besar daripada keutamaan anak-anaknya. Sebatang pokok dipanggil binari lengkap jika setiap ibu bapa mempunyai tidak lebih daripada dua anak, dan pengisian tahap pergi dari atas ke bawah (dari tahap yang sama — dari kiri ke kanan). Timbunan binari menyusun semula dirinya setiap kali elemen baharu ditambah atau dialih keluar daripadanya. Dalam kes timbunan min, elemen terkecil pergi ke akar tanpa mengira susunan sisipannya. Gilir keutamaan berdasarkan timbunan min ini, jadi jika kita mempunyai PriorityQueue integer, elemen pertamanya akan menjadi yang terkecil daripada nombor ini. Jika anda memadamkan akar, yang terkecil seterusnya menjadi akar.

Kaedah PriorityQueue Utama:

• boolean add(objek) memasukkan elemen yang ditentukan ke dalam baris gilir keutamaan. Kembali benar sekiranya berjaya. Jika baris gilir penuh, kaedah membuang pengecualian.
• tawaran boolean(objek) memasukkan elemen yang ditentukan ke dalam baris gilir keutamaan ini. Jika baris gilir penuh, kaedah mengembalikan palsu.
• boolean remove(object) mengalih keluar satu contoh elemen yang ditentukan daripada baris gilir ini, jika ia ada.
• Tinjauan objek() mengambil dan mengalih keluar kepala baris gilir ini. Mengembalikan batal jika baris gilir kosong.
• void clear() mengalih keluar semua elemen daripada baris gilir keutamaan.
• Elemen objek() mendapatkan semula kepala baris gilir ini tanpa mengalihkannya. Membuang NoSuchElementException jika baris gilir kosong.
• Object peek() mendapatkan semula kepala baris gilir tanpa mengalihkannya. Mengembalikan batal jika baris gilir kosong.
• boolean mengandungi(Objek o) mengembalikan benar jika baris gilir mengandungi elemen o.
• int size() mengembalikan bilangan elemen dalam baris gilir 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

Adalah penting untuk memahami bahawa baris gilir keutamaan adalah berdasarkan timbunan binari, jadi mereka tidak menyimpan elemen dalam susunan disusun linear. Setiap jalan dari akar ke daun disusun, tetapi cara yang berbeza dari akar tidak. Ini bermakna anda boleh mendapatkan elemen minimum baris gilir dengan cepat. Jika anda memadamkan kepala setiap kali, anda akan mencetak struktur yang diisih.

ArrayBlockingQueue

Struktur data dalaman ArrayBlockingQueueadalah berdasarkan tatasusunan bulat untuk menyimpan elemen. Ia ialah baris gilir biasa (FIFO) sekiranya elemen baharu dimasukkan pada ekor baris gilir, dan operasi pengekstrakan mengembalikan elemen daripada kepala baris gilir. Sebaik sahaja kapasiti baris gilir dibuat tidak boleh diubah. Percubaan untuk memasukkan (meletakkan) elemen ke dalam baris gilir penuh membawa kepada menyekat aliran; cuba mengambil elemen dari baris gilir kosong juga menyekat benang. Seperti yang kita katakan sebelum ini, tatasusunan ini adalah bulat. Ini bermakna elemen pertama dan terakhir tatasusunan dilayan secara logik bersebelahan. Baris memajukan indeks elemen kepala dan ekor setiap kali anda meletakkan elemen ke dalam baris gilir atau mengeluarkannya daripada baris gilir. Jika sesetengah indeks memajukan elemen terakhir tatasusunan, ia dimulakan semula dari 0. Oleh itu, baris gilir tidak perlu mengalihkan semua elemen sekiranya kepala dialih keluar (seperti dalam tatasusunan biasa). Walau bagaimanapun, dalam kes mengalih keluar elemen dari tengah (menggunakan Iterator.remove), elemen dialihkan. ArrayBlockingQueue menyokong dasar keadilan tambahan dengan parameter adil dalam pembina untuk memerintahkan kerja aliran menunggu pengeluar (memasukkan elemen) dan pengguna (mengekstrak elemen). Secara lalai, pesanan tidak dijamin. Walau bagaimanapun, jika baris gilir dibuat dengan "adil == benar", pelaksanaan kelas ArrayBlockingQueue menyediakan akses benang dalam susunan FIFO. Ekuiti biasanya mengurangkan lebar jalur, tetapi juga mengurangkan turun naik dan menghalang kehabisan sumber.

Pembina Kelas ArrayBlockingQueue

• ArrayBlockingQueue (kapasiti int) mencipta baris gilir kapasiti tetap dan dengan dasar akses lalai.
• ArrayBlockingQueue (kapasiti int, boolean fair) mencipta baris gilir dengan kapasiti tetap dan dasar akses tertentu.
• ArrayBlockingQueue (kapasiti int, boolean fair, Collection <? extends E> c) mencipta baris gilir dengan kapasiti tetap yang ditentukan oleh dasar akses dan termasuk elemen dalam baris gilir.

Di sini kita mempunyai contoh BlockingQueueExample. Kami mencipta baris gilir ArrayBlockingQueue dengan kapasiti satu elemen dan bendera yang adil. Dua utas dimulakan. Yang pertama daripada mereka, benang Pengeluar, menyusun baris gilir mesej daripada tatasusunan mesej menggunakan kaedah put. Yang kedua, Pengguna, benang membaca elemen daripada baris gilir menggunakan kaedah ambil dan memaparkannya dalam konsol. Susunan elemen adalah yang semula jadi untuk baris gilir.

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

Output adalah baris gilir dalam susunan semula jadi; dua elemen pertama muncul dengan kelewatan. Untuk mengukuhkan perkara yang anda pelajari, kami cadangkan anda menonton pelajaran video daripada Kursus Java kami

Kesimpulan

• Baris Gilir digunakan untuk memasukkan elemen pada penghujung baris gilir dan mengalih keluar dari permulaan baris gilir. Ia mengikut konsep FIFO.
• Java Queue ialah sebahagian daripada Rangka Kerja Koleksi dan melaksanakan antara muka Koleksi. Jadi ia menyokong semua kaedah antara muka Koleksi seperti sisipan, pemadaman dan sebagainya.
• Pelaksanaan Queue yang paling kerap digunakan ialah LinkedList, ArrayBlockingQueue dan PriorityQueue.
• Unsur-unsur baris gilir keutamaan disusun mengikut susunan semula jadinya, atau oleh Pembanding yang disediakan pada masa pembinaan baris gilir, bergantung pada pembina yang digunakan.
• Jika mana-mana operasi null dilakukan pada BlockingQueues, NullPointerException dilemparkan.