Similar a Queue és una estructura de dades lineal que segueix un ordre particular en què es realitzen les operacions per emmagatzemar dades. L'ordre és First In First Out (FIFO) . Es pot imaginar una cua com una fila de persones esperant rebre alguna cosa en ordre seqüencial que comença des del principi de la línia. És una llista ordenada en què les insercions es fan en un extrem que es coneix com el darrere i les supressions es fan des de l'altre extrem conegut com el davant. Un bon exemple de cua és qualsevol cua de consumidors per a un recurs on el consumidor que ha arribat primer és atès primer.
La diferència entre les piles i les cues està en l'eliminació. En una pila traiem l'element afegit més recentment; en una cua, eliminem l'element que s'ha afegit menys recentment.
Estructura de dades de la cua
Operacions bàsiques a la cua:
- enqueue(): Insereix un element al final de la cua, és a dir, a la part posterior. dequeue(): aquesta operació elimina i retorna un element que es troba a la part frontal de la cua. front(): Aquesta operació retorna l'element a l'extrem frontal sense eliminar-lo. rear(): aquesta operació retorna l'element a la part posterior sense eliminar-lo. isEmpty(): aquesta operació indica si la cua està buida o no. isFull(): aquesta operació indica si la cua està plena o no. size(): aquesta operació retorna la mida de la cua, és a dir, el nombre total d'elements que conté.
Tipus de cues:
- Cua simple: la cua simple també coneguda com a cua lineal és la versió més bàsica d'una cua. Aquí, la inserció d'un element, és a dir, l'operació de col·locació de cua té lloc a l'extrem posterior i l'eliminació d'un element, és a dir, l'operació de retirada de cua es realitza a la part frontal. El problema aquí és que si fem un ítem des de la part davantera i després arribem a la part posterior fins a la capacitat de la cua i, tot i que hi ha espais buits abans de la part frontal, significa que la cua no està plena, però segons la condició de la funció isFull(), mostrarà que el aleshores la cua està plena. Per resoldre aquest problema fem servir la cua circular.
- Cua circular : En una cua circular, l'element de la cua actua com un anell circular. El funcionament d'una cua circular és similar a la cua lineal excepte pel fet que l'últim element està connectat al primer element. El seu avantatge és que la memòria s'utilitza millor. Això es deu al fet que si hi ha un espai buit, és a dir, si no hi ha cap element present en una determinada posició de la cua, es pot afegir fàcilment un element en aquesta posició mitjançant la capacitat del mòdul ( %n ).
- Cua de prioritats : Aquesta cua és un tipus especial de cua. La seva especialitat és que disposa els elements en una cua en funció d'alguna prioritat. La prioritat pot ser quelcom on l'element amb el valor més alt tingui la prioritat, de manera que es crea una cua amb un ordre decreixent de valors. La prioritat també pot ser tal que l'element amb el valor més baix tingui la prioritat més alta, de manera que al seu torn crea una cua amb un ordre creixent de valors. A la cua de prioritats predefinides, C++ dóna prioritat al valor més alt, mentre que Java dóna prioritat al valor més baix.
- D'acord amb : La sortida de cua també es coneix com a cua de doble final. Com el seu nom indica amb doble extrem, vol dir que un element es pot inserir o treure dels dos extrems de la cua, a diferència de les altres cues en què només es pot fer des d'un extrem. A causa d'aquesta propietat, pot no obeir la propietat First In First Out.
Aplicacions de la cua:
La cua s'utilitza quan les coses no s'han de processar immediatament, sinó que s'han de processar F primer jo n F primer O ut ordre com Primera recerca d'amplada . Aquesta propietat de Queue la fa també útil en els següents tipus d'escenaris.
- Quan un recurs es comparteix entre diversos consumidors. Alguns exemples inclouen la programació de la CPU, la programació del disc. Quan les dades es transfereixen de manera asíncrona (les dades no necessàriament es reben a la mateixa velocitat que s'envien) entre dos processos. Alguns exemples inclouen IO Buffers, canonades, fitxers IO, etc. La cua es pot utilitzar com a component essencial en diverses altres estructures de dades.
Implementació de matriu de cua:
Per implementar la cua, hem de fer un seguiment de dos índexs, frontal i posterior. Posem a la cua un article a la part posterior i retirem un article de la cua per davant. Si simplement augmentem els índexs frontals i posteriors, pot haver-hi problemes, la part davantera pot arribar al final de la matriu. La solució a aquest problema és augmentar la part davantera i posterior de manera circular.
Passos per a la cua:
- Comproveu que la cua estigui plena o no
- Si està ple, imprimeix el desbordament i surt
- Si la cua no està plena, incrementeu la cua i afegiu l'element
Passos per treure la cua:
- Comproveu que la cua estigui buida o no
- si està buit, imprimiu el desbordament inferior i sortiu
- si no està buit, imprimiu l'element al capçal i incrementeu-lo
A continuació es mostra un programa per implementar l'operació anterior a la cua
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->capacitat = capacitat;> >queue->front = cua->mida = 0;> >// This is important, see the enqueue> >queue->posterior = capacitat - 1;> >queue->matriu =>new> int>[queue->capacitat];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->mida == cua->capacitat);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->mida == 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->posterior = (cua->darrera + 1)> >% queue->capacitat;> >queue->array[queue->rear] = element;> >queue->mida = cua->mida + 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->matriu[cua->front];> >queue->front = (cua->front + 1)> >% queue->capacitat;> >queue->mida = cua->mida - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matriu[cua->front];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matriu[cua->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> |
cadena a la matriu c
>
>
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->capacitat = capacitat;> >queue->front = cua->mida = 0;> >// This is important, see the enqueue> >queue->posterior = capacitat - 1;> >queue->matriu = (>int>*)>malloc>(> >queue->capacitat *>>>, 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->matriu[cua->front];> >queue->front = (cua->front + 1)> >% queue->capacitat;> >queue->mida = cua->mida - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matriu[cua->front];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matriu[cua->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> |
comparar amb la cadena
>
>
Python 3
# 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> > |
>
>Sortida
classe de cadena java
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>
Anàlisi de complexitat:
- Complexitat temporal
| Operacions | Complexitat |
|---|---|
| Cua (inserció) | O(1) |
| Deque (supressió) | O(1) |
| Davant (Pon al davant) | O(1) |
| Rear (Aconseguir darrere) | O(1) |
| IsFull (comprova que la cua estigui plena o no) | O(1) |
| IsEmpty (Comprova que la cua estigui buida o no) | O(1) |
- Espai auxiliar:
O(N) on N és la mida de la matriu per emmagatzemar elements.
Avantatges de la implementació de matrius:
- Fàcil d'implementar.
- Una gran quantitat de dades es pot gestionar de manera eficient amb facilitat.
- Operacions com la inserció i la supressió es poden realitzar amb facilitat, ja que segueix la regla del primer en entrar, primer en sortir.
Desavantatges de la implementació de matrius:
- Estructura de dades estàtiques, mida fixa.
- Si la cua té un gran nombre d'operacions de col·locació i eliminació de la cua, en algun moment (en cas d'increment lineal dels índexs frontals i posteriors) és possible que no puguem inserir elements a la cua encara que la cua estigui buida (aquest problema s'evita utilitzant la cua circular).
- La mida màxima d'una cua s'ha de definir prèviament.