En kø er en annen type lineær datastruktur som brukes til å lagre elementer akkurat som enhver annen datastruktur, men på en bestemt måte. Med enkle ord kan vi si at køen er en type datastruktur i programmeringsspråket Java som lagrer elementer av samme type. Komponentene i en kø er lagret i en FIFO-atferd (først inn, først ut). Det er to ender i køsamlingen, dvs. foran og bak. Køen har to ender som er foran og bak.
Følgende figur beskriver perfekt FIFO-egenskapen (First In, First Out) til Java-køen.
Som forklart i det foregående bildet, kan vi se at køen er en lineær datastruktur med to terminaler, dvs. start (foran) og slutt (bak). Komponenter legges til inne i køen fra den bakre enden av køen og komponentene trekkes ut fra den fremre enden av køen.
Køen er et grensesnitt i Java som tilhører Java.util-pakken. Det utvider også samlingsgrensesnittet.
Den generiske representasjonen av Java Queue-grensesnittet er vist nedenfor:
public interface Queue extends Collection
Som vi har diskutert ovenfor at køen er et grensesnitt, kan vi derfor også si at køen ikke kan instansieres fordi grensesnitt ikke kan instansieres. Hvis en bruker ønsker å implementere funksjonaliteten til Queue-grensesnittet i Java, er det obligatorisk å ha noen solide klasser som implementerer Queue-grensesnittet.
tallene i alfabetet
I programmeringsspråket Java er det to forskjellige klasser som brukes til å implementere Queue-grensesnittet. Disse klassene er:
Kjennetegn ved Java-køen
Java-køen kan betraktes som en av de viktigste datastrukturene i programmeringsverdenen. Java Queue er attraktiv på grunn av egenskapene. De betydelige egenskapene til Java Queue-datastrukturen er gitt som følger:
- Java Queue følger FIFO-måten (først inn, først ut). Det indikerer at elementer legges inn i køen på slutten og elimineres fra forsiden.
- Java Queue-grensesnittet gir alle reglene og prosessene til samlingsgrensesnittet som inkludering, sletting, etc.
- Det er to forskjellige klasser som brukes til å implementere Queue-grensesnittet. Disse klassene er LinkedList og PriorityQueue.
- Annet enn disse to, er det en klasse som er Array Blocking Queue som brukes til å implementere Queue-grensesnittet.
- Det er to typer køer, Ubegrensede køer og Begrensede køer. Køene som er en del av java.util-pakken er kjent som Unbounded-køene og avgrensede køer er køene som er tilstede i java.util.concurrent-pakken.
- Deque eller (dobbeltende kø) er også en type kø som inneholder inkludering og sletting av elementer fra begge ender.
- Dekken anses også som trådsikker.
- Blokkeringskøer er også en av typene køer som også er trådsikre. Blokkeringskøene brukes til å implementere produsent-forbruker-spørringene.
- Blokkeringskøer støtter ikke null-elementer. I blokkeringskøer, hvis noe arbeid som ligner på null-verdier blir prøvd, blir NullPointerException også kastet.
Implementering av kø
Klasser brukt i implementering av kø
Klassene som brukes til å implementere funksjonaliteten til køen er gitt som følger:
Grensesnitt brukt i implementering av kø
Java-grensesnittene brukes også i implementeringen av Java-køen. Grensesnittene som brukes til å implementere funksjonaliteten til køen er gitt som følger:
- Om hva
- Blokkeringskø
- Blokkerende Deque
Klassemetoder for Java Queue
I Java-køen er det mange metoder som brukes veldig ofte. Kø-grensesnittet fremmer forskjellige metoder som å sette inn, slette, kikke osv. Noen av operasjonene i Java-køen gir et unntak, mens noen av disse operasjonene returnerer en bestemt verdi når programmet er fullført.
Merk - I Java SE 8 er det ingen endringer gjort i Java-køsamlingen. Disse metodene som er definert under er videre utarbeidet i de etterfølgende versjonene av programmeringsspråket Java. For eksempel Java SE 9.
Ulike metoder for Java Queue er definert nedenfor:
Metode | Metode Prototype | Beskrivelse |
---|---|---|
Legg til | boolsk add(E e) | Legger til element e i køen på slutten (halen) av køen uten å bryte kapasitetsbegrensningene. Returnerer true if success eller IllegalStateException hvis kapasiteten er oppbrukt. |
titt | E kikk() | Returnerer hodet (foran) av køen uten å fjerne det. |
element | E element() | Utfører samme operasjon som kikkmetoden (). Kaster NoSuchElementException når køen er tom. |
fjerne | E fjern() | Fjerner lederen av køen og returnerer den. Kaster NoSuchElementException hvis køen er tom. |
avstemming | E avstemning() | Fjerner lederen av køen og returnerer den. Hvis køen er tom, returnerer den null. |
By på | boolsk tilbud(E e) | Sett inn det nye elementet e i køen uten å bryte kapasitetsbegrensninger. |
størrelse | int størrelse() | Returnerer størrelsen eller antallet elementer i køen. |
Java Queue Array Implementering
Køimplementering er ikke like enkelt som en stackimplementering.
For å implementere kø ved å bruke Arrays, erklærer vi først en matrise som inneholder n antall elementer.
Deretter definerer vi følgende operasjoner som skal utføres i denne køen.
1) Kø: En operasjon for å sette inn et element i køen er Enqueue (funksjonskø Enqueue i programmet). For å sette inn et element i bakenden må vi først sjekke om køen er full. Hvis det er fullt, kan vi ikke sette inn elementet. Hvis bak 2) Hale: Operasjonen for å slette et element fra køen er Dequeue (funksjonskø Dequeue i programmet). Først sjekker vi om køen er tom. For at kødrift skal fungere, må det være minst ett element i køen. 3) Foran: Denne metoden returnerer forsiden av køen. 4) Skjerm: Denne metoden går gjennom køen og viser elementene i køen. Følgende Java-program demonstrerer implementeringen av Queue. QueueArrayImplementation.java Ettersom vi har implementert Queue-datastrukturen ved å bruke Arrays i programmet ovenfor, kan vi også implementere Queue ved å bruke Linked List. Vi vil implementere de samme metodene enqueue, dequeue, front og display i dette programmet. Forskjellen er at vi vil bruke Linked List-datastrukturen i stedet for Array. Programmet nedenfor demonstrerer Linked List-implementeringen av Queue i Java. QueueLLImplementation.java Produksjon: Java-køprogram
class Queue { private static int front, rear, capacity; private static int queue[]; Queue(int size) { front = rear = 0; capacity = size; queue = new int[capacity]; } // insert an element into the queue static void queueEnqueue(int item) { // check if the queue is full if (capacity == rear) { System.out.printf('
Queue is full
'); return; } // insert element at the rear else { queue[rear] = item; rear++; } return; } //remove an element from the queue static void queueDequeue() { // check if queue is empty if (front == rear) { System.out.printf('
Queue is empty
'); return; } // shift elements to the right by one place uptil rear else { for (int i = 0; i <rear 0 4 - 1; i++) { queue[i]="queue[i" + 1]; } set queue[rear] to if (rear < capacity) decrement rear rear--; return; print queue elements static void queuedisplay() int i; (front="=" rear) system.out.printf('queue is empty
'); traverse front and for (i="front;" i rear; system.out.printf(' %d , ', queue[i]); of queuefront() system.out.printf('
front element the queue: %d', queue[front]); public class queuearrayimplementation main(string[] args) create a capacity q="new" queue(4); system.out.println('initial queue:'); q.queuedisplay(); inserting in q.queueenqueue(10); q.queueenqueue(30); q.queueenqueue(50); q.queueenqueue(70); system.out.println('queue after enqueue operation:'); q.queuefront(); insert q.queueenqueue(90); q.queuedequeue(); system.out.printf('
queue two dequeue operations:'); pre> <p> <strong>Output:</strong> </p> <pre> Initial Queue: Queue is Empty Queue after Enqueue Operation: 10 , 30 , 50 , 70 , Front Element of the queue: 10 Queue is full 10 , 30 , 50 , 70 , Queue after two dequeue operations: 50 , 70 , Front Element of the queue: 50 </pre> <h2>Java Queue Linked List Implementation</h2> <p>As we have implemented the Queue data structure using Arrays in the above program, we can also implement the Queue using Linked List.</p> <p>We will implement the same methods enqueue, dequeue, front, and display in this program. The difference is that we will be using the Linked List data structure instead of Array.</p> <p>The below program demonstrates the Linked List implementation of Queue in Java.</p> <p> <strong>QueueLLImplementation.java</strong> </p> <pre> class LinkedListQueue { private Node front, rear; private int queueSize; // queue size //linked list node private class Node { int data; Node next; } //default constructor - initially front & rear are null; size=0; queue is empty public LinkedListQueue() { front = null; rear = null; queueSize = 0; } //check if the queue is empty public boolean isEmpty() { return (queueSize == 0); } //Remove item from the front of the queue. public int dequeue() { int data = front.data; front = front.next; if (isEmpty()) { rear = null; } queueSize--; System.out.println('Element ' + data+ ' removed from the queue'); return data; } //Add data at the rear of the queue. public void enqueue(int data) { Node oldRear = rear; rear = new Node(); rear.data = data; rear.next = null; if (isEmpty()) { front = rear; } else { oldRear.next = rear; } queueSize++; System.out.println('Element ' + data+ ' added to the queue'); } //print front and rear of the queue public void print_frontRear() { System.out.println('Front of the queue:' + front.data + ' Rear of the queue:' + rear.data); } } class QueueLLImplementation{ public static void main(String a[]){ LinkedListQueue queue = new LinkedListQueue(); queue.enqueue(6); queue.enqueue(3); queue.print_frontRear(); queue.enqueue(12); queue.enqueue(24); queue.dequeue(); queue.dequeue(); queue.enqueue(9); queue.print_frontRear(); } } </pre> <p> <strong>Output:</strong> </p> <pre> Element 6 added to the queue Element 3 added to the queue Front of the queue:6 Rear of the queue:3 Element 12 added to the queue Element 24 added to the queue Element 6 removed from the queue Element 3 removed from the queue Element 9 added to the queue Front of the queue:12 Rear of the queue:9 </pre> <hr></rear>
Implementering av Java Queue Linked List
class LinkedListQueue { private Node front, rear; private int queueSize; // queue size //linked list node private class Node { int data; Node next; } //default constructor - initially front & rear are null; size=0; queue is empty public LinkedListQueue() { front = null; rear = null; queueSize = 0; } //check if the queue is empty public boolean isEmpty() { return (queueSize == 0); } //Remove item from the front of the queue. public int dequeue() { int data = front.data; front = front.next; if (isEmpty()) { rear = null; } queueSize--; System.out.println('Element ' + data+ ' removed from the queue'); return data; } //Add data at the rear of the queue. public void enqueue(int data) { Node oldRear = rear; rear = new Node(); rear.data = data; rear.next = null; if (isEmpty()) { front = rear; } else { oldRear.next = rear; } queueSize++; System.out.println('Element ' + data+ ' added to the queue'); } //print front and rear of the queue public void print_frontRear() { System.out.println('Front of the queue:' + front.data + ' Rear of the queue:' + rear.data); } } class QueueLLImplementation{ public static void main(String a[]){ LinkedListQueue queue = new LinkedListQueue(); queue.enqueue(6); queue.enqueue(3); queue.print_frontRear(); queue.enqueue(12); queue.enqueue(24); queue.dequeue(); queue.dequeue(); queue.enqueue(9); queue.print_frontRear(); } }
Element 6 added to the queue Element 3 added to the queue Front of the queue:6 Rear of the queue:3 Element 12 added to the queue Element 24 added to the queue Element 6 removed from the queue Element 3 removed from the queue Element 9 added to the queue Front of the queue:12 Rear of the queue:9