În informatică, o coadă este o structură de date liniară în care componentele sunt puse într-un capăt și îndepărtate de la celălalt capăt conform principiului „primul intrat, primul ieșit” (FIFO). Această structură de date poate fi utilizată pentru controlul unei secvențe de acțiuni sau pentru stocarea datelor. C este un limbaj de calculator cu capacitate de coadă încorporată sub formă de matrice sau liste legate.
Caracteristici:
- O coadă este un tip de structură de date liniară care poate fi construită cu o matrice sau o listă legată.
- Elementele sunt mutate în spatele cozii în timp ce sunt îndepărtate din față.
- Pune în coadă (adăugați un element în spate) și scoateți la coadă (eliminați un element din față) sunt două operațiuni de coadă.
- Când elementele sunt adăugate și eliminate des, o coadă poate fi construită ca o coadă circulară pentru a preveni risipa de memorie.
Folosind Array:
Pentru a implementa o coadă în C folosind o matrice, mai întâi definiți dimensiunea maximă a cozii și declarați o matrice de acea dimensiune. Numerele întregi din față și din spate au fost setate la 1. Variabila din față reprezintă elementul din față al cozii, iar variabila din spate reprezintă elementul din spate.
Înainte de a împinge noul element în poziția finală a cozii, trebuie să creștem variabila din spate cu 1. Coada este acum plină și nu pot fi adăugate alte elemente suplimentare când poziția din spate atinge capacitatea maximă a cozii. Adăugăm un element în fața cozii și creștem variabila din față cu una doar pentru a elimina un element din coadă. Dacă pozițiile față și spate sunt egale și nu mai pot fi șterse componente, deci putem spune că coada este goală.
Mai jos este o instanță a unei cozi scrise în C care utilizează o matrice:
Limbajul de programare 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; } Ieșirea codului va fi:
Ieșire:
10 20 30 Queue is empty-1
Explicaţie:
- Mai întâi, punem în coadă trei elemente 10, 20 și 30 în coadă.
- Apoi, scoatem la coadă și imprimăm elementul frontal al cozii, care este 10.
- Apoi, scoatem din coadă și imprimăm din nou elementul din față al cozii, care este 20.
- Apoi, scoatem la coadă și imprimăm din nou elementul din față al cozii, care este 30.
- În cele din urmă, facem o coadă dintr-o coadă goală care scoate „Coada este goală” și returnează -1.
Utilizarea listei conectate:
O altă abordare alternativă pentru construirea unei cozi în limbajul de programare C este utilizarea unei liste legate. Fiecare dintre nodurile din coadă este exprimat folosind această metodă printr-un nod care conține valoarea elementului și un pointer către următorul nod din coadă. Pentru a ține evidența primului și, respectiv, ultimul nod din coadă, se folosesc indicatori din față și din spate.
Stabilim un nou nod cu valoarea elementului și setăm următorul indicator la NULL pentru a adăuga un element la coadă. Pentru noul nod, setăm pointerii din față și din spate dacă coada este goală. Dacă nu, actualizăm indicatorul din spate și setăm următorul indicator al vechiului nod din spate să indice noul nod.
Când ștergeți un nod dintr-o coadă, nodul precedent este șters mai întâi, apoi indicatorul frontal este actualizat la nodul următor din coadă și, în final, este eliberată memoria pe care o ocupa nodul eliminat. Dacă indicatorul frontal este NULL după eliminare, coada este goală.
Iată un exemplu de coadă implementată în C folosind o listă legată:
Limbajul de programare 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; } Ieșirea codului va fi:
Ieșire:
10 20 30 Queue is empty-1
Explicaţie:
- Mai întâi, punem în coadă trei elemente 10, 20 și 30 în coadă.
- Apoi, scoatem la coadă și imprimăm elementul frontal al cozii, care este 10.
- Apoi, scoatem din coadă și imprimăm din nou elementul frontal al cozii, care este 20.
- Apoi, scoatem la coadă și imprimăm din nou elementul din față al cozii, care este 30.
- În cele din urmă, încercăm să scoatem coada din coada goală, care afișează mesajul „Coada este goală” și returnează -1.
Avantaje:
- Cozile sunt deosebit de utile pentru implementarea algoritmilor care necesită procesarea elementelor într-o secvență precisă, cum ar fi căutarea pe lățime și programarea sarcinilor.
- Deoarece operațiunile de coadă au o complexitate de timp O(1), ele pot fi executate rapid chiar și pe cozi enorme.
- Cozile sunt deosebit de flexibile, deoarece pot fi implementate pur și simplu folosind o matrice sau o listă legată.
Dezavantaje:
- O coadă, spre deosebire de o stivă, nu poate fi construită cu un singur pointer, ceea ce face implementarea cozii puțin mai complicată.
- Dacă coada este construită ca o matrice, s-ar putea umple în curând dacă se adaugă prea multe elemente, ceea ce duce la probleme de performanță sau posibil o blocare.
- Când se utilizează o listă legată pentru a implementa coada, supraîncărcarea de memorie a fiecărui nod poate fi semnificativă, în special pentru elementele mici.
Concluzie:
Aplicațiile care folosesc cozi, o structură de date crucială, includ sisteme de operare, rețele și jocuri, pentru a numi doar câteva. Sunt ideali pentru algoritmii care trebuie să gestioneze elemente într-o anumită ordine, deoarece sunt simplu de creat folosind o matrice sau o listă legată. Cu toate acestea, cozile au dezavantaje care trebuie luate în considerare atunci când se selectează o structură de date pentru o anumită aplicație, cum ar fi consumul de memorie și complexitatea implementării.