Podobno kot čakalna vrsta je linearna podatkovna struktura, ki sledi določenemu vrstnemu redu, v katerem se izvajajo operacije za shranjevanje podatkov. Vrstni red je Prvi prisoten, prvi ven (FIFO) . Čakalno vrsto si lahko predstavljamo kot vrsto ljudi, ki čakajo na nekaj v zaporednem vrstnem redu, ki se začne od začetka vrste. To je urejen seznam, v katerem se vstavki izvajajo na enem koncu, ki je znan kot zadnji del, in brisanja na drugem koncu, imenovanem sprednji. Dober primer čakalne vrste je katera koli čakalna vrsta porabnikov za vir, kjer je porabnik, ki je bil prvi, postrežen prvi.
Razlika med skladi in čakalnimi vrstami je v odstranjevanju. V skladu odstranimo element, ki je bil nazadnje dodan; v čakalni vrsti odstranimo element, ki je bil nazadnje dodan.
Struktura podatkov čakalne vrste
Osnovne operacije v čakalni vrsti:
- enqueue(): Vstavi element na konec čakalne vrste, tj. na zadnji konec. dequeue(): Ta operacija odstrani in vrne element, ki je na sprednjem koncu čakalne vrste. front(): Ta operacija vrne element na sprednji strani, ne da bi ga odstranila. rear(): ta operacija vrne element na zadnji strani, ne da bi ga odstranil. isEmpty(): Ta operacija označuje, ali je čakalna vrsta prazna ali ne. isFull(): Ta operacija kaže, ali je čakalna vrsta polna ali ne. size(): ta operacija vrne velikost čakalne vrste, tj. skupno število elementov, ki jih vsebuje.
Vrste čakalnih vrst:
- Preprosta čakalna vrsta: Preprosta čakalna vrsta, znana tudi kot linearna čakalna vrsta, je najbolj osnovna različica čakalne vrste. Tu se vstavljanje elementa, tj. operacija Enqueue, izvede na zadnjem delu, odstranitev elementa, tj. Operacija dequeue, pa na sprednjem koncu. Tu je težava v tem, da če izstrelimo nek element od spredaj in nato od zadaj dosežemo kapaciteto čakalne vrste in čeprav so pred sprednjo stranjo prazni prostori, to pomeni, da čakalna vrsta ni polna, vendar bo po pogoju v funkciji isFull() prikazano, da potem je čakalna vrsta polna. Za rešitev tega problema uporabljamo krožno čakalno vrsto.
- Krožna čakalna vrsta : V krožni čakalni vrsti element čakalne vrste deluje kot krožni obroč. Delovanje krožne čakalne vrste je podobno linearni čakalni vrsti, razen dejstva, da je zadnji element povezan s prvim elementom. Njegova prednost je, da je pomnilnik bolje izkoriščen. To je zato, ker če je prazen prostor, tj. če na določenem mestu v čakalni vrsti ni prisotnega nobenega elementa, je mogoče element enostavno dodati na to mesto z uporabo modulo zmogljivosti ( %n ).
- Prednostna čakalna vrsta : Ta čakalna vrsta je posebna vrsta čakalne vrste. Njegova posebnost je v tem, da razvršča elemente v čakalno vrsto na podlagi neke prioritete. Prednost je lahko nekaj, pri čemer ima element z najvišjo vrednostjo prednost, tako da ustvari čakalno vrsto z padajočim vrstnim redom vrednosti. Prioriteta je lahko tudi taka, da element z najnižjo vrednostjo dobi najvišjo prednost, tako da ustvari čakalno vrsto z naraščajočim vrstnim redom vrednosti. V vnaprej določeni prednostni čakalni vrsti daje C++ prednost najvišji vrednosti, medtem ko ima Java prednost najnižji vrednosti.
- Skladno s tem : Dequeue je znan tudi kot Double Ended Queue. Kot že ime pove dvojno končano, to pomeni, da je mogoče element vstaviti ali odstraniti z obeh koncev čakalne vrste, za razliko od drugih čakalnih vrst, v katerih je to mogoče storiti samo z enega konca. Zaradi te lastnosti morda ne bo upošteval lastnosti First In First Out.
Aplikacije čakalne vrste:
Čakalna vrsta se uporablja, ko stvari ni treba takoj obdelati, ampak jih je treba obdelati F najprej jaz n F najprej O ut naročilo všeč Najprej iskanje v širino . Zaradi te lastnosti čakalne vrste je uporabna tudi v naslednjih vrstah scenarijev.
- Ko je vir v skupni rabi med več potrošniki. Primeri vključujejo razporejanje procesorja, razporejanje diska. Ko se podatki prenašajo asinhrono (podatki niso nujno prejeti z enako hitrostjo kot poslani) med dvema procesoma. Primeri vključujejo medpomnilnike IO, cevi, IO datoteke itd. Čakalno vrsto je mogoče uporabiti kot bistveno komponento v različnih drugih podatkovnih strukturah.
Izvedba matrike čakalne vrste:
Za izvedbo čakalne vrste moramo slediti dvema indeksoma, sprednjemu in zadnjemu. Predmet postavimo v vrsto zadaj in izstopimo iz vrste spredaj. Če preprosto povečamo sprednji in zadnji indeks, lahko pride do težav, sprednji del lahko doseže konec niza. Rešitev tega problema je krožno povečanje sprednjega in zadnjega dela.
Koraki za vpis v čakalno vrsto:
- Preverite, ali je čakalna vrsta polna ali ne
- Če je polno, natisnite overflow in zapustite
- Če čakalna vrsta ni polna, povečajte rep in dodajte element
Koraki za odstranitev iz čakalne vrste:
- Preverite, ali je čakalna vrsta prazna ali ne
- če je prazen, natisni spodnji del in zapusti
- če ni prazno, natisnite element na glavi in povečajte glavo
Spodaj je program za izvajanje zgornje operacije v čakalni vrsti
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->zmogljivost = zmogljivost;> >queue->spredaj = čakalna vrsta->velikost = 0;> >// This is important, see the enqueue> >queue->zadaj = prostornina - 1;> >queue->niz =>new> int>[queue->zmogljivost];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->velikost == čakalna vrsta->zmogljivost);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->velikost == 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->zadaj = (čakalna vrsta->zadaj + 1)> >% queue->zmogljivost;> >queue->array[queue->rear] = item;> >queue->velikost = čakalna vrsta->velikost + 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->polje[čakalna vrsta->spredaj];> >queue->spredaj = (čakalna vrsta->spredaj + 1)> >% queue->zmogljivost;> >queue->velikost = čakalna vrsta->velikost - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->polje[čakalna vrsta->spredaj];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->polje[čakalna vrsta->zadaj];> }> // 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> |
>
seznam programov python
>
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->zmogljivost = zmogljivost;> >queue->spredaj = čakalna vrsta->velikost = 0;> >// This is important, see the enqueue> >queue->zadaj = prostornina - 1;> >queue->niz = (>int>*)>malloc>(> >queue->zmogljivost *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->velikost == čakalna vrsta->zmogljivost);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->velikost == 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->zadaj = (čakalna vrsta->zadaj + 1)> >% queue->zmogljivost;> >queue->array[queue->rear] = item;> >queue->velikost = čakalna vrsta->velikost + 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->polje[čakalna vrsta->spredaj];> >queue->spredaj = (čakalna vrsta->spredaj + 1)> >% queue->zmogljivost;> >queue->velikost = čakalna vrsta->velikost - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->polje[čakalna vrsta->spredaj];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->polje[čakalna vrsta->zadaj];> }> // 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()> |
>
java char v int
>
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> > |
>
>Izhod
java stikalo int
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>
Analiza kompleksnosti:
- Časovna zapletenost
| Operacije | Kompleksnost |
|---|---|
| V čakalno vrsto (vstavljanje) | O(1) |
| Deque (izbris) | O(1) |
| Spredaj (dobi spredaj) | O(1) |
| Zadaj (dobi zadaj) | O(1) |
| IsFull (Preveri, ali je čakalna vrsta polna ali ne) | O(1) |
| IsEmpty (Preverite, ali je čakalna vrsta prazna ali ne) | O(1) |
- Pomožni prostor:
O(N), kjer je N velikost polja za shranjevanje elementov.
Prednosti implementacije polja:
- Enostaven za izvedbo.
- Z lahkoto je mogoče učinkovito upravljati veliko količino podatkov.
- Operacije, kot sta vstavljanje in brisanje, je mogoče izvesti z lahkoto, saj sledi pravilu prvi notri, prvi ven.
Slabosti implementacije polja:
- Statična struktura podatkov, fiksna velikost.
- Če ima čakalna vrsta veliko število operacij postavljanja v čakalno vrsto in odstranjevanja iz čakalne vrste, na neki točki (v primeru linearnega prirastka sprednjih in zadnjih indeksov) morda ne bomo mogli vstaviti elementov v čakalno vrsto, tudi če je čakalna vrsta prazna (tej težavi se izognemo z uporabo krožne čakalne vrste).
- Predhodno je treba določiti največjo velikost čakalne vrste.