Java Queue Interface at mga pagpapatupad nito

Dito natin tatalakayin ang interface ng Java Queue. Malalaman mo kung ano ang istraktura ng data ng Queue , kung paano ito kinakatawan sa Java, kung anong mga pamamaraan ang pinakamahalaga para sa lahat ng mga pila. Gayundin, kung anong mga pagpapatupad ng Queue ang nasa wikang Java. Pagkatapos nito, susuriin namin ang pinakamahalagang pagpapatupad at matutunan ang mga ito gamit ang mga halimbawa.

Istraktura ng data ng pila

Ang Queue ay isang linear abstract data structure na may partikular na pagkakasunud-sunod ng pagsasagawa ng mga operasyon — First In First Out (FIFO). Nangangahulugan iyon na maaari kang magdagdag ng isang elemento (o enqueue, ilagay sa queue) lamang sa dulo ng istraktura, at kumuha ng isang elemento (dequeue o alisin mula sa queue) lamang mula sa simula nito. Maaari mong isipin ang istraktura ng data ng Queue nang napakadali. Tila isang pila o linya ng mga customer sa totoong buhay. Ang customer na nauna, ay mauna ring ihain. Kung mayroon kang apat na tao sa linya sa McDonalds o sa ibang lugar, ang unang pumila ay ang unang makakakuha ng tindahan. Kung darating ang bagong customer, siya ang ika-5 sa linya para makakuha ng mga hamburger. Kaya, habang nagtatrabaho sa isang queue, ang mga bagong elemento ay idinagdag sa dulo, at kung nais mong makakuha ng isang elemento, ito ay kukunin mula sa simula. Ito ang pangunahing prinsipyo ng klasikal na queue data structure work.

Pila sa Java

Ang queue sa Java ay isang interface. Ayon sa dokumentasyon ng Oracle, ang interface ng Queue ay may 2 superinterface, 4 na magkakaibang interface na nagmana mula sa queue, at isang napaka-kahanga-hangang listahan ng mga klase. Ano ang ibig sabihin nito? Una sa lahat, ang Java Queue ay bahagi ng Collection Framework at nagpapatupad ng interface ng Collection. Kaya sinusuportahan nito ang lahat ng paraan ng interface ng Collection tulad ng pagpasok, pagtanggal at iba pa. Ang Queue ay nagpapatupad ng Iterable na interface, na nagpapahintulot sa isang object na maging target ng "for-each loop" na pahayag.

Mga Paraan ng Queue Java

Ang Queue ay nagpapahayag ng isang bilang ng mga pamamaraan. Bilang mga pamamaraan ng interface, dapat silang kinakatawan sa lahat ng mga klase na nagpapatupad ng Queue. Ang pinakamahalagang Paraan ng Queue, Java:

• Boolean offer() – naglalagay ng bagong elemento sa queue kung posible
• Boolean add(E e) – naglalagay ng bagong elemento sa queue kung posible. Nagbabalik ng true kung sakaling magtagumpay at magtapon ng IllegalStateException kung walang espasyo.
• Object poll() – kinukuha at inaalis ang isang elemento mula sa ulo ng. Nagbabalik ng null kung walang laman ang pila.
• Object remove() – kinukuha at inaalis ang isang elemento mula sa ulo ng pila.
• Object peek() – kinukuha, ngunit hindi nag-aalis ng elemento sa ulo ng pila. Nagbabalik ng null kung walang laman ang pila.
• Object element() – kinukuha, ngunit hindi nag-aalis ng elemento sa ulo ng pila.

Mga subinterface ng Java Queue

Ang interface ng Queue ay minana ng 4 na subinterface – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Maaari mong hatiin ang mga ito sa 3 grupo: Deques, Blocking Queues at Transfer Queues na may BlockingDeque na una sa dalawa. Tingnan natin ang mga grupong ito.

Deques

Ang ibig sabihin ng Deque ay D ouble- E nded Q ueue at sumusuporta sa pagdaragdag o pag-alis mula sa alinmang buntot ng data bilang isang queue (first-in-first-out/FIFO) o mula sa head bilang isa pang sikat na istruktura ng data na tinatawag na stack (last - in- first-out/LIFO). Mga klase na nagpapatupad ng Deque Interface: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Pag-block ng Mga Pila

