En informàtica, una cua és una estructura de dades lineal on els components es col·loquen en un extrem i s'eliminen de l'altre extrem d'acord amb el principi de 'primer en entrar, primer en sortir' (FIFO). Aquesta estructura de dades es pot utilitzar per controlar una seqüència d'accions o emmagatzemar dades. C és un llenguatge informàtic amb capacitat de cua incorporada en forma de matrius o llistes enllaçades.
Característiques:
- Una cua és un tipus d'estructura de dades lineal que es pot construir amb una matriu o una llista enllaçada.
- Els elements es col·loquen a la part posterior de la cua mentre s'eliminen de la part davantera.
- Posar a la cua (afegir un element a la part posterior) i eliminar la cua (eliminar un element de la part davantera) són dues operacions de cua.
- Quan s'afegeixen i s'eliminen elements sovint, es pot crear una cua com una cua circular per evitar malgastar memòria.
Utilitzant Array:
Per implementar una cua en C mitjançant una matriu, primer definiu la mida màxima de la cua i declareu una matriu d'aquesta mida. Els enters frontals i posteriors es van establir respectivament a 1. La variable frontal representa l'element frontal de la cua i la variable posterior representa l'element posterior.
Abans d'empènyer el nou element a la posició final de la cua, hem d'augmentar la variable de darrere en 1. Ara la cua està plena i no es poden afegir altres elements addicionals quan la posició posterior arriba a la capacitat màxima de la cua. Afegim un element al capdavant de la cua i augmentem la variable frontal en un només per eliminar un element de la cua. Si les posicions davantera i posterior són iguals i no es poden suprimir més components, per tant podem dir que la cua està buida.
llista de matrius en l'ordenació java
A continuació es mostra una instància d'una cua escrita en C que fa ús d'una matriu:
Llenguatge de programació C:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } La sortida del codi serà:
Com accedir a les fotos d'iCloud
Sortida:
10 20 30 Queue is empty-1
Explicació:
- Primer, posem a la cua tres elements 10, 20 i 30.
- A continuació, retirem la cua i imprimim l'element frontal de la cua, que és 10.
- A continuació, tornem a treure i imprimir l'element frontal de la cua, que és 20.
- A continuació, retirem la cua i tornem a imprimir l'element frontal de la cua, que és 30.
- Finalment, fem una sortida de cua d'una cua buida que mostra 'La cua està buida' i retorna -1.
Ús de la llista enllaçada:
Un altre enfocament alternatiu per construir una cua en el llenguatge de programació C és utilitzar una llista enllaçada. Cadascun dels nodes de la cua s'expressa mitjançant aquest mètode mitjançant un node que conté el valor de l'element i un punter al següent node de la cua. Per fer un seguiment del primer i l'últim node de la cua, respectivament, s'utilitzen punters frontals i posteriors.
Establim un nou node amb el valor de l'element i establim el seu següent punter a NULL per afegir un element a la cua. Al nou node, posem els punters frontal i posterior si la cua està buida. Si no, actualitzem el punter posterior i establim el següent punter del node posterior antic perquè apunti al nou node.
Quan s'elimina un node d'una cua, primer s'elimina el node anterior, després s'actualitza el punter frontal al node posterior de la cua i, finalment, s'allibera la memòria que ocupava el node eliminat. Si el punter frontal és NULL després de l'eliminació, la cua està buida.
js onclick
Aquí teniu un exemple d'una cua implementada en C mitjançant una llista enllaçada:
Llenguatge de programació C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } La sortida del codi serà:
Sortida:
un exemple d'un sistema operatiu de codi obert és
10 20 30 Queue is empty-1
Explicació:
- Primer, posem a la cua tres elements 10, 20 i 30.
- A continuació, retirem la cua i imprimim l'element frontal de la cua, que és 10.
- A continuació, tornem a treure i imprimir l'element frontal de la cua, que és 20.
- A continuació, retirem la cua i tornem a imprimir l'element frontal de la cua, que és 30.
- Finalment, intentem treure la cua de la cua buida, que imprimeix el missatge 'La cua està buida' i retorna -1.
Avantatges:
- Les cues són especialment útils per implementar algorismes que requereixen que els elements es processin en una seqüència precisa, com ara la cerca en amplitud i la programació de tasques.
- Com que les operacions de cua tenen una complexitat de temps O(1), es poden executar ràpidament fins i tot en cues enormes.
- Les cues són particularment flexibles, ja que es poden implementar simplement mitjançant una matriu o una llista enllaçada.
Desavantatges:
- Una cua, a diferència d'una pila, no es pot construir amb un sol punter, cosa que fa que la implementació de la cua sigui una mica més complicada.
- Si la cua es construeix com una matriu, aviat s'omplirà si s'afegeixen massa elements, la qual cosa comporta problemes de rendiment o possiblement un error.
- Quan s'utilitza una llista enllaçada per implementar la cua, la sobrecàrrega de memòria de cada node pot ser important, especialment per als elements petits.
Conclusió:
Les aplicacions que utilitzen cues, una estructura de dades crucial, inclouen sistemes operatius, xarxes i jocs, per citar-ne només algunes. Són ideals per a algorismes que han de manejar elements en un ordre particular, ja que són senzills de crear mitjançant una matriu o una llista enllaçada. Tanmateix, les cues tenen desavantatges que s'han de tenir en compte a l'hora de seleccionar una estructura de dades per a una aplicació concreta, com ara el consum de memòria i la complexitat de la implementació.