I likhet med Queue er en lineær datastruktur som følger en bestemt rekkefølge som operasjonene utføres for å lagre data. Bestillingen er First In First Out (FIFO) . Man kan forestille seg en kø som en rekke mennesker som venter på å motta noe i sekvensiell rekkefølge som starter fra begynnelsen av linjen. Det er en ordnet liste der innsettinger gjøres i den ene enden som er kjent som baksiden og slettinger gjøres fra den andre enden kjent som fronten. Et godt eksempel på en kø er en hvilken som helst kø av forbrukere for en ressurs der forbrukeren som kom først blir servert først.
Forskjellen mellom stabler og køer er å fjerne. I en stabel fjerner vi elementet som sist ble lagt til; i en kø fjerner vi elementet som er minst nylig lagt til.
Kødatastruktur
Grunnleggende operasjoner på kø:
- enqueue(): Setter inn et element på slutten av køen, dvs. i bakenden. dequeue(): Denne operasjonen fjerner og returnerer et element som er i frontenden av køen. front(): Denne operasjonen returnerer elementet i frontenden uten å fjerne det. rear(): Denne operasjonen returnerer elementet i bakenden uten å fjerne det. isEmpty(): Denne operasjonen indikerer om køen er tom eller ikke. isFull(): Denne operasjonen indikerer om køen er full eller ikke. size(): Denne operasjonen returnerer størrelsen på køen, dvs. det totale antallet elementer den inneholder.
Typer køer:
- Enkel kø: Enkel kø, også kjent som en lineær kø, er den mest grunnleggende versjonen av en kø. Her skjer innsetting av et element, dvs. Enqueue-operasjonen, i bakenden og fjerning av et element, dvs. Dequeue-operasjonen finner sted i frontenden. Her er problemet at hvis vi spretter et element forfra og deretter bakfra når kapasiteten til køen, og selv om det er tomme plasser før fronten betyr at køen ikke er full, men i henhold til betingelsen i isFull()-funksjonen, vil den vise at da er køen full. For å løse dette problemet bruker vi sirkulær kø.
- Sirkulær kø : I en sirkulær kø fungerer elementet i køen som en sirkulær ring. Arbeidet til en sirkulær kø er lik den lineære køen bortsett fra at det siste elementet er koblet til det første elementet. Fordelen er at minnet utnyttes på en bedre måte. Dette er fordi hvis det er en tom plass, dvs. hvis det ikke er noe element til stede på en bestemt posisjon i køen, kan et element enkelt legges til på den posisjonen ved å bruke modulo-kapasitet ( %n ).
- Prioritetskø : Denne køen er en spesiell type kø. Dens spesialitet er at den arrangerer elementene i en kø basert på en eller annen prioritet. Prioriteten kan være noe der elementet med høyest verdi har prioritet slik at det skaper en kø med synkende rekkefølge av verdier. Prioriteten kan også være slik at elementet med lavest verdi får høyest prioritet slik at det i sin tur skaper en kø med økende rekkefølge av verdier. I forhåndsdefinert prioritetskø, gir C++ prioritet til høyeste verdi, mens Java prioriterer laveste verdi.
- Tilsvarende : Dequeue er også kjent som Double Ended Queue. Som navnet antyder, betyr det at et element kan settes inn eller fjernes fra begge ender av køen, i motsetning til de andre køene der det bare kan gjøres fra den ene enden. På grunn av denne egenskapen, kan den ikke adlyde First In First Out-egenskapen.
Applikasjoner av kø:
Kø brukes når ting ikke må behandles umiddelbart, men må behandles inn F først Jeg n F først O ut bestille som Bredde først søk . Denne egenskapen til Queue gjør den også nyttig i følgende scenarier.
- Når en ressurs deles mellom flere forbrukere. Eksempler inkluderer CPU-planlegging, Diskplanlegging. Når data overføres asynkront (data mottas ikke nødvendigvis med samme hastighet som sendt) mellom to prosesser. Eksempler inkluderer IO-buffere, rør, fil-IO, etc. Kø kan brukes som en essensiell komponent i forskjellige andre datastrukturer.
Matriseimplementering av kø:
For å implementere kø, må vi holde styr på to indekser, foran og bak. Vi setter en gjenstand i kø bak og setter en gjenstand i kø fra forsiden. Hvis vi bare øker fremre og bakre indekser, kan det være problemer, fronten kan nå slutten av matrisen. Løsningen på dette problemet er å øke foran og bak på en sirkulær måte.
Trinn for kø:
- Sjekk at køen er full eller ikke
- Hvis den er full, skriv ut og avslutt
- Hvis køen ikke er full, øker du tail og legger til elementet
Trinn for å sette ut kø:
- Sjekk at køen er tom eller ikke
- hvis tom, skriv ut underflyt og avslutt
- hvis den ikke er tom, skriv ut elementet ved hodet og inkrementeringshodet
Nedenfor er et program for å implementere operasjonen ovenfor på kø
C++
tcp ip-modell
// 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->kapasitet = kapasitet;> >queue->front = kø->størrelse = 0;> >// This is important, see the enqueue> >queue->bak = kapasitet - 1;> >queue->array =>new> int>[queue->kapasitet];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->størrelse == kø->kapasitet);> }> // 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->bak = (kø->bak + 1)> >% queue->kapasitet;> >queue->array[kø->bak] = element;> >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ø->foran];> >queue->front = (kø->front + 1)> >% queue->kapasitet;> >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ø->foran];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[kø->bak];> }> // 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->kapasitet = kapasitet;> >queue->front = kø->størrelse = 0;> >// This is important, see the enqueue> >queue->bak = kapasitet - 1;> >queue->array = (>int>*)>malloc>(> >queue->kapasitet *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->størrelse == kø->kapasitet);> }> // 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->bak = (kø->bak + 1)> >% queue->kapasitet;> >queue->array[kø->bak] = element;> >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ø->foran];> >queue->front = (kø->front + 1)> >% queue->kapasitet;> >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ø->foran];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[kø->bak];> }> // 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();> >}> }> }> |
>
lateks tekststørrelser
>
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> > |
>
>Produksjon
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
| Drift | Kompleksitet |
|---|---|
| Enqueue (innsetting) | O(1) |
| Deque (sletting) | O(1) |
| Foran (Få foran) | O(1) |
| Bak (Få bak) | O(1) |
| IsFull (Sjekkkøen er full eller ikke) | O(1) |
| IsEmpty (Sjekkkøen er tom eller ikke) | O(1) |
- Hjelpeplass:
O(N) hvor N er størrelsen på matrisen for lagring av elementer.
Fordeler med Array-implementering:
- Enkel å implementere.
- En stor mengde data kan enkelt administreres effektivt.
- Operasjoner som innsetting og sletting kan utføres med letthet da den følger først inn først ut-regelen.
Ulemper med Array-implementering:
- Statisk datastruktur, fast størrelse.
- Hvis køen har et stort antall kø- og dekøoperasjoner, kan det hende at vi på et tidspunkt (i tilfelle lineær økning av fremre og bakre indekser) ikke kan sette inn elementer i køen selv om køen er tom (dette problemet unngås ved å bruke sirkulær kø).
- Maksimal størrelse på en kø må være definert på forhånd.