Un ghid pentru începători pentru înțelegerea cozilor și a cozilor prioritare

În calitate de programator, veți lucra cu diferite structuri de date în funcție de sfera proiectelor dvs. Un astfel de concept este o structură de date în coadă; cozile sunt esențiale pentru studenți și sunt utilizate în numeroși algoritmi importanți. La fel ca cozile, cozile prioritare au un concept similar, dar au câteva diferențe fundamentale.

Citiți mai departe pentru a înțelege cozile și cozile prioritare.

Ce este o coadă?

O coadă este o structură simplă de date care are o varietate de aplicații în proiecte de codificare din viața reală. Structurile de date sunt inerent abstracte, dar, din motive de simplitate, ne imaginăm că o structură de date în coadă are o formă liniară cu două capete diferite.

În ceea ce privește complexitatea timpului, o coadă permite inserarea (coada) și ștergerea (coada) în timpul O (1). Datorită eficienței sale asimptotice, cozile sunt eficiente pentru seturile de date mari. Cozile sunt de tip first-in-first-out (FIFO), ceea ce înseamnă că un element de date care este introdus mai întâi va fi accesat mai întâi. În schimb, stivele au o natură last-in-first-out (LIFO) și au un singur capăt deschis.

Imaginați-vă o coadă de bilete la un cinematograf; fiecare client nou care ajunge se alătură cozii la un capăt. Rând pe rând, fiecare client cumpără un bilet și părăsește coada de la front-end. Structura datelor cozii funcționează exact ca orice coadă din lumea reală, iar datele sunt inserate (coadă) la un capăt și eliminate (coadă) la celălalt capăt. Acum puteți înțelege cu speranță raționamentul de ce cozile urmează o metodologie FIFO.

O coadă are o mulțime de aplicații de codificare în viața reală. Este mai frecvent utilizat în aplicații în care datele nu trebuie procesate imediat, ci mai degrabă într-o ordine FIFO. Programarea discurilor, transferul de date asincron, semaforele sunt câteva aplicații tipice. Sarcinile de planificare primul venit, primul servit, cum ar fi spoolingul de imprimare sau tampoanele dispozitivului de intrare, utilizează, de asemenea, o coadă.

Ce este o coadă prioritară?

O coadă prioritară este similară cu o coadă, dar are proprietăți suplimentare. Când un element de date este pus în coadă în coada de prioritate, i se acordă un număr de prioritate. Spre deosebire de stingerea unei cozi standard, elementele de date cu prioritate ridicată sunt stinse înainte de elementele de date cu prioritate scăzută. Prioritatea înlocuiește ordinea de sosire într-o coadă prioritară, motiv pentru care cozile prioritare nu au o natură FIFO consistentă.

Legate de: Algoritmi pe care fiecare programator ar trebui să le cunoască

Programatorii pot implementa o coadă prioritară în mai multe moduri. O implementare simplă este de a utiliza o matrice cu un element de date struct / clasă, iar articolul de date va conține prioritatea fiecărui element de date și datele în sine. O altă implementare a cozii de prioritate primitive este utilizarea unei liste conectate. Cozile prioritare implementate prin liste legate sunt funcționale, dar nu sunt ideale datorită performanței lor.

Puteți implementa o coadă prioritară mai bună cu o grămadă. Dacă vă amintiți, grămezile binare dau elementul maxim sau minim în 0 (1) timp, iar inserarea durează doar 0 (logN) timp. Cu ajutorul grămezilor, cozile prioritare oferă o performanță mai bună asimptotic în comparație cu cozile sau tablourile.

O coadă prioritară are, de asemenea, o varietate de aplicații esențiale. Cozile prioritare sunt esențiale în algoritmii grafici, cum ar fi Prim's Minimum Spanning Tree și algoritmul lui Dijkstra Shortest Path. Ele sunt, de asemenea, ideale în algoritmi de planificare a proceselor de procesare a unității de procesare (CPU).

Aflați structurile de date

Cozile și cozile prioritare sunt structuri de date importante pentru toți începătorii. Este crucial ca studenții să se simtă confortabil să implementeze aceste structuri de date și să le folosească în diferite proiecte.

Alte structuri de date, cum ar fi grămezi, stive și copaci sunt la fel de importante pentru studenți și profesioniști. De asemenea, este foarte obișnuit ca intervievatorii să întrebe solicitanții cu privire la structurile de date.

După ce ați citit acest articol, ar trebui să aveți acum o idee bună despre cum funcționează cozile și cozile prioritare. Dacă totul pare încă puțin clar, veți fi la curent cu acestea pe măsură ce câștigați mai multă experiență folosindu-le.

Grămezi vs. Stive: Ce le separă?

Ați auzit de grămezi și stive, dar când ar trebui să folosiți unul peste altul?

Citiți în continuare

Despre autor