Vodič za početnike za razumijevanje redova i prioritetnih redova

Kao programer radit ćete s različitim strukturama podataka ovisno o opsegu vaših projekata. Jedan takav koncept je struktura podataka u redu čekanja; redovi su neophodni za studente i koriste se u mnogim važnim algoritmima. Poput redova, prioritetni redovi dijele sličan koncept, ali imaju nekoliko temeljnih razlika.

Čitajte dalje kako biste razumjeli redove i prioritetne redove.

Što je red čekanja?

Red je jednostavna struktura podataka koja ima različite primjene u projektima kodiranja u stvarnom životu. Strukture podataka su same po sebi apstraktne, ali radi jednostavnosti zamišljamo da struktura podataka u redu čekanja ima linearni oblik s dva različita kraja.

Što se tiče vremenske složenosti, red omogućuje umetanje (enqueue) i brisanje (dequeue) u O (1) vremenu. Zbog svoje asimptotske učinkovitosti, redovi su učinkoviti za velike skupove podataka. Redovi su po prirodi prvi-u-prvi-van (FIFO), što znači da će se prvo pristupiti stavci podataka koja se prva umetne. Nasuprot tome, hrpe imaju značajku posljednji-u-prvom-izlazu (LIFO) i imaju samo jedan otvoreni kraj.

Zamislite red karata u kinu; svaki novi kupac koji se pridruži pridružuje se redu s jednog kraja. Jedan po jedan, svaki kupac kupi kartu i napusti red s prednje strane. Struktura podataka o redu čekanja funkcionira baš kao i svaki red u stvarnom svijetu, a podaci se ubacuju (enqueue) na jedan kraj, a uklanjaju (dequeue) na drugom kraju. Nadamo se da sada možete razumjeti obrazloženje zašto redovi slijede FIFO metodologiju.

Red čekanja ima mnogo aplikacija za kodiranje u stvarnom životu. Češće se koristi u aplikacijama u kojima se podaci ne moraju odmah obraditi, već po FIFO redoslijedu. Zakazivanje diska, asinkroni prijenos podataka, semafori neke su tipične aplikacije. Zadaci planiranja "prvi stigao-prvi-posluži", poput premotavanja ispisa ili međuspremnika ulaznih uređaja, također koriste red.

Što je red prioriteta?

Red prioriteta sličan je redu, ali ima dodatna svojstva. Kad se element podataka stavi u red prioriteta, dobiva se prioritetni broj. Za razliku od dequeuinga standardnog reda, podatkovni elementi s visokim prioritetom se dequeuiraju prije podatkovnih elemenata s niskim prioritetom. Prioritet zamjenjuje redoslijed dolaska u red prioriteta, zbog čega redovi prioriteta nemaju dosljednu FIFO prirodu.

Povezano: Algoritmi koje bi trebao znati svaki programer

Programeri mogu implementirati red prioriteta na nekoliko načina. Jednostavna implementacija je korištenje niza sa podatkovnom stavkom struct/class, a stavka podataka sadržavat će prioritet svakog podatkovnog elementa i samih podataka. Druga primitivna primjena reda prioriteta je korištenje povezanog popisa. Redovi prioriteta implementirani putem povezanih popisa funkcionalni su, ali nisu idealni zbog svojih performansi.

Možete implementirati red s boljim prioritetom s hrpom. Ako se sjećate, binarne hrpe daju maksimalni ili minimalni element u 0 (1) vremenu, a umetanje traje samo 0 (logN) vremena. Uz pomoć hrpe, prioritetni redovi daju bolje performanse asimptotski u usporedbi s redovima ili nizovima.

Red prioriteta također ima niz bitnih aplikacija. Redovi prioriteta ključni su u algoritmima grafova kao što su Primovo stablo minimalnog raspona i Dijkstrin algoritam najkraće staze. Također su idealni u algoritmima za planiranje procesa računalnih procesnih jedinica (CPU).

Naučite strukture podataka

Redovi i redovi prioriteta važna su struktura podataka za sve početnike. Od ključne je važnosti da studenti udobno implementiraju te strukture podataka i koriste ih u različitim projektima.

Druge strukture podataka kao što su hrpe, hrpe i stabla jednako su važne za studente i stručnjake. Također je vrlo uobičajeno da anketari ispituju podnositelje zahtjeva o strukturama podataka.

Nakon što ste pročitali ovaj članak, trebali biste imati dobru ideju o tome kako redovi i prioritetni redovi rade. Ako vam se i dalje čini da je sve pomalo nejasno, uhvatit ćete se u koštac s njima kako stječete više iskustva u njihovoj upotrebi.

Hrpe vs. Hrpe: Što ih razlikuje?

Čuli ste za hrpe i hrpe, ali kada biste trebali koristiti jedno preko drugog?

Pročitajte Dalje

O autoru