Podobně jako Queue je lineární datová struktura, která sleduje určité pořadí, ve kterém jsou operace prováděny pro ukládání dat. Pořadí je First In First Out (FIFO) . Frontu si lze představit jako řadu lidí čekajících na přijetí něčeho v sekvenčním pořadí, které začíná od začátku řady. Je to uspořádaný seznam, ve kterém se vkládání provádí na jednom konci, který je známý jako zadní, a mazání se provádí na druhém konci známém jako přední. Dobrým příkladem fronty je jakákoli fronta spotřebitelů pro zdroj, kde je jako první obsluhován spotřebitel, který přišel jako první.
Rozdíl mezi zásobníky a frontami je v odstraňování. V zásobníku odstraníme položku, která byla přidána naposledy; ve frontě odstraníme položku, která byla přidána nejméně nedávno.
Struktura dat fronty
Základní operace ve frontě:
- enqueue(): Vloží prvek na konec fronty, tj. na zadní konec. dequeue(): Tato operace odstraní a vrátí prvek, který je na předním konci fronty. front(): Tato operace vrátí prvek na frontend bez jeho odstranění. zadní(): Tato operace vrátí prvek na zadním konci, aniž by jej odstranil. isEmpty(): Tato operace označuje, zda je fronta prázdná nebo ne. isFull(): Tato operace označuje, zda je fronta plná nebo ne. size(): Tato operace vrací velikost fronty, tj. celkový počet prvků, které obsahuje.
Typy front:
- Jednoduchá fronta: Jednoduchá fronta známá také jako lineární fronta je nejzákladnější verzí fronty. Zde se vkládání prvku, tj. operace zařazování do fronty, provádí na zadním konci a vyjímání prvku, tj. operace zařazování do fronty, probíhá na předním konci. Zde problém spočívá v tom, že pokud vytáhneme nějakou položku zepředu a pak zezadu do kapacity fronty a ačkoli jsou před frontou prázdná místa, fronta není plná, ale podle podmínky ve funkci isFull() se ukáže, že fronta je pak plná. K vyřešení tohoto problému používáme kruhovou frontu .
- Kruhová fronta : V kruhové frontě působí prvek fronty jako kruhový kruh. Činnost kruhové fronty je podobná jako u lineární fronty s tím rozdílem, že poslední prvek je spojen s prvním prvkem. Jeho výhodou je lepší využití paměti. Je to proto, že pokud je prázdné místo, tj. pokud na určité pozici ve frontě není přítomen žádný prvek, lze prvek na tuto pozici snadno přidat pomocí modulo kapacity( %n ).
- Prioritní fronta : Tato fronta je zvláštním typem fronty. Jeho specialitou je, že řadí prvky do fronty na základě nějaké priority. Priorita může být něco, kde má prioritu prvek s nejvyšší hodnotou, takže vytvoří frontu s klesajícím pořadím hodnot. Priorita může být také taková, že prvek s nejnižší hodnotou dostane nejvyšší prioritu, takže vytvoří frontu s rostoucím pořadím hodnot. V předdefinované frontě priority dává C++ prioritu nejvyšší hodnotě, zatímco Java dává prioritu nejnižší hodnotě.
- V souladu s tím : Dequeue je také známá jako Double Ended Queue. Jak název napovídá double end, znamená to, že prvek lze vložit nebo odebrat z obou konců fronty, na rozdíl od ostatních front, ve kterých to lze provést pouze z jednoho konce. Kvůli této vlastnosti nemusí splňovat vlastnost First In First Out.
Aplikace fronty:
Fronta se používá, když věci nemusí být zpracovány okamžitě, ale musí být zpracovány F první já n F první Ó ut objednat jako První vyhledávání šířky . Díky této vlastnosti Queue je také užitečný v následujících typech scénářů.
- Když je zdroj sdílen mezi více spotřebiteli. Příklady zahrnují plánování CPU, Plánování disku. Když jsou data přenášena asynchronně (data nemusí být nutně přijímána stejnou rychlostí jako odesílaná) mezi dvěma procesy. Příklady zahrnují IO Buffery, roury, soubor IO atd. Fronta může být použita jako základní součást v různých jiných datových strukturách.
Implementace pole fronty:
Pro implementaci fronty potřebujeme sledovat dva indexy, přední a zadní. Položku zařadíme do fronty vzadu a položku vyřadíme zepředu. Pokud jednoduše zvýšíme přední a zadní indexy, pak mohou nastat problémy, přední může dosáhnout konce pole. Řešením tohoto problému je zvětšení přední a zadní části kruhovým způsobem.
Kroky pro zařazení do fronty:
- Zkontrolujte, zda je fronta plná nebo ne
- Je-li plná, přetečení tisku a ukončení
- Pokud fronta není plná, zvyšte konec a přidejte prvek
Kroky pro vyřazení z fronty:
- Zkontrolujte, zda je fronta prázdná nebo ne
- pokud je prázdný, vytiskněte podtečení a ukončete
- pokud není prázdný, tiskněte prvek na hlavě a inkrementační hlavě
Níže je uveden program pro implementaci výše uvedené operace ve frontě
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->kapacita = kapacita;> >queue->front = fronta->velikost = 0;> >// This is important, see the enqueue> >queue->zadní = 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->velikost == fronta->kapacita);> }> // 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->zadní = (fronta->zadní + 1)> >% queue->kapacita;> >queue->array[queue->rear] = item;> >queue->velikost = fronta->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->array[queue->front];> >queue->front = (fronta->front + 1)> >% queue->kapacita;> >queue->velikost = fronta->velikost - 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 = fronta->velikost = 0;> >// This is important, see the enqueue> >queue->zadní = 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->velikost == fronta->kapacita);> }> // 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->zadní = (fronta->zadní + 1)> >% queue->kapacita;> >queue->array[queue->rear] = item;> >queue->velikost = fronta->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->array[queue->front];> >queue->front = (fronta->front + 1)> >% queue->kapacita;> >queue->velikost = fronta->velikost - 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;> }> |
>
>
Jáva
// 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();> >}> }> }> |
>
>
Javascript
řazení vkládání java
> // 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ýstup
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 složitosti:
- Časová složitost
| Operace | Složitost |
|---|---|
| Zařadit (vložení) | O(1) |
| Deque (smazání) | O(1) |
| Přední (dostat se dopředu) | O(1) |
| Rear (Get Rear) | O(1) |
| IsFull (kontrolní fronta je plná nebo ne) | O(1) |
| IsEmpty (kontrolní fronta je prázdná nebo ne) | O(1) |
- Pomocný prostor:
O(N) kde N je velikost pole pro uložení prvků.
Výhody implementace Array:
- Snadná implementace.
- Velké množství dat lze snadno a efektivně spravovat.
- Operace, jako je vkládání a mazání, lze snadno provádět, protože se řídí pravidlem první dovnitř, první ven.
Nevýhody implementace pole:
- Statická datová struktura, pevná velikost.
- Pokud má fronta velký počet operací fronty a dequeue, v určitém okamžiku (v případě lineárního přírůstku předních a zadních indexů) nemusíme být schopni vložit prvky do fronty, i když je fronta prázdná (tomuto problému se vyhneme pomocí kruhové fronty).
- Maximální velikost fronty musí být definována předem.