Ang blocking queue ay isang queue na humaharang sa isang thread sa dalawang kaso:

• Sinusubukan ng thread na kumuha ng mga elemento mula sa isang walang laman na pila
• Sinusubukan ng thread na ilagay ang mga elemento sa buong pila

Kapag sinubukan ng isang thread na kumuha ng mga item mula sa isang walang laman na queue, naghihintay ito hanggang sa ilagay ng ibang thread ang mga item sa queue. Katulad nito, kapag sinubukan ng isang thread na ilagay ang mga elemento sa isang buong queue, naghihintay ito hanggang sa alisin ng ibang thread ang mga elemento mula sa pila upang makakuha ng libreng espasyo para sa mga elemento. Oo naman, ang konsepto ng "buong pila" ay nagpapahiwatig na ang pila ay may limitadong laki, na karaniwang tinutukoy sa tagabuo. Kasama sa Mga Karaniwang Blocking Queue ang LinkedBlockingQueue, SynchronousQueue, at ArrayBlockingQueue. Pagpapatupad ng mga klase ng interface ng BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeay isang subinterface para sa BlockingQueue. Ang BlockingDeque tulad ng BlockingQueue ay isang blocking queue, ngunit bidirectional. Kaya namamana nito ang mga katangian ng interface ng Deque. Ito ay nakatuon sa multi-threaded execution, hindi pinapayagan ang mga zero na elemento at maaaring limitado ang kapasidad. Ang mga pagpapatupad ng interface ng BlockingDeque ay humaharang sa pagpapatakbo ng pagkuha ng mga elemento kung ang pila ay walang laman, at pagdaragdag ng isang elemento sa pila kung ito ay puno na.

Mga Transfer Queue

Ang interface ng TransferQueue ay nagpapalawak ng interface ng BlockingQueue. Gayunpaman, hindi tulad ng pagpapatupad ng BlockingQueue interface queues, kung saan ang mga thread ay maaaring i-block kung ang queue ay walang laman (pagbabasa), o kung ang queue ay puno (pagsulat), ang TransferQueue interface queues ay hinaharangan ang write stream hanggang sa isa pang stream ang makuha ang elemento. Gumamit ng paraan ng paglipat para dito. Sa madaling salita, ginagarantiyahan ng pagpapatupad ng BlockingQueue na ang elementong ginawa ng Producer ay dapat nasa queue, habang ang pagpapatupad ng TransferQueue ay ginagarantiyahan na ang Producer element ay "natatanggap" ng Consumer. Mayroon lamang isang opisyal na pagpapatupad ng Java ng interface ng TransferQueue — LinkedTransferQueue.

Mga Pagpapatupad ng Java Queue

Mayroong maraming mga klase na nagpapatupad ng Queue interface:

• AbstractQueue ayon sa Queue Java 8 docs, ang abstract class na ito ay nagbibigay ng mga pangunahing pagpapatupad ng ilang operasyon ng Queue. Hindi nito pinapayagan ang mga null na elemento. May 3 pang paraan ng pagdaragdag, pag-alis, at elemento batay sa Queue classical na alok , poll , at silip , ayon sa pagkakabanggit. Gayunpaman, nagtatapon sila ng mga pagbubukod sa halip na magpahiwatig ng pagkabigo sa pamamagitan ng false o null returns.
• ArrayBlockingQueue — isang nakapirming laki ng FIFO blocking queue na sinusuportahan ng isang array
• ArrayDeque — resizable array na pagpapatupad ng Deque interface
• ConcurrentLinkedDeque — isang unbounded concurrent deque batay sa mga naka-link na node.
• ConcurrentLinkedQueue — isang walang hangganang thread-safe queue batay sa mga naka-link na node.
• DelayQueue — isang nakabatay sa oras na pag-iskedyul ng pila na sinusuportahan ng isang heap
• LinkedBlockingDeque — ang kasabay na pagpapatupad ng interface ng Deque.
• LinkedBlockingQueue — isang opsyonal na hangganan ng FIFO blocking queue na sinusuportahan ng mga naka-link na node
• LinkedList — dobleng naka-link na pagpapatupad ng listahan ng mga interface ng Listahan at Deque. Ipinapatupad ang lahat ng opsyonal na pagpapatakbo ng listahan, at pinahihintulutan ang lahat ng elemento (kabilang ang null)
• LinkedTransferQueue — isang walang hangganang TransferQueue batay sa mga naka-link na node
• PriorityBlockingQueue — isang unbounded blocking priority queue na sinusuportahan ng isang heap
• PriorityQueue — isang priority queue batay sa istraktura ng heap data
• SynchronousQueue — isang blocking queue kung saan ang bawat insert na operasyon ay dapat maghintay para sa kaukulang pag-alis ng operasyon ng isa pang thread, at kabaliktaran.

