En kø er en anden form for lineær datastruktur, der bruges til at gemme elementer ligesom enhver anden datastruktur, men på en bestemt måde. Med enkle ord kan vi sige, at køen er en type datastruktur i programmeringssproget Java, der gemmer elementer af samme slags. Komponenterne i en kø er gemt i en FIFO-adfærd (First In, First Out). Der er to ender i køsamlingen, dvs. foran og bag. Køen har to ender, der er foran og bagpå.
Følgende figur beskriver perfekt FIFO-egenskaben (First In, First Out) i Java-køen.
Som forklaret i det foregående billede kan vi se, at køen er en lineær datastruktur med to terminaler, dvs. start (foran) og slut (bagerst). Komponenter tilføjes inde i køen fra den bagerste ende af køen, og komponenterne udtrækkes fra den forreste ende af køen.
Køen er en grænseflade i Java der hører til Java.util-pakken. Det udvider også samlingsgrænsefladen.
Den generiske repræsentation af Java Queue-grænsefladen er vist nedenfor:
public interface Queue extends Collection
Som vi har diskuteret ovenfor, at køen er en grænseflade, kan vi derfor også sige, at køen ikke kan instansieres, fordi grænseflader ikke kan instantieres. Hvis en bruger ønsker at implementere funktionaliteten af Queue-grænsefladen i Java, så er det obligatorisk at have nogle solide klasser, der implementerer Queue-grænsefladen.
numrene i alfabetet
I Java-programmeringssprog er der to forskellige klasser, som bruges til at implementere Queue-grænsefladen. Disse klasser er:
Karakteristika for Java-køen
Java-køen kan betragtes som en af de vigtigste datastrukturer i programmeringsverdenen. Java Queue er attraktiv på grund af dens egenskaber. De væsentlige egenskaber ved Java Queue-datastrukturen er givet som følger:
- Java Queue adlyder FIFO-måden (First In, First Out). Det indikerer, at elementer er indtastet i køen til sidst og elimineret forfra.
- Java Queue-grænsefladen giver alle regler og processer for samlingsgrænsefladen som inklusion, sletning osv.
- Der er to forskellige klasser, der bruges til at implementere Queue-grænsefladen. Disse klasser er LinkedList og PriorityQueue.
- Ud over disse to er der en klasse, dvs. Array Blocking Queue, der bruges til at implementere Queue-grænsefladen.
- Der er to typer køer, ubegrænsede køer og afgrænsede køer. Køerne, der er en del af java.util-pakken, er kendt som ubundne køer, og afgrænsede køer er de køer, der er til stede i java.util.concurrent-pakken.
- Deque eller (dobbelt-endet kø) er også en type kø, der bærer inklusion og sletning af elementer fra begge ender.
- Dequet anses også for trådsikkert.
- Blokeringskøer er også en af de typer køer, der også er trådsikre. Blokeringskøerne bruges til at implementere producent-forbruger-forespørgslerne.
- Blokeringskøer understøtter ikke null-elementer. I blokeringskøer, hvis noget arbejde, der ligner nul-værdier, prøves, kastes NullPointerException også.
Implementering af kø
Klasser brugt til implementering af kø
Klasserne, der bruges til at implementere køens funktionaliteter, er givet som følger:
Grænseflader brugt til implementering af kø
Java-grænsefladerne bruges også i implementeringen af Java-køen. De grænseflader, der bruges til at implementere køens funktionaliteter, er angivet som følger:
- Om hvad
- Blokeringskø
- Blokerende Deque
Java-kø-klassemetoder
I Java-køen er der mange metoder, der bruges meget almindeligt. Køgrænsefladen fremmer forskellige metoder som indsæt, slet, kig osv. Nogle af operationerne i Java-køen giver anledning til en undtagelse, mens nogle af disse operationer returnerer en bestemt værdi, når programmet er afsluttet.
Bemærk - I Java SE 8 er der ikke foretaget ændringer i Java-køsamlingen. Disse metoder, som er defineret under, er yderligere forberedt i de efterfølgende versioner af programmeringssproget Java. For eksempel Java SE 9.
Forskellige metoder til Java Queue er defineret nedenfor:
| Metode | Metode prototype | Beskrivelse |
|---|---|---|
| tilføje | boolesk tilføjelse(E e) | Tilføjer element e til køen i slutningen (halen) af køen uden at overtræde begrænsningerne på kapaciteten. Returnerer sand hvis succes eller IllegalStateException hvis kapaciteten er opbrugt. |
| kig | E kig() | Returnerer hovedet (forrest) af køen uden at fjerne det. |
| element | E element() | Udfører samme handling som peek ()-metoden. Kaster NoSuchElementException, når køen er tom. |
| fjerne | E fjern() | Fjerner hovedet af køen og returnerer det. Kaster NoSuchElementException, hvis køen er tom. |
| afstemning | E afstemning() | Fjerner hovedet af køen og returnerer det. Hvis køen er tom, returnerer den null. |
| Tilbud | boolesk tilbud(E e) | Indsæt det nye element e i køen uden at overtræde kapacitetsbegrænsningerne. |
| størrelse | int størrelse() | Returnerer størrelsen eller antallet af elementer i køen. |
Java Queue Array Implementering
Køimplementering er ikke så ligetil som en stakimplementering.
For at implementere kø ved hjælp af Arrays, erklærer vi først et array, der indeholder n antal elementer.
Derefter definerer vi følgende operationer, der skal udføres i denne kø.
1) Kø: En operation for at indsætte et element i køen er Enqueue (funktionskø Enqueue i programmet). For at indsætte et element i bagenden skal vi først kontrollere, om køen er fuld. Hvis den er fuld, kan vi ikke indsætte elementet. Hvis bagved 2) Hale: Operationen for at slette et element fra køen er Dequeue (funktionskø Dequeue i programmet). Først tjekker vi, om køen er tom. For at dekødrift skal fungere, skal der være mindst ét element i køen. 3) Foran: Denne metode returnerer forsiden af køen. 4) Display: Denne metode krydser køen og viser elementerne i køen. Følgende Java-program demonstrerer implementeringen af Queue. QueueArrayImplementation.java Da vi har implementeret Queue-datastrukturen ved hjælp af Arrays i ovenstående program, kan vi også implementere Queue ved hjælp af Linked List. Vi vil implementere de samme metoder i kø, dekø, foran og visning i dette program. Forskellen er, at vi vil bruge Linked List-datastrukturen i stedet for Array. Nedenstående program demonstrerer Linked List-implementeringen af Queue i Java. QueueLLImplementation.java Produktion: 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 af 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