V računalništvu je čakalna vrsta linearna podatkovna struktura, kjer so komponente postavljene na en konec in odstranjene z drugega konca po načelu 'prvi vstopi, prvi ven' (FIFO). To podatkovno strukturo je mogoče uporabiti za nadzor zaporedja dejanj ali shranjevanje podatkov. C je računalniški jezik z možnostjo čakalne vrste, vključeno v obliki nizov ali povezanih seznamov.
orodna vrstica za hitri dostop do besed
Značilnosti:
- Čakalna vrsta je vrsta linearne podatkovne strukture, ki jo je mogoče sestaviti z matriko ali povezanim seznamom.
- Elementi so prestavljeni na zadnji del čakalne vrste, medtem ko so odstranjeni s sprednje strani.
- Enqueue (dodaj element na zadnjo stran) in dequeue (odstrani element s sprednje strani) sta dve operaciji čakalne vrste.
- Ko se elementi pogosto dodajajo in odstranjujejo, je lahko čakalna vrsta zgrajena kot krožna čakalna vrsta, da se prepreči zapravljanje pomnilnika.
Uporaba polja:
Če želite implementirati čakalno vrsto v C z uporabo matrike, najprej definirajte največjo velikost čakalne vrste in deklarirajte matriko te velikosti. Sprednje in zadnje celo število sta bili nastavljeni na 1. Sprednja spremenljivka predstavlja sprednji element čakalne vrste, zadnja spremenljivka pa zadnji element.
Preden novi element potisnemo na končni položaj v čakalni vrsti, moramo spremenljivko nazaj povečati za 1. Čakalna vrsta je zdaj polna in nobenih drugih dodatnih elementov ni mogoče dodati, ko zadnji položaj doseže največjo zmogljivost čakalne vrste. Dodamo element na začetek čakalne vrste in povečamo sprednjo spremenljivko za eno samo, da odstranimo element iz čakalne vrste. Če sta sprednji in zadnji položaj enaka in ni mogoče izbrisati več komponent, lahko rečemo, da je čakalna vrsta prazna.
Spodaj je primer čakalne vrste, napisane v C, ki uporablja matriko:
Programski jezik 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; } Izhod kode bo:
Izhod:
10 20 30 Queue is empty-1
Pojasnilo:
shweta tiwari igralec
- Najprej v čakalno vrsto postavimo tri elemente 10, 20 in 30.
- Nato odstranimo čakalno vrsto in natisnemo sprednji element čakalne vrste, ki je 10.
- Nato odstranimo čakalno vrsto in ponovno natisnemo sprednji element čakalne vrste, ki je 20.
- Nato odstranimo iz čakalne vrste in ponovno natisnemo sprednji element čakalne vrste, ki je 30.
- Nazadnje iz prazne čakalne vrste naredimo odstranitev iz čakalne vrste, ki izpiše 'Čakalna vrsta je prazna' in vrne -1.
Uporaba povezanega seznama:
Drug alternativni pristop k izdelavi čakalne vrste v programskem jeziku C je uporaba povezanega seznama. Vsako od vozlišč v čakalni vrsti je s to metodo izraženo z vozliščem, ki vsebuje vrednost elementa in kazalec na naslednje vozlišče v čakalni vrsti. Za spremljanje prvega in zadnjega vozlišča v čakalni vrsti se uporabljata sprednji in zadnji kazalec.
java za oblikovanje nizov
Vzpostavimo novo vozlišče z vrednostjo elementa in nastavimo njegov naslednji kazalec na NULL, da dodamo element v čakalno vrsto. Novemu vozlišču nastavimo sprednji in zadnji kazalec, če je čakalna vrsta prazna. Če ne, posodobimo zadnji kazalec in nastavimo naslednji kazalec starega zadnjega vozlišča, da kaže na novo vozlišče.
Pri brisanju vozlišča iz čakalne vrste se najprej izbriše prejšnje vozlišče, nato se sprednji kazalec posodobi na naslednje vozlišče v čakalni vrsti in na koncu se sprosti pomnilnik, ki ga je zasedalo odstranjeno vozlišče. Če je sprednji kazalec po odstranitvi NULL, je čakalna vrsta prazna.
Tukaj je primer čakalne vrste, implementirane v C z uporabo povezanega seznama:
Programski jezik 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; } Izhod kode bo:
Izhod:
c program za dvodimenzionalni niz
10 20 30 Queue is empty-1
Pojasnilo:
- Najprej v čakalno vrsto postavimo tri elemente 10, 20 in 30.
- Nato odstranimo čakalno vrsto in natisnemo sprednji element čakalne vrste, ki je 10.
- Nato odstranimo čakalno vrsto in ponovno natisnemo sprednji element čakalne vrste, ki je 20.
- Nato odstranimo iz čakalne vrste in ponovno natisnemo sprednji element čakalne vrste, ki je 30.
- Na koncu poskusimo odstraniti iz prazne čakalne vrste, kar natisne sporočilo 'Čakalna vrsta je prazna' in vrne -1.
Prednosti:
- Čakalne vrste so še posebej uporabne za izvajanje algoritmov, ki zahtevajo obdelavo elementov v natančnem zaporedju, kot je iskanje po širini in razporejanje opravil.
- Ker imajo operacije v čakalni vrsti O(1) časovno zapletenost, jih je mogoče hitro izvesti tudi v ogromnih čakalnih vrstah.
- Čakalne vrste so še posebej prilagodljive, saj jih je mogoče preprosto implementirati z uporabo polja ali povezanega seznama.
Slabosti:
- Čakalne vrste, za razliko od sklada, ni mogoče sestaviti z enim samim kazalcem, zaradi česar je implementacija čakalne vrste nekoliko bolj zapletena.
- Če je čakalna vrsta sestavljena kot niz, se lahko kmalu zapolni, če se doda preveč elementov, kar povzroči pomisleke glede zmogljivosti ali morebitno zrušitev.
- Pri uporabi povezanega seznama za izvedbo čakalne vrste je lahko pomnilniška poraba vsakega vozlišča znatna, zlasti za majhne elemente.
Zaključek:
Aplikacije, ki uporabljajo čakalne vrste, ključno strukturo podatkov, vključujejo operacijske sisteme, mreženje in igre, če naštejemo le nekatere. Idealni so za algoritme, ki morajo obravnavati elemente v določenem vrstnem redu, saj jih je enostavno ustvariti z uporabo matrike ali povezanega seznama. Vendar imajo čakalne vrste slabosti, ki jih je treba upoštevati pri izbiri podatkovne strukture za določeno aplikacijo, kot sta poraba pomnilnika in kompleksnost implementacije.