Ang pinakasikat na mga pagpapatupad ay ang LinkedList, ArrayBlockingQueue at PriorityQueue. Tingnan natin ang mga ito at gumawa ng ilang halimbawa para sa mas mahusay na pag-unawa.

LinkedList

Ang Class LinkedList sa Java ay nagpapatupad ng mga interface ng List at Deque. Kaya, ito ay isang kumbinasyon ng List at Deque, isang two-way na pila, na sumusuporta sa pagdaragdag at pag-alis ng mga elemento mula sa magkabilang panig. Sa Java LinkedList ay doble-link na Listahan: ang bawat elemento ng Listahan ay tumatawag sa Node at naglalaman ng isang bagay at mga sanggunian sa dalawang magkalapit na bagay — ang nauna at ang susunod. Maaari mong sabihin na ang LinkList ay hindi masyadong epektibo sa mga tuntunin ng paggamit ng memorya. Totoo iyon, ngunit ang istraktura ng data na ito ay maaaring maging kapaki-pakinabang sa kaso ng pagpasok at pagtanggal ng pagganap ng mga operasyon. Gayunpaman, nangyayari lamang ito kung gumagamit ka ng mga iterator para sa kanila (sa kasong ito, nangyayari ito sa patuloy na oras). Ang mga operasyon sa pag-access sa pamamagitan ng index ay isinasagawa sa pamamagitan ng paghahanap mula sa simula ng dulo (alinman ang mas malapit) sa nais na elemento. Gayunpaman, huwag kalimutan ang tungkol sa mga karagdagang gastos para sa pag-iimbak ng mga sanggunian sa pagitan ng mga elemento. Kaya, ang LinkList ay ang pinakasikat na pagpapatupad ng queue sa Java. Ito ay isang pagpapatupad din ng List at Deque at ito ay nagpapahintulot sa amin na lumikha ng isang bidirectional queue na binubuo ng anumang mga bagay kabilang ang null. Ang LinkList ay isang koleksyon ng mga elemento.

LinkedList Constructors

Ang LinkList() na walang mga parameter ay ginagamit upang bumuo ng isang walang laman na listahan. Ang LinkedList(Collection<? extends E> c) ay para sa paglikha ng isang listahan na naglalaman ng mga elemento ng tinukoy na koleksyon, sa pagkakasunud-sunod, ang mga ito ay ibinalik ng iterator ng koleksyon.

Pangunahing Mga Paraan ng LinkedList:

• add(E element) Idinaragdag ang tinukoy na elemento sa dulo ng listahang ito;
• add(int index, E element) Ipinapasok ang elemento sa tinukoy na index ng posisyon;
• get(int index) Ibinabalik ang elemento sa tinukoy na posisyon sa listahang ito;
• remove(int index) Tinatanggal ang elemento na nasa position index;
• remove(Object o) Tinatanggal ang unang paglitaw ng ?o element mula sa listahang ito kung naroon ito.
• remove() Kinukuha at inaalis ang unang elemento ng listahan.
• addFirst(), addLast() magdagdag ng elemento sa simula/wakas ng isang listahan
• Ang clear() ay nag-aalis ng lahat ng elemento mula sa listahan
• contains(Object o) returns true kung ang listahan ay naglalaman ng o element.
• Ibinabalik ng indexOf(Object o) ang index ng unang paglitaw ng elementong o, o -1 kung wala ito sa listahan.
• pinapalitan ng set(int index, E element) ang elemento sa posisyon ng index ng elemento
• size()Ibinabalik ang dami ng mga elemento sa listahan.
• toArray() ay nagbabalik ng array na naglalaman ng lahat ng mga elemento ng listahan mula una hanggang sa huling elemento.
• pop() na nagpa-pop ng isang elemento mula sa stack (kinakatawan ng listahan)
• push(E e) na nagtutulak ng elemento papunta sa stack (kinakatawan ng listahang ito)

