I lighed med Queue er en lineær datastruktur, der følger en bestemt rækkefølge, hvori operationerne udføres til lagring af data. Ordren er First In First Out (FIFO) . Man kan forestille sig en kø som en række mennesker, der venter på at modtage noget i sekventiel rækkefølge, som starter fra begyndelsen af linjen. Det er en ordnet liste, hvor indsættelser udføres i den ene ende, som er kendt som bagsiden, og sletninger udføres fra den anden ende kendt som forsiden. Et godt eksempel på en kø er enhver kø af forbrugere til en ressource, hvor den forbruger, der kom først, bliver serveret først.
Forskellen mellem stakke og køer er i at fjerne. I en stak fjerner vi det element, der er tilføjet senest; i en kø fjerner vi det element, der er tilføjet mindst for nylig.
Kødatastruktur
Grundlæggende handlinger på kø:
- enqueue(): Indsætter et element i slutningen af køen, dvs. i bagenden. dequeue(): Denne operation fjerner og returnerer et element, der er forrest i køen. front(): Denne operation returnerer elementet i frontenden uden at fjerne det. rear(): Denne operation returnerer elementet i bagenden uden at fjerne det. isEmpty(): Denne operation angiver, om køen er tom eller ej. isFull(): Denne handling angiver, om køen er fuld eller ej. size(): Denne operation returnerer størrelsen af køen, dvs. det samlede antal elementer, den indeholder.
Typer af køer:
- Simpel kø: Simpel kø, også kendt som en lineær kø, er den mest grundlæggende version af en kø. Her sker indsættelse af et element, dvs. Enqueue-operationen, i den bageste ende og fjernelse af et element, dvs. Dequeue-operationen finder sted i den forreste ende. Her er problemet, at hvis vi popper noget element forfra og derefter bagfra når køens kapacitet, og selvom der er tomme pladser før fronten betyder det, at køen ikke er fuld, men ifølge betingelsen i isFull()-funktionen, vil det vise, at så er køen fuld. For at løse dette problem bruger vi cirkulær kø.
- Cirkulær kø : I en cirkulær kø fungerer køens element som en cirkulær ring. Funktionen af en cirkulær kø ligner den lineære kø, bortset fra det faktum, at det sidste element er forbundet med det første element. Dens fordel er, at hukommelsen udnyttes på en bedre måde. Dette skyldes, at hvis der er et tomt rum, dvs. hvis intet element er til stede på en bestemt position i køen, så kan et element nemt tilføjes på den position ved hjælp af modulo-kapacitet( %n ).
- Prioritetskø : Denne kø er en speciel type kø. Dens speciale er, at den arrangerer elementerne i en kø baseret på en eller anden prioritet. Prioriteten kan være noget, hvor elementet med den højeste værdi har prioritet, så det skaber en kø med faldende rækkefølge af værdier. Prioriteten kan også være sådan, at elementet med den laveste værdi får den højeste prioritet, så det igen skaber en kø med stigende rækkefølge af værdier. I foruddefineret prioritetskø prioriterer C++ højeste værdi, mens Java prioriterer laveste værdi.
- Derfor : Dequeue er også kendt som Double Ended Queue. Som navnet antyder dobbelt ende, betyder det, at et element kan indsættes eller fjernes fra begge ender af køen, i modsætning til de andre køer, hvor det kun kan gøres fra den ene ende. På grund af denne ejendom adlyder den muligvis ikke First In First Out-ejendommen.
Anvendelser af kø:
Kø bruges, når ting ikke skal behandles med det samme, men skal behandles ind F først jeg n F først O ud orden gerne Breadth First Search . Denne egenskab ved Queue gør den også nyttig i følgende slags scenarier.
- Når en ressource deles mellem flere forbrugere. Eksempler inkluderer CPU-planlægning, Disk-planlægning. Når data overføres asynkront (data modtages ikke nødvendigvis med samme hastighed som sendt) mellem to processer. Eksempler inkluderer IO-buffere, rør, fil-IO osv. Kø kan bruges som en væsentlig komponent i forskellige andre datastrukturer.
Array implementering af kø:
For at implementere kø skal vi holde styr på to indekser, foran og bagpå. Vi stiller en vare i kø bagpå og stiller en vare i kø forfra. Hvis vi blot øger front- og bagindekser, så kan der være problemer, fronten kan nå slutningen af arrayet. Løsningen på dette problem er at øge front og bag på cirkulær måde.
Trin til kø:
- Tjek, at køen er fuld eller ej
- Hvis fuld, udskriv overløb og afslut
- Hvis køen ikke er fuld, skal du øge hale og tilføje elementet
Trin til udskydelse af kø:
- Tjek, at køen er tom eller ej
- hvis tom, udskriv underløb og afslut
- hvis den ikke er tom, udskriv element ved hovedet og trinhovedet
Nedenfor er et program til at implementere ovenstående operation i kø
C++
for sløjfe i c
// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->kapacitet = kapacitet;> >queue->front = kø->størrelse = 0;> >// This is important, see the enqueue> >queue->bag = kapacitet - 1;> >queue->array =>new> int>[queue->kapacitet];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->størrelse == kø->kapacitet);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->størrelse == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->bag = (kø->bag + 1)> >% queue->kapacitet;> >queue->array[kø->bagside] = vare;> >queue->størrelse = kø->størrelse + 1;> >cout << item <<>' enqueued to queue
'>;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->array[kø->front];> >queue->front = (kø->front + 1)> >% queue->kapacitet;> >queue->størrelse = kø->størrelse - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[kø->front];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[kø->bagside];> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>' dequeued from queue
'>;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra> |
>
>
C
// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->kapacitet = kapacitet;> >queue->front = kø->størrelse = 0;> >// This is important, see the enqueue> >queue->bag = kapacitet - 1;> >queue->array = (>int>*)>malloc>(> >queue->kapacitet *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->størrelse == kø->kapacitet);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->størrelse == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->bag = (kø->bag + 1)> >% queue->kapacitet;> >queue->array[kø->bagside] = vare;> >queue->størrelse = kø->størrelse + 1;> >printf>(>'%d enqueued to queue
'>, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->array[kø->front];> >queue->front = (kø->front + 1)> >% queue->kapacitet;> >queue->størrelse = kø->størrelse - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[kø->front];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[kø->bagside];> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>'%d dequeued from queue
'>,> >dequeue(queue));> >printf>(>'Front item is %d
'>, front(queue));> >printf>(>'Rear item is %d
'>, rear(queue));> >return> 0;> }> |
>
>
Java
// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>' dequeued from queue
'>);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani> |
>
>
Python3
# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()> |
>
>
C#
// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }> |
>
streng til int konverter
>
Javascript
> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> > |
>
>Produktion
10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>
Kompleksitetsanalyse:
- Tidskompleksitet
| Operationer | Kompleksitet |
|---|---|
| Enqueue (indsættelse) | O(1) |
| Deque (sletning) | O(1) |
| Foran (Gå foran) | O(1) |
| Rear (Get Rear) | O(1) |
| IsFull (Kontrollér, at køen er fuld eller ej) | O(1) |
| IsEmpty (Tjek, at køen er tom eller ej) | O(1) |
- Hjælpeplads:
O(N) hvor N er størrelsen af arrayet til lagring af elementer.
Fordele ved Array-implementering:
- Let at implementere.
- En stor mængde data kan administreres effektivt med lethed.
- Operationer såsom indsættelse og sletning kan udføres med lethed, da den følger først ind først ud-reglen.
Ulemper ved Array-implementering:
- Statisk datastruktur, fast størrelse.
- Hvis køen har et stort antal kø- og dekø-operationer, vil vi på et tidspunkt (i tilfælde af lineær stigning af for- og bagindekser) muligvis ikke være i stand til at indsætte elementer i køen, selvom køen er tom (dette problem undgås ved at bruge cirkulær kø).
- Maksimal størrelse af en kø skal defineres forud.