Podobne ako Queue je lineárna dátová štruktúra, ktorá sleduje určité poradie, v ktorom sa vykonávajú operácie na ukladanie dát. Poradie je First In First Out (FIFO) . Rad si možno predstaviť ako rad ľudí čakajúcich na prijatie niečoho v postupnom poradí, ktoré začína od začiatku radu. Je to usporiadaný zoznam, v ktorom sa vkladanie vykonáva na jednom konci, ktorý je známy ako zadný, a vymazáva sa na druhom konci, ktorý je známy ako predný. Dobrým príkladom radu je každý rad spotrebiteľov pre zdroj, kde je prvý obsluhovaný spotrebiteľ, ktorý prišiel ako prvý.
Rozdiel medzi zásobníkmi a frontami je v odstraňovaní. V zásobníku odstránime položku, ktorá bola pridaná naposledy; vo fronte odstránime položku, ktorá bola pridaná najmenej nedávno.
Štruktúra údajov frontu
Základné operácie vo fronte:
- enqueue(): Vloží prvok na koniec frontu, t.j. na zadný koniec. dequeue(): Táto operácia odstráni a vráti prvok, ktorý je na začiatku frontu. front(): Táto operácia vráti prvok na prednom konci bez jeho odstránenia. zadný(): Táto operácia vráti prvok na zadnom konci bez jeho odstránenia. isEmpty(): Táto operácia označuje, či je front prázdny alebo nie. isFull(): Táto operácia označuje, či je front plný alebo nie. size(): Táto operácia vráti veľkosť frontu, t.j. celkový počet prvkov, ktoré obsahuje.
Typy frontov:
- Jednoduchý rad: Jednoduchý rad známy aj ako lineárny rad je najzákladnejšou verziou radu. Tu sa vloženie prvku, t. j. operácia zaradenia do radu, uskutoční na zadnom konci a odstránenie prvku, t. j. operácia vyradenia do radu, sa uskutoční na prednom konci. Problém je v tom, že ak vytiahneme nejakú položku spredu a potom zozadu do kapacity frontu a hoci pred prednou časťou sú prázdne miesta, fronta nie je plná, ale podľa podmienky vo funkcii isFull() sa ukáže, že potom je rad plný. Na vyriešenie tohto problému používame kruhovú frontu.
- Kruhový rad : V kruhovom rade pôsobí prvok radu ako kruhový krúžok. Fungovanie kruhového radu je podobné ako pri lineárnom rade s tým rozdielom, že posledný prvok je spojený s prvým prvkom. Jeho výhodou je lepšie využitie pamäte. Je to preto, že ak je prázdne miesto, t. j. ak sa na určitej pozícii vo fronte nenachádza žiadny prvok, potom možno prvok jednoducho pridať na túto pozíciu pomocou modulo kapacity ( %n ).
- Prioritný front : Tento rad je špeciálnym typom frontu. Jeho špecialitou je, že zoraďuje prvky do radu na základe určitej priority. Priorita môže byť niečo, kde má prioritu prvok s najvyššou hodnotou, takže vytvorí rad s klesajúcim poradím hodnôt. Priorita môže byť aj taká, že prvok s najnižšou hodnotou dostane najvyššiu prioritu, takže následne vytvorí rad s rastúcim poradím hodnôt. V preddefinovanom fronte priority dáva C++ prioritu najvyššej hodnote, zatiaľ čo Java dáva prioritu najnižšej hodnote.
- Podľa toho : Dequeue je tiež známy ako Double Ended Queue. Ako už názov napovedá s dvojitým zakončením, znamená to, že prvok možno vložiť alebo odstrániť z oboch koncov fronty, na rozdiel od ostatných frontov, v ktorých to môže byť vykonané iba z jedného konca. Kvôli tejto vlastnosti nemusí spĺňať vlastnosť First In First Out.
Aplikácie frontu:
Fronta sa používa, keď veci nemusia byť spracované okamžite, ale musia byť spracované F najprv ja n F najprv O ut poradia ako Prvé vyhľadávanie podľa šírky . Vďaka tejto vlastnosti Queue je tiež užitočná v nasledujúcich typoch scenárov.
- Keď je zdroj zdieľaný medzi viacerými spotrebiteľmi. Príklady zahŕňajú plánovanie CPU, plánovanie disku. Keď sa dáta prenášajú asynchrónne (údaje sa nemusia nevyhnutne prijímať rovnakou rýchlosťou ako odosielané) medzi dvoma procesmi. Príklady zahŕňajú IO vyrovnávacie pamäte, kanály, súbor IO atď. Fronta môže byť použitá ako základný komponent v rôznych iných dátových štruktúrach.
Implementácia poľa frontu:
Na implementáciu frontu potrebujeme sledovať dva indexy, predný a zadný. Položku zaradíme do poradia vzadu a položku spredu. Ak jednoducho zvýšime predný a zadný index, môžu nastať problémy, predný môže dosiahnuť koniec poľa. Riešením tohto problému je zväčšenie prednej a zadnej časti kruhovým spôsobom.
Kroky pre poradie:
- Skontrolujte, či je front plný alebo nie
- Ak je plná, pretečenie tlače a ukončenie
- Ak fronta nie je plná, zvýšte koniec a pridajte prvok
Kroky na vyradenie z frontu:
- Skontrolujte, či je front prázdny alebo nie
- ak je prázdny, vytlačte podtečenie a výstup
- ak nie je prázdny, vytlačte prvok na hlave a prírastkovú hlavu
Nižšie je uvedený program na implementáciu vyššie uvedenej operácie vo fronte
C++
string json java
// 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->kapacita = kapacita;> >queue->front = front->veľkosť = 0;> >// This is important, see the enqueue> >queue->vzadu = kapacita - 1;> >queue->pole =>new> int>[queue->kapacita];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->veľkosť == front->kapacita);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->veľkosť == 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->zadný = (front->zadný + 1)> >% queue->kapacita;> >queue->array[queue->rear] = item;> >queue->veľkosť = front->veľkosť + 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[queue->front];> >queue->front = (front->front + 1)> >% queue->kapacita;> >queue->veľkosť = front->veľkosť - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->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->kapacita = kapacita;> >queue->front = front->veľkosť = 0;> >// This is important, see the enqueue> >queue->vzadu = kapacita - 1;> >queue->pole = (>int>*)>malloc>(> >queue->kapacita *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->veľkosť == front->kapacita);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->veľkosť == 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->zadný = (front->zadný + 1)> >% queue->kapacita;> >queue->array[queue->rear] = item;> >queue->veľkosť = front->veľkosť + 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[queue->front];> >queue->front = (front->front + 1)> >% queue->kapacita;> >queue->veľkosť = front->veľkosť - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->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;> }> |
>
ako zistiť, či vás niekto zablokoval v systéme Android
>
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
rozhranie v jazyku Java
# 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()> |
Fibonacciho sekvencia java
>
>
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
okno.otvoriť
> // 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> > |
>
>Výkon
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>
Analýza zložitosti:
- Časová zložitosť
| Operácie | Zložitosť |
|---|---|
| Zaradiť (vloženie) | O(1) |
| Deque (vymazanie) | O(1) |
| Predné (dostať sa dopredu) | O(1) |
| Zadné (dostať dozadu) | O(1) |
| IsFull (Kontrolný front je plný alebo nie) | O(1) |
| IsEmpty (Kontrolný front je prázdny alebo nie) | O(1) |
- Pomocný priestor:
O(N) kde N je veľkosť poľa na uloženie prvkov.
Výhody implementácie Array:
- Jednoduchá implementácia.
- Veľké množstvo údajov je možné efektívne a jednoducho spravovať.
- Operácie, ako je vkladanie a vymazávanie, je možné vykonávať jednoducho, pretože sa riadi pravidlom prvý dovnútra, prvý von.
Nevýhody implementácie Array:
- Statická dátová štruktúra, pevná veľkosť.
- Ak má front veľký počet operácií zaradenia a vyradenia z radu, v určitom bode (v prípade lineárneho prírastku predných a zadných indexov) nemusíme byť schopní vložiť prvky do frontu, aj keď je front prázdny (týmto problémom sa dá vyhnúť pomocou kruhového radu).
- Maximálna veľkosť frontu musí byť definovaná vopred.