Halimbawa ng Java Queue — LinkedList (paglalagay at pag-alis ng mga elemento sa iba't ibang paraan)

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

Ang PriorityQueue ay hindi eksakto ang queue sa pangkalahatang kahulugan ng FIFO. Ang mga elemento ng priyoridad na pila ay inayos ayon sa kanilang natural na pagkakasunud-sunod, o ng isang Comparator na ibinigay sa oras ng pagbuo ng pila, depende kung aling constructor ang ginagamit. Gayunpaman, hindi ito isang order na maaaring nasa linear na istraktura tulad ng listahan (mula sa pinakamalaki hanggang sa pinakamaliit o vice versa). Isang priority queue batay sa isang priority min heap. Ang Heap ay isang istraktura ng data batay sa binary tree. Ang priyoridad ng bawat magulang ay mas malaki kaysa sa mga priyoridad ng mga anak nito. Ang isang puno ay tinatawag na kumpletong binary kung ang bawat magulang ay may hindi hihigit sa dalawang anak, at ang pagpuno ng mga antas ay napupunta mula sa itaas hanggang sa ibaba (mula sa parehong antas - mula kaliwa hanggang kanan). Ang binary heap ay muling inaayos ang sarili nito sa tuwing may idaragdag o aalis na bagong elemento dito. Sa kaso ng min-heap, ang pinakamaliit na elemento ay napupunta sa ugat anuman ang pagkakasunud-sunod ng pagpasok nito. Priority queue batay sa min-heap na ito, kaya kung mayroon tayong PriorityQueue ng mga integer, ang unang elemento nito ang magiging pinakamaliit sa mga numerong ito. Kung tatanggalin mo ang ugat, ang susunod na pinakamaliit ay magiging ugat.

Pangunahing Mga Paraan ng PriorityQueue:

• Ang boolean add(object) ay naglalagay ng tinukoy na elemento sa priority queue. Nagbabalik ng totoo kung sakaling magtagumpay. Kung ang pila ay puno, ang pamamaraan ay naghagis ng isang pagbubukod.
• Inilalagay ng boolean offer(object) ang tinukoy na elemento sa priority queue na ito. Kung ang pila ay puno, ang pamamaraan ay nagbabalik ng mali.
• Ang boolean remove(object) ay nag-aalis ng isang instance ng tinukoy na elemento mula sa queue na ito, kung ito ay naroroon.
• Kinukuha at inaalis ng Object poll() ang ulo ng pila na ito. Nagbabalik ng null kung walang laman ang pila.
• inaalis ng void clear() ang lahat ng elemento mula sa priority queue.
• Kinukuha ng Object element() ang head ng queue na ito nang hindi ito inaalis. Itinapon ang NoSuchElementException kung walang laman ang pila.
• Kinukuha ng Object peek() ang ulo ng pila nang hindi ito inaalis. Nagbabalik ng null kung walang laman ang pila.
• Ang boolean contains(Object o) ay nagbabalik ng true kung ang queue ay naglalaman ng o element.
• int size() ay nagbabalik ng bilang ng mga elemento sa queue na ito.

Halimbawa ng 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

Mahalagang maunawaan na ang mga priyoridad na pila ay batay sa mga binary heap, kaya hindi nila pinapanatili ang mga elemento sa linear sorted order. Ang bawat paraan mula sa ugat hanggang sa dahon ay naayos, ngunit ang iba't ibang paraan mula sa ugat ay hindi. Nangangahulugan iyon na maaari mong makuha ang kaunting elemento ng pila nang napakabilis. Kung tatanggalin mo ang ulo sa bawat oras, magpi-print ka ng pinagsunod-sunod na istraktura.

ArrayBlockingQueue

Panloob na istraktura ng data ng ArrayBlockingQueueay batay sa isang pabilog na hanay upang mag-imbak ng mga elemento. Isa itong tipikal na pila (FIFO) kung sakaling may mga bagong elemento na ipinasok sa buntot ng pila, at ang mga operasyon ng pagkuha ay nagbabalik ng elemento mula sa ulo ng pila. Kapag nalikha ang kapasidad ng pila ay hindi na mababago. Ang mga pagtatangkang magpasok (maglagay) ng isang elemento sa isang buong pila ay humahantong sa pagharang sa daloy; ang sinusubukang kumuha ng elemento mula sa isang walang laman na pila ay humaharang din sa thread. Tulad ng sinabi namin dati, ang array na ito ay pabilog. Nangangahulugan iyon na ang una at huling mga elemento ng array ay lohikal na tinatrato na magkatabi. Inuusad ng pila ang mga indeks ng mga elemento ng ulo at buntot sa tuwing ilalagay mo ang elemento sa pila o aalisin ito sa pila. Kung ang ilang index ay nag-advance sa huling elemento ng array, ito ay magre-restart mula sa 0. Kaya, ang pila ay hindi kailangang ilipat ang lahat ng mga elemento kung sakaling maalis ang ulo (tulad ng karaniwang hanay). Gayunpaman, sa kaso ng pag-alis ng isang elemento mula sa gitna (gamit ang Iterator.remove), ang mga elemento ay inilipat. Sinusuportahan ng ArrayBlockingQueue ang isang karagdagang patakaran sa pagiging patas na may patas na parameter sa constructor upang i-order ang gawain ng mga daloy ng paghihintay ng mga producer (pagpasok ng mga elemento) at mga consumer (pag-extract ng mga elemento). Bilang default, hindi ginagarantiyahan ang order. Gayunpaman, kung ang queue ay ginawa gamit ang "patas == true", ang pagpapatupad ng klase ng ArrayBlockingQueue ay nagbibigay ng thread access sa FIFO order. Karaniwang binabawasan ng equity ang bandwidth, ngunit binabawasan din ang pagkasumpungin at pinipigilan ang pag-ubos ng mga mapagkukunan.

ArrayBlockingQueue Class сconstructors

• Ang ArrayBlockingQueue (int capacity) ay lumilikha ng isang queue ng fixed capacity at may default na patakaran sa pag-access.
• Ang ArrayBlockingQueue (int capacity, boolean fair) ay lumilikha ng isang queue na may nakapirming kapasidad at isang tinukoy na patakaran sa pag-access.
• Ang ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) ay lumilikha ng queue na may fixed capacity na tinukoy ng access policy at may kasamang mga elemento sa queue.

