Liknande Queue är en linjär datastruktur som följer en viss ordning i vilken operationerna utförs för att lagra data. Ordern är First In First Out (FIFO) . Man kan föreställa sig en kö som en rad människor som väntar på att få något i sekventiell ordning som börjar från början av raden. Det är en ordnad lista där insättningar görs i ena änden som kallas baksidan och raderingar görs från den andra änden som kallas framsidan. Ett bra exempel på en kö är varje kö av konsumenter till en resurs där konsumenten som kom först serveras först.
Skillnaden mellan stackar och köer är att ta bort. I en stack tar vi bort objektet som senast lagts till; i en kö tar vi bort objektet som senast lagts till.
Ködatastruktur
Grundläggande åtgärder på kö:
- enqueue(): Infogar ett element i slutet av kön, dvs i den bakre änden. dequeue(): Denna operation tar bort och returnerar ett element som är längst fram i kön. front(): Denna operation returnerar elementet i fronten utan att ta bort det. rear(): Denna operation returnerar elementet i den bakre änden utan att ta bort det. isEmpty(): Denna operation indikerar om kön är tom eller inte. isFull(): Denna operation indikerar om kön är full eller inte. size(): Denna operation returnerar storleken på kön, dvs det totala antalet element som den innehåller.
Typer av köer:
- Enkel kö: Enkel kö, även känd som en linjär kö, är den mest grundläggande versionen av en kö. Här sker insättning av ett element, dvs. Enqueue-operationen, vid den bakre änden och borttagning av ett element, dvs. Dequeue-operationen sker i den främre änden. Problemet här är att om vi poppar något objekt framifrån och sedan bakåt når köns kapacitet och även om det finns tomma utrymmen före front betyder det att kön inte är full, men enligt villkoret i isFull()-funktionen, kommer det att visa att då är kön full. För att lösa detta problem använder vi cirkulär kö.
- Cirkulär kö : I en cirkulär kö fungerar köns element som en cirkulär ring. Arbetet med en cirkulär kö liknar den linjära kön förutom det faktum att det sista elementet är kopplat till det första elementet. Dess fördel är att minnet utnyttjas på ett bättre sätt. Detta beror på att om det finns ett tomt utrymme, dvs om inget element finns på en viss position i kön, kan ett element enkelt läggas till på den positionen med hjälp av modulo-kapacitet( %n ).
- Prioriterad kö : Denna kö är en speciell typ av kö. Dess specialitet är att den ordnar elementen i en kö baserat på någon prioritet. Prioriteten kan vara något där elementet med det högsta värdet har prioritet så det skapar en kö med minskande värdeordning. Prioriteten kan också vara sådan att elementet med lägst värde får högst prioritet så det skapar i sin tur en kö med ökande värdeordning. I fördefinierad prioritetskö prioriterar C++ det högsta värdet medan Java prioriterar det lägsta värdet.
- Följaktligen : Dequeue är också känd som Double Ended Queue. Som namnet antyder dubbla ändar betyder det att ett element kan infogas eller tas bort från båda ändarna av kön, till skillnad från de andra köerna där det bara kan göras från ena änden. På grund av den här egenskapen kanske den inte följer First In First Out-egendomen.
Tillämpningar av kö:
Kö används när saker inte behöver bearbetas omedelbart, utan måste bearbetas in F först jag n F först O ut ordning som Utöka första sökningen . Denna egenskap hos Queue gör den också användbar i följande typer av scenarier.
- När en resurs delas mellan flera konsumenter. Exempel inkluderar CPU-schemaläggning, Disk Scheduling. När data överförs asynkront (data tas inte nödvändigtvis emot i samma takt som de skickas) mellan två processer. Exempel inkluderar IO-buffertar, rör, fil-IO, etc. Kö kan användas som en väsentlig komponent i olika andra datastrukturer.
Arrayimplementering av kö:
För att implementera kö måste vi hålla reda på två index, fram och bak. Vi köar ett föremål på baksidan och ställer i kö ett föremål framifrån. Om vi helt enkelt ökar främre och bakre index kan det uppstå problem, fronten kan nå slutet av arrayen. Lösningen på detta problem är att öka fram och bak på ett cirkulärt sätt.
Steg för kö:
- Kontrollera att kön är full eller inte
- Om den är full, skriv över och avsluta
- Om kön inte är full, öka svansen och lägg till elementet
Steg för avköning:
- Kontrollera att kön är tom eller inte
- om det är tomt, skriv ut underflöde och avsluta
- om det inte är tomt, skriv ut elementet vid huvudet och inkrementhuvudet
Nedan finns ett program för att implementera ovanstående operation i kö
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ö->storlek = 0;> >// This is important, see the enqueue> >queue->bak = 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->storlek == kö->kapacitet);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->storlek == 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->bak = (kö->bak + 1)> >% queue->kapacitet;> >queue->array[queue->rear] = objekt;> >queue->storlek = kö->storlek + 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->storlek = kö->storlek - 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[queue->rear];> }> // 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ö->storlek = 0;> >// This is important, see the enqueue> >queue->bak = 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->storlek == kö->kapacitet);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->storlek == 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->bak = (kö->bak + 1)> >% queue->kapacitet;> >queue->array[queue->rear] = objekt;> >queue->storlek = kö->storlek + 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->storlek = kö->storlek - 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[queue->rear];> }> // 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> |
>
full form
>
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();> >}> }> }> |
>
>
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>
Komplexitetsanalys:
- Tidskomplexitet
| Operationer | Komplexitet |
|---|---|
| Enqueue(insättning) | O(1) |
| Deque (radering) | O(1) |
| Fram (Få fram) | O(1) |
| Rear (Get Rear) | O(1) |
| IsFull (Kontrollkön är full eller inte) | O(1) |
| IsEmpty (Kontrollkön är tom eller inte) | O(1) |
- Hjälputrymme:
O(N) där N är storleken på arrayen för att lagra element.
Fördelar med Array-implementering:
- Lätt att implementera.
- En stor mängd data kan hanteras effektivt med lätthet.
- Operationer som infogning och radering kan utföras med lätthet eftersom den följer först in först ut-regeln.
Nackdelar med Array-implementering:
- Statisk datastruktur, fast storlek.
- Om kön har ett stort antal kö- och avköoperationer kan vi vid något tillfälle (vid linjär ökning av främre och bakre index) inte kunna infoga element i kön även om kön är tom (detta problem undviks genom att använda cirkulär kö).
- Maximal storlek på en kö måste definieras tidigare.