Salut! As avea nevoie de ajutor, daca imi poate explica cineva cam in ce tipuri de probleme se foloseste coada ( queue )
Stiu ca se foloseste la Lee si ca e mai rapid decat sa scoti dintr-un vector, dar, in general, ce utilitate practica are?
c++
Răspunsuri la întrebare
O coada e foarte buna in modelarea problemelor in care ai o serie de chestii (joburi, noduri, instante ale unor clase, taskuri, etc.) unde ai elemente care se adauga in lista de "chestii" de procesat iar tu trebuie sa le procesezi in ordinea in care vin. In plus nu te intereseaza sa alte elemente din coada decat din capul cozii.
De ce (si cand) o coada e mai rapida decat un vector ?
► Complexitatile pentru opeartiile pe vector :
- Intr-un vector inserarea unui element la finalul cozii se poate efectua imediat (in conditia in care vectorul are dimensiune suficienta si nu trebuie facuta relocare) - complexitate O(1).
- Intr-un vector stergerea elementului din fata cozii are o eficienta "criminala", trebuie sa luam toate elementele la rand si sa le ducem o pozitie mai inainte - complexitate O(n).
- Intr-un vector accesearea unui element la intamplare (care nu e capul cozii) se poate face in (e aritmetica cu pointeri urmat de o accesare de memorie) - complexitate O(1).
Pe noi ne cam "rupe" stergerea elementului din capul cozii, daca in ce avem noi nevoie sa facem operatia asta se executa des nu e prea minunat.
► Complexitati pentru operatii pe coada (implementata frumos cu noduri ca o lista simplu inlantuita) :
- ( ! ) Inserarea unui element la finalul cozii - complexitate O(1) - se creaza nod nou, se face legatura cu nodul precedent, se actualizeaza pointerul cu finalul cozii.
- ( ! ) Stergerea elementului aflat la inceputul cozii - complexitate O(1) - se actualizeaza pointerul catre primul nod cu nodul de pe pozitia II (pe baza legaturii nodului I cu nodul II) si se dealoca primul nod.
- Accesarea unui element la intamplare - complexitate teoretica O(n) daca vrem neaparat - trebuie sa luam nodurile la rand din fata in spate si sa cautam ce ne intereseaza. Aceasta operatie nici nu e permisa pe coada si deosebeste coada de lista simplu inlantuita (coada e o restrictie impusa listei simplu inlantuite).
Deci am gasit cum sa stergem primul element in O(1), minunat, putem sa folosim aceasta minunata structura de date peste tot unde ne intereseaza doar cele doua operatii marcate cu semnul exclamarii ( ! ).
Unde ai folosi o coada in viata reala ai folosi o coada si in programare, nu sunt foarte multe de zis sincer. Iti las mai jos cateva cazuri in care ai folosi o coada, unele ceva mai teoretice axate pe informatica, altele ceva mai practice:
► Ai o sala de asteptare (la doctor, primarie, mos craciun, whatever), vin persoane noi mereu, tu trebuie sa il iei mereu pe primul venit, sa il rezolvi, apoi sa il stergi din lista.
► S-a digitalizat primaria, oamenii trimit online dosarul cu ce are nevoie fiecare, trebuie sa iei dosarul fiecaruia din coada principala si sa il pui la o coada secundara pentru fiecare departament (o coada pentru cereri adeverinte, o coada pentru cei care asteapta cadastru sau autorizatie de constructie, etc.). Apoi la fiecare coada e o persoana care ia primul dosar din coada respectiva, il rezolva si il pun fie in alta coada secundara decat aceasta ( daca e nevoie si de implicarea altui departament - ca mna, chiar daca s-a modernizat primarie tot e birocratie), fie termina cu el de tot.
► Ai nevoie de o lista de noduri dintr-un graf astfel incat nodurile sa fie parcurse in latime (algoritmul lui Lee). In plus, fata de de coada se foloseste si un vector/matrice caracteristica care iti indica daca ai fost sau nu in nodul respectiv (sau un unordered_set care indeplineste acelasi scop)
► Ai o matrice care reprezinta un desen, un teren sau altceva, trebuie sa umpli (ca galeata cu culoare din Paint in cazul desenului, in cazul terenului asa poti vedea suprafata unui teren conex in care valoarea matricei e numele/ID-ul proprietarului) toate casutele alaturate care au aceasi valoare. Acesta e algoritmul de Fill, poate fi implementat recursiv, cu stiva sau cu coada. E practic tot algoritmul lui Lee, dar pentru matrice, nu pentru graf.
► Proiectezi un sistem de operare multitasking, fiecare proces e executat putin de catre un nucleu (pana se duce timpul alocat unui proces), apoi sunt executate cate putin si celelalte procese, la rand. In cazul asta folosesti o coada de procese, iei procesul din capul cozii, executi cateva instructiuni (daca l-ai terminat il iei pe urmatorul, daca procesul asteapta ceva resursa il pui in wait si il iei pe urmatorul, daca mai ai avea instrucituni de rulat dar a expirat cuantumul de timp il pui la coada si iei urmatoarul proces). Nu e un algoritm foarte eficient dar a fost folosit. Mai nou procesele sunt grupate pe mai multe niveluri de prioritate, pentru fiecare nivel e cate o coada, se foloseste un alt algoritm pentru stabilirea cozii din care se executa si se foloseste algoritmul asta simplu cu coada la nivelul fiecarei cozi. Sunt mai multi algoritmi de genul acesta pentru scheduling de procese, majoritatea folosesc cozi.
[VEZI FISIERUL ATASAT PENTRU RASPUNS COMPLET]
Pe Brainly un raspuns are maxim 5000 de caractere, am depasit putin. Gasesti raspunsul complet in fisierul .docx atasat.