Narito mayroon kaming halimbawa ng BlockingQueueExample. Lumilikha kami ng isang pila ng ArrayBlockingQueue na may kapasidad ng isang elemento at isang patas na bandila. Dalawang thread ang nagsimula. Ang una sa kanila, ang thread ng Producer, ay nag-queue ng mga mensahe mula sa hanay ng mga mensahe gamit ang put method. Ang pangalawa, Consumer, ay nagbabasa ng mga elemento mula sa queue gamit ang paraan ng pagkuha at ipinapakita ang mga ito sa console. Ang pagkakasunud-sunod ng mga elemento ay ang natural para sa pila.

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

Ang output ay ang pila sa natural na pagkakasunud-sunod; lumilitaw ang unang dalawang elemento nang may pagkaantala. Upang palakasin ang iyong natutunan, iminumungkahi naming manood ka ng isang video lesson mula sa aming Java Course

Mga konklusyon

• Ang Queue ay ginagamit upang magpasok ng mga elemento sa dulo ng queue at mag-alis mula sa simula ng queue. Ito ay sumusunod sa konsepto ng FIFO.
• Ang Java Queue ay isang bahagi ng Collection Framework at nagpapatupad ng interface ng Collection. Kaya sinusuportahan nito ang lahat ng paraan ng interface ng Collection tulad ng pagpasok, pagtanggal at iba pa.
• Ang pinakamadalas na ginagamit na pagpapatupad ng Queue ay LinkedList, ArrayBlockingQueue at PriorityQueue.
• Ang mga elemento ng priyoridad na pila ay inayos ayon sa kanilang natural na pagkakasunud-sunod, o ng isang Comparator na ibinigay sa oras ng pagbuo ng pila, depende sa kung aling constructor ang ginagamit.
• Kung ang anumang null na operasyon ay isinasagawa sa BlockingQueues, ang NullPointerException ay itatapon.