U računalnoj znanosti, red je linearna struktura podataka gdje se komponente stavljaju na jedan kraj i uklanjaju s drugog kraja prema načelu 'prvi ušao, prvi izašao' (FIFO). Ova struktura podataka može se koristiti za kontrolu niza radnji ili pohranu podataka. C je računalni jezik s mogućnošću čekanja uključenom u obliku nizova ili povezanih popisa.

Karakteristike:

• Red je vrsta linearne podatkovne strukture koja se može konstruirati s nizom ili povezanim popisom.
• Elementi se premještaju na stražnju stranu reda dok se uklanjaju s prednje strane.
• Stavljanje u red (dodavanje elementa pozadi) i uklanjanje iz reda (uklanjanje elementa s prednje strane) dvije su operacije čekanja.
• Kada se elementi često dodaju i uklanjaju, red se može izgraditi kao kružni red kako bi se spriječilo trošenje memorije.

Korištenje polja:

Da biste implementirali red čekanja u C-u koristeći niz, prvo definirajte maksimalnu veličinu reda i deklarirajte niz te veličine. Prednji i stražnji cijeli brojevi redom su postavljeni na 1. Prednja varijabla predstavlja prednji element reda čekanja, a stražnja varijabla predstavlja stražnji element.

Prije nego što gurnemo novi element na konačnu poziciju u redu čekanja, moramo povećati varijablu back za 1. Red čekanja je sada pun i nikakvi drugi dodatni elementi se ne mogu dodati kada zadnja pozicija dosegne maksimalni kapacitet reda čekanja. Dodamo element na početak reda i povećamo prednju varijablu za jedan samo da uklonimo element iz reda. Ako su prednja i stražnja pozicija jednake i nijedna se komponenta više ne može izbrisati, možemo reći da je red prazan.

Ispod je primjer reda čekanja napisanog u C-u koji koristi niz:

C programski jezik:

 #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; }  

Izlaz koda će biti:

Izlaz:

 10 20 30 Queue is empty-1  

Obrazloženje:

1. Prvo stavljamo tri elementa 10, 20 i 30 u red čekanja.
2. Zatim uklanjamo iz reda i ispisujemo prednji element reda, koji je 10.
3. Zatim uklanjamo iz reda čekanja i ponovno ispisujemo prednji element reda čekanja, a to je 20.
4. Zatim uklanjamo iz reda čekanja i ponovno ispisujemo prednji element reda, koji je 30.
5. Naposljetku, iz praznog reda izrađujemo dequeue koji ispisuje 'Queue is prazan' i vraća -1.

Korištenje povezanog popisa:

Drugi alternativni pristup konstruiranju reda čekanja u programskom jeziku C je korištenje povezane liste. Svaki od čvorova u redu čekanja izražen je pomoću ove metode pomoću čvora koji sadrži vrijednost elementa i pokazivač na sljedeći čvor u redu čekanja. Kako bi se pratio prvi i zadnji čvor u redu čekanja, koriste se prednji i stražnji pokazivači.

Uspostavljamo novi čvor s vrijednošću elementa i postavljamo njegov sljedeći pokazivač na NULL kako bismo dodali element u red. Na novi čvor postavljamo prednji i stražnji pokazivač ako je red prazan. Ako nije, ažuriramo stražnji pokazivač i postavljamo sljedeći pokazivač starog stražnjeg čvora da pokazuje na novi čvor.

Prilikom brisanja čvora iz reda čekanja, prvo se briše prethodni čvor, zatim se prednji pokazivač ažurira na sljedeći čvor u redu čekanja i na kraju se oslobađa memorija koju je uklonjeni čvor zauzimao. Ako je prednji pokazivač NULL nakon uklanjanja, red je prazan.

Evo primjera reda implementiranog u C-u pomoću povezanog popisa:

C programski jezik:

 #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; }  

Izlaz koda će biti:

Izlaz:

 10 20 30 Queue is empty-1  

Obrazloženje:

1. Prvo stavljamo tri elementa 10, 20 i 30 u red čekanja.
2. Zatim uklanjamo iz reda i ispisujemo prednji element reda, koji je 10.
3. Zatim uklanjamo iz reda čekanja i ponovno ispisujemo prednji element reda čekanja, a to je 20.
4. Zatim uklanjamo iz reda čekanja i ponovno ispisujemo prednji element reda, koji je 30.
5. Na kraju, pokušavamo deaktivirati prazan red čekanja, što ispisuje poruku 'Red čekanja je prazan' i vraća -1.

Prednosti:

• Redovi čekanja su osobito korisni za implementaciju algoritama koji zahtijevaju da se elementi obrađuju u preciznom slijedu, kao što je pretraživanje u širinu i raspoređivanje zadataka.
• Budući da operacije u redu čekanja imaju O(1) vremensku složenost, mogu se izvršiti brzo čak i na ogromnim redovima čekanja.
• Redovi su posebno fleksibilni budući da se mogu jednostavno implementirati korištenjem niza ili povezanog popisa.

Nedostaci:

• Red čekanja, za razliku od stoga, ne može se konstruirati s jednim pokazivačem, što implementaciju reda čini malo složenijom.
• Ako je red čekanja konstruiran kao niz, mogao bi se uskoro popuniti ako se doda previše elemenata, što može dovesti do problema s izvedbom ili mogućeg pada.
• Kada se koristi povezana lista za implementaciju reda čekanja, opterećenje memorije svakog čvora može biti značajno, posebno za male elemente.

Zaključak:

Aplikacije koje koriste redove čekanja, ključnu strukturu podataka, uključuju operativne sustave, umrežavanje i igre, da spomenemo samo neke. Idealni su za algoritme koji moraju rukovati elementima u određenom redoslijedu budući da ih je jednostavno izraditi korištenjem niza ili povezanog popisa. Međutim, redovi čekanja imaju nedostatke koji se moraju uzeti u obzir pri odabiru strukture podataka za određenu aplikaciju, kao što su potrošnja memorije i složenost implementacije.