Ing kene kita bakal ngrembug antarmuka Java Queue. Sampeyan bakal ngerti apa struktur data Antrian , carane diwakili ing Jawa, cara apa sing paling penting kanggo kabeh antrian. Uga, apa implementasine Queue ing basa Jawa. Sawise iku, kita nliti implementasine sing paling penting lan sinau kanthi conto.
Struktur data antrian
Antrian minangka struktur data abstrak linier kanthi urutan operasi tartamtu - First In First Out (FIFO). Tegese sampeyan bisa nambah unsur (utawa enqueue, sijine ing antrian) mung ing mburi struktur, lan njupuk unsur (dequeue utawa mbusak saka antrian) mung saka awal. Sampeyan bisa mbayangno struktur data Antrian kanthi gampang. Iku misale jek kaya antrian utawa baris pelanggan ing urip nyata. Pelanggan sing teka luwih dhisik, uga bakal dilayani luwih dhisik. Yen sampeyan duwe wong papat ing antrian ing McDonalds utawa ing papan liya, sing pertama baris dadi sing pertama entuk toko. Yen pelanggan anyar teka, dheweke bakal dadi nomer 5 kanggo entuk hamburger. Dadi, nalika nggarap antrian, unsur anyar ditambahake ing pungkasan, lan yen sampeyan pengin entuk unsur, bakal dijupuk saka wiwitan. Iki minangka prinsip utama karya struktur data antrian klasik.
Antri ing Jawa
Antrian ing Jawa minangka antarmuka. Miturut dokumentasi Oracle, antarmuka Antrian duwe 2 superinterface, 4 antarmuka sing beda-beda sing diturunake saka antrian, lan dhaptar kelas sing apik banget.
Iki artine apa? Kaping pisanan, Java Queue minangka bagean saka Framework Koleksi lan ngetrapake antarmuka Koleksi. Dadi ndhukung kabeh cara antarmuka Koleksi kayata sisipan, pambusakan lan liya-liyane. Antrian ngetrapake antarmuka Iterable, sing ngidini obyek dadi target pernyataan "kanggo-saben daur ulang".
Metode Antrian Jawa
Antrian ngumumake sawetara cara. Minangka cara antarmuka kudu diwakili ing kabeh kelas sing ngleksanakake Antrian. Metode Antrian sing paling penting, Jawa:
tawaran Boolean () - nglebokake unsur anyar menyang antrian yen bisa
Tambah Boolean (E e) - nglebokake unsur anyar menyang antrian yen bisa. Ngasilake bener yen sukses lan mbuwang IllegalStateException yen ora ana spasi.
Obyek jajak pendapat () - retrieves lan mbusak unsur saka sirah saka. Ngasilake null yen antrian kosong.
Obyek mbusak () - retrieves lan mbusak unsur saka sirah antrian.
Ndeleng obyek () - retrieves, nanging ora mbusak unsur saka sirah antrian. Ngasilake null yen antrian kosong.
unsur obyek () - retrieves, nanging ora mbusak unsur saka sirah antrian.
Subinterfaces saka antrian Jawa
Antarmuka antrian diwarisake dening 4 subinterfaces – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Sampeyan bisa dibagi dadi 3 klompok: Deques, Blocking Queues lan Transfer Queues karo BlockingDeque duweke loro pisanan. Ayo padha njupuk sak klebatan ing grup iki.
Deques
Deque tegese D ouble- E nded Q ue lan ndhukung tambahan utawa mbusak saka salah siji buntut data minangka antrian (first-in-first-out/FIFO) utawa saka sirah minangka struktur data populer liyane sing disebut stack (last - in- pisanan metu / LIFO). Kelas sing ngetrapake Antarmuka Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.
Pamblokiran Antrian
Antrian pamblokiran yaiku antrian sing mblokir thread ing rong kasus:
thread nyoba kanggo njaluk unsur saka antrian kosong
thread nyoba kanggo nyelehake unsur ing antrian lengkap
Nalika thread nyoba njupuk item saka antrian kosong, iku ngenteni nganti sawetara thread liyane nempatno item menyang antrian. Kajaba iku, nalika utas nyoba nglebokake unsur ing antrian lengkap, bakal ngenteni nganti sawetara utas liyane njupuk unsur kasebut saka antrian kanggo entuk ruang bebas kanggo unsur kasebut. Mesthi, konsep "antrean lengkap" nuduhake yen antrian nduweni ukuran winates, sing biasane ditemtokake ing konstruktor. Antrian Pamblokiran standar kalebu LinkedBlockingQueue, SynchronousQueue, lan ArrayBlockingQueue. Ngleksanakake kelas antarmuka BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlokingDequepunika subinterface kanggo BlockingQueue. BlockingDeque kayata BlockingQueue minangka antrian pamblokiran, nanging loro arah. Dadi warisan properti saka antarmuka Deque. Iki orientasi kanggo eksekusi multi-Utas, ora ngidini unsur nol lan kapasitas bisa diwatesi. Implementasi saka antarmuka BlockingDeque mblokir operasi njupuk unsur yen antrian kosong, lan nambah unsur menyang antrian yen kebak.
Transfer Antrian
Antarmuka TransferQueue ngluwihi antarmuka BlockingQueue. Nanging ora kaya implementasine antrian antarmuka BlockingQueue, ing ngendi benang bisa diblokir yen antrian kosong (maca), utawa yen antrian kebak (nulis), antrian antarmuka TransferQueue ngalangi stream nulis nganti stream liyane njupuk unsur kasebut. Gunakake cara transfer kanggo iki. Ing tembung liyane, implementasine saka BlockingQueue njamin yen unsur digawe dening Produser kudu ing antrian, nalika implementasine saka TransferQueue njamin yen unsur Produser "ditampa" dening Konsumen. Mung ana siji implementasi Java resmi antarmuka TransferQueue - LinkedTransferQueue.
Implementasine antrian Jawa
Ana akeh kelas sing ngetrapake antarmuka Antrian:
AbstractQueue miturut Queue Java 8 docs, kelas abstrak iki nyedhiyakake implementasi dhasar saka sawetara operasi Queue. Ora ngidini unsur null. Ana 3 cara liyane nambah, mbusak, lan unsur adhedhasar Queue tawaran klasik , jajak pendapat , lan Ndeleng , mungguh. Nanging padha mbuwang pengecualian tinimbang nuduhake kegagalan liwat bali palsu utawa null.
ArrayBlockingQueue - antrian pamblokiran FIFO ukuran tetep sing didhukung dening array
ArrayDeque - implementasine array resizable saka antarmuka Deque
ConcurrentLinkedDeque - deque concurrent tanpa wates adhedhasar node sing disambung.
ConcurrentLinkedQueue - antrian aman thread tanpa wates adhedhasar simpul sing disambung.
DelayQueue - antrian jadwal adhedhasar wektu sing didhukung dening tumpukan
LinkedBlockingDeque - implementasine bebarengan saka antarmuka Deque.
LinkedBlockingQueue - antrian pamblokiran FIFO sing diwatesi kanthi opsional sing didhukung dening kelenjar sing disambung
LinkedList - implementasi dhaptar kaping pindho saka antarmuka List lan Deque. Ngleksanakake kabeh operasi dhaptar opsional, lan ngidini kabeh unsur (kalebu null)
LinkedTransferQueue - TransferQueue tanpa wates adhedhasar simpul sing disambung
PriorityBlockingQueue - antrian prioritas pamblokiran tanpa wates sing didhukung dening tumpukan
PriorityQueue - antrian prioritas adhedhasar struktur data tumpukan
SynchronousQueue - antrian pamblokiran ing ngendi saben operasi insert kudu ngenteni operasi mbusak sing cocog karo benang liyane, lan kosok balene.
Implementasi paling populer yaiku LinkedList, ArrayBlockingQueue lan PriorityQueue. Ayo padha ndeleng lan nindakake sawetara conto kanggo pemahaman sing luwih apik.
LinkedList
Kelas LinkedList ing Jawa ngleksanakake antarmuka List lan Deque. Dadi, iku kombinasi List lan Deque, antrian loro-lorone, sing ndhukung nambah lan mbusak unsur saka loro-lorone. Ing Jawa LinkedList wis dobel-linked List: saben unsur List nelpon Node lan ngemot obyek lan referensi kanggo loro obyek tetanggan - sadurunge lan sabanjuré. Sampeyan bisa uga ujar manawa LinkedList ora efektif banget babagan panggunaan memori. Iku bener, nanging struktur data iki bisa migunani ing kasus insert lan mbusak kinerja operasi. Nanging mung kedadeyan yen sampeyan nggunakake iterator kanggo wong-wong mau (ing kasus iki kedadeyan ing wektu sing tetep). Operasi akses miturut indeks ditindakake kanthi nggoleki saka wiwitan pungkasan (sing luwih cedhak) menyang unsur sing dikarepake. Nanging, aja lali babagan biaya tambahan kanggo nyimpen referensi ing antarane unsur. Dadi, LinkedList minangka implementasi antrian sing paling populer ing Jawa. Iku uga implementasine saka List lan Deque lan ngidini kita nggawe antrian bidirectional dumadi saka sembarang obyek kalebu null. LinkedList minangka kumpulan unsur.
LinkedList () tanpa paramèter digunakake kanggo mbangun dhaftar kosong. LinkedList(Koleksi<? ngluwihi E> c) kanggo nggawe dhaptar sing ngemot unsur-unsur koleksi kasebut, supaya bisa dibalekake dening iterator koleksi.
Metode LinkedList Utama:
nambah (E unsur) Appends unsur kasebut kanggo mburi dhaftar iki;
nambah (int indeks, E unsur) Nglebokake unsur ing indeks posisi kasebut;
njaluk (int indeks) Ngasilake unsur ing posisi kasebut ing dhaftar iki;
mbusak (indeks int) Mbusak unsur sing ana ing indeks posisi;
mbusak (Obyek o) Mbusak kedadeyan pisanan saka ?o unsur saka dhaftar iki yen ana.
mbusak () Nompo lan mbusak unsur pisanan dhaftar.
addFirst (), addLast () nambah unsur ing wiwitan / pungkasan dhaftar
cetha () mbusak kabeh unsur saka dhaftar
ngandhut (Obyek o) ngasilake bener yen dhaptar ngemot unsur o.
indexOf (Obyek o) ngasilake indeks kedadeyan pisanan saka unsur o, utawa -1 yen ora ana ing dhaptar.
set (int index, E unsur) ngganti unsur ing posisi indeks karo unsur
size () Ngasilake jumlah unsur ing dhaftar.
toArray () ngasilake array sing ngemot kabeh unsur dhaptar saka pisanan nganti unsur pungkasan.
pop () sing njedhul unsur saka tumpukan (diwakili dening dhaptar)
push (E e) sing nyurung unsur menyang tumpukan (diwakili dening dhaptar iki)
Tuladha Antrian Jawa - LinkedList (nglebokake lan mbusak unsur kanthi cara sing beda)
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 ora persis antrian ing FIFO makna umum. Unsur antrian prioritas diurutake miturut urutan alam, utawa dening Comparator sing diwenehake ing wektu konstruksi antrian, gumantung saka konstruktor sing digunakake. Nanging iku ora urutan kaya bisa ing struktur linear kayata dhaftar (saka paling gedhe kanggo cilik utawa kosok balene). Antrian prioritas adhedhasar tumpukan min prioritas. Heap minangka struktur data adhedhasar wit binar. Prioritas saben wong tuwa luwih gedhe tinimbang prioritas anak-anake. Wit diarani binar lengkap yen saben wong tuwa ora duwe anak luwih saka loro, lan ngisi tingkat saka ndhuwur nganti ngisor (saka tingkat sing padha - saka kiwa menyang tengen). Binary heap reorganises dhewe saben wektu unsur anyar ditambahake utawa dibusak saka iku. Ing cilik saka min-numpuk, unsur paling cilik menyang ROOT preduli saka urutan sisipan sawijining. Prioritas antrian adhedhasar min-tumpukan iki, supaya yen kita duwe PriorityQueue saka wilangan bulat, unsur pisanan bakal dadi paling cilik saka nomer iki. Yen sampeyan mbusak oyod, sing paling cilik sabanjure dadi oyod.
Metode PriorityQueue Utama:
boolean add(obyek) nglebokake unsur kasebut menyang antrian prioritas. Ngasilake bener ing kasus sukses. Yen antrian kebak, cara mbalang pangecualian.
tawaran boolean (obyek) nglebokake unsur kasebut menyang antrian prioritas iki. Yen antrian kebak, cara ngasilake palsu.
boolean mbusak (obyek) mbusak conto siji saka unsur kasebut saka antrian iki, yen ana.
Obyek jajak pendapat () retrieves lan mbusak sirah antrian iki. Ngasilake null yen antrian kosong.
void clear () mbusak kabeh unsur saka antrian prioritas.
Unsur obyek () njupuk kepala antrian iki tanpa njabut. Mbuwang NoSuchElementException yen antrian kosong.
Ndeleng obyek () retrieves sirah antrian tanpa njabut. Ngasilake null yen antrian kosong.
boolean ngemot (Obyek o) ngasilake bener yen antrian ngemot unsur o.
int size () ngasilake nomer unsur ing antrian iki.
Tuladha 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 kanggo mangerteni yen antrian prioritas adhedhasar tumpukan binar, supaya ora nyimpen unsur ing urutan sing diurutake kanthi linier. Saben cara saka oyod menyang rwaning diurutake, nanging cara sing beda saka oyod ora. Tegese sampeyan bisa entuk unsur minimal saka antrian kanthi cepet. Yen sampeyan mbusak sirah saben wektu, sampeyan bakal nyithak struktur sing diurutake.
ArrayBlockingQueue
Struktur data internal ArrayBlockingQueueadhedhasar array bunder kanggo nyimpen unsur. Iku antrian khas (FIFO) yen unsur anyar dilebokake ing buntut antrian, lan operasi extraction bali unsur saka kepala antrian. Sawise digawe kapasitas antrian ora bisa diganti. Nyoba kanggo nglebokake (nglebokake) unsur menyang antrian lengkap mimpin kanggo mblokir aliran; nyoba njupuk unsur saka antrian kosong uga mblokir thread. Kaya sing wis dingerteni sadurunge, array iki bunder. Iki tegese unsur pisanan lan pungkasan saka array dianggep logis jejer. Antrian maju indeks saka unsur sirah lan buntut saben-saben sampeyan sijine unsur menyang antrian utawa mbusak saka antrian. Yen sawetara indeks maju unsur pungkasan saka array, iku bakal miwiti maneh saka 0. Mula, antrian ora kudu ngalih kabeh unsur ing cilik saka sirah njabut (minangka ing Uploaded biasanipun). Nanging, ing cilik saka njabut unsur saka tengah (nggunakake Iterator.remove), unsur sing pindah. ArrayBlockingQueue ndhukung kabijakan keadilan tambahan kanthi parameter sing adil ing konstruktor supaya bisa kerja ngenteni aliran produser (nyisipake unsur) lan konsumen (ekstrak unsur). Kanthi gawan, pesenan ora dijamin. Nanging yen antrian digawe karo "adil == bener", implementasine saka kelas ArrayBlockingQueue menehi akses thread ing urutan FIFO. Ekuitas biasane nyuda bandwidth, nanging uga nyuda volatilitas lan nyegah sumber daya.
ArrayBlockingQueue Kelas konstruktor
ArrayBlockingQueue (kapasitas int) nggawe antrian kapasitas tetep lan karo kabijakan akses standar.
ArrayBlockingQueue (kapasitas int, boolean fair) nggawe antrian kanthi kapasitas tetep lan kebijakan akses sing ditemtokake.
ArrayBlockingQueue (kapasitas int, boolean adil, Koleksi <? ngluwihi E> c) nggawe antrian karo kapasitas tetep ditemtokake dening kabijakan akses lan kalebu unsur ing antrian.
Ing kene kita entuk conto BlockingQueueExample. Kita nggawe antrian ArrayBlockingQueue kanthi kapasitas siji unsur lan gendera sing adil. Loro benang diwiwiti. Sing pertama, Utas Produser, antri pesen saka larik pesen nggunakake metode put. Sing nomer loro, Konsumen, thread maca unsur saka antrian nggunakake metode njupuk lan nampilake ing console. Urutan unsur iku alam kanggo antrian.
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 punika antrian ing urutan alam; loro unsur pisanan katon karo wektu tundha. Kanggo nguatake apa sing sampeyan sinau, disaranake sampeyan nonton video pelajaran saka Kursus Jawa
Kesimpulan
Antrian digunakake kanggo nglebokake unsur ing mburi antrian lan mbusak saka wiwitan antrian. Iku nderek konsep FIFO.
Java Queue minangka bagéan saka Framework Koleksi lan ngleksanakake antarmuka Koleksi. Dadi ndhukung kabeh cara antarmuka Koleksi kayata sisipan, pambusakan lan liya-liyane.
Implementasi Queue sing paling kerep digunakake yaiku LinkedList, ArrayBlockingQueue lan PriorityQueue.
Unsur antrian prioritas diurutake miturut urutan alam, utawa dening Comparator sing diwenehake ing wektu konstruksi antrian, gumantung saka konstruktor sing digunakake.
Yen operasi null ditindakake ing BlockingQueues, NullPointerException dibuwang.
Dadi, nalika nggarap antrian, unsur anyar ditambahake ing pungkasan, lan yen sampeyan pengin entuk unsur, bakal dijupuk saka wiwitan. Iki minangka prinsip utama karya struktur data antrian klasik.
Sampeyan bisa uga ujar manawa LinkedList ora efektif banget babagan panggunaan memori. Iku bener, nanging struktur data iki bisa migunani ing kasus insert lan mbusak kinerja operasi. Nanging mung kedadeyan yen sampeyan nggunakake iterator kanggo wong-wong mau (ing kasus iki kedadeyan ing wektu sing tetep). Operasi akses miturut indeks ditindakake kanthi nggoleki saka wiwitan pungkasan (sing luwih cedhak) menyang unsur sing dikarepake. Nanging, aja lali babagan biaya tambahan kanggo nyimpen referensi ing antarane unsur. Dadi, LinkedList minangka implementasi antrian sing paling populer ing Jawa. Iku uga implementasine saka List lan Deque lan ngidini kita nggawe antrian bidirectional dumadi saka sembarang obyek kalebu null. LinkedList minangka kumpulan unsur.
GO TO FULL VERSION