U ovom članku ću vam reći šta je stog, kao i čemu služi i gdje se koristi.
Veliki broj problema vezanih za informaciju daje se otkucanom rješenju. Stoga nema ničeg iznenađujuće u činjenici da su za mnoge od njih metode, termini i opisi odavno izmišljeni. Na primjer, nije neuobičajeno čuti riječi poput stog. Zvuči veoma komplikovano, ali sve je mnogo jednostavnije.
stog je metoda predstavljanja podataka istog tipa (možete ga jednostavno nazvati tipom) u LIFO redoslijedu (Last In - First Out, što znači "prvi je došao - posljednji izašao"). Vrijedi napomenuti da se u ruskoj tehnologiji naziva i "prodavnica". I ne radi se o trgovini, već o trubi sa patronama za oružje, jer je princip vrlo sličan - prvi umetnuti patrona koristit će se zadnji.
Bilješka: Vrijedi znati da ova riječ može imati i druga značenja. Stoga, ako ne govorimo o kompjuterima, onda ima smisla razjasniti.
Da biste bolje razumjeli, dopustite mi da vam dam primjer iz stvarnog života. Recimo da imate hrpu listova. Svaki napisani list stavljate pored njega, a svaki sljedeći na ostale. Da biste dobili, na primjer, prvi list iz rezultirajućeg snopa, morate izvući sve ostale listove. Ovdje je, po istom principu, raspoređen stog. Odnosno, svaki posljednji dodani element postaje gornji, a da biste dobili, na primjer, prvi element, morate izvući sve ostale.
Čemu služi stek? Glavna svrha je rješavanje tipičnih problema gdje je potrebno održavati niz stanja nečega ili gdje je potrebna inverzna reprezentacija podataka (odnosno u suprotnom smjeru).
U računarstvu, stek se koristi u hardverskim uređajima (kao što je procesor), u operativnom sistemu i u mnogim programima. Ako uzmemo u obzir primjer koji je poznat skoro svima koji su se bavili programiranjem, onda bez steka rekurzija ne bi bila moguća, jer svaki put kada ponovo uđete u funkciju, potrebno je sačuvati trenutno stanje na vrhu, a svaki kada izađete iz funkcije, brzo vratite ovo stanje (to jest, samo LIFO sekvenca). A ako kopate još dublje, onda se u principu cijeli pristup pokretanju i izvršavanju programa zasniva na principu steka, gdje se prije nego što se izvrši sljedeći program pokrenut iz glavnog, stanje prethodnog se stavlja na stek pa se da kada pokrenuta aplikacija ili potprogram završi sa izvršavanjem, prethodni program nastavlja da radi normalno od mesta gde je stao.
Koje su operacije steka? Postoje samo dvije glavne operacije:
1. Poziva se dodavanje elementa na vrh steka guranje
2. Poziva se ekstrakcija gornjeg elementa pop
Ali, povremeno se možete sresti i sa implementacijom operacije čitanja gornjeg elementa bez njegovog izdvajanja - tzv peek.
Kako je stog organizovan? Stack se obično implementira na dva načina:
1. Korištenje niza i varijable koje pokazuju na ćeliju s vrhom steka
2. Korištenje povezanih lista
Svaka od ove 2 opcije ima svoje prednosti i nedostatke. Na primjer, povezane liste su sigurnije za korištenje jer je svaki dodat element smješten u dinamički kreiranu strukturu (nema problema s brojanjem stavki - nema sigurnosnih rupa koje bi omogućile slobodno kretanje u memoriji programa). Međutim, u smislu skladištenja i brzine korišćenja, oni su manje efikasni (zahtevaju dodatni prostor za pohranjivanje pokazivača; razbacani su u memoriji, a ne poređani jedan za drugim, kao u nizovima).
Sada znate šta je stek, kao i zašto je potreban i za šta se koristi.
Memorija koju koriste programi sastoji se od nekoliko dijelova − segmentima:
segment koda(ili "tekstualni segment") gdje se nalazi kompajlirani program. Segment koda je obično samo za čitanje;
bss segment(ili "neinicijalizirani segment podataka"), gdje su globalni i pohranjeni, inicijalizirani na nulu;
segment podataka(ili "inicijalizirani segment podataka"), gdje se pohranjuju inicijalizirane globalne i statičke varijable;
Tonastave(hrpa), odakle se dodjeljuju dinamičke varijable;
stek poziva, gdje se pohranjuju lokalne varijable i druge informacije vezane za funkciju.
U ovom vodiču ćemo pogledati samo hrpu i stek, jer se tu dešava sva zabava.
hrpa
segment gomile(ili jednostavno " hrpa") vodi evidenciju o memoriji koja se koristi za dinamičku dodjelu. Već smo malo pričali o hrpi u .
U C++, kada se koristi novi operator za dodjelu dinamičke memorije, ta se memorija dodjeljuje u segmentu hrpe same aplikacije.
int *ptr = novi int; // ptr dodjeljuje 4 bajta iz hrpe int *array = new int; // nizu je dodijeljeno 40 bajtova iz hrpe
Adresu memorije koja će se dodijeliti je proslijeđena od strane novog operatora i tada se može pohraniti u . Nema razloga da brinemo o mehanizmu za pohranjivanje i dodjelu slobodne memorije. Međutim, vrijedno je znati da uzastopni memorijski zahtjevi ne rezultiraju uvijek dodjelom uzastopnih memorijskih adresa!
int *ptr1 = novi int; int *ptr2 = novi int; // ptr1 i ptr2 možda nemaju uzastopne adrese
Kada se dinamički dodijeljena varijabla izbriše, memorija se vraća u hrpu i može se ponovo dodijeliti (na osnovu naknadnih zahtjeva). Zapamtite da brisanje pokazivača ne briše varijablu, već samo uzrokuje da se memorija na toj adresi vrati nazad u operativni sistem.
Gomila ima svoje prednosti i nedostatke:
Heap alokacija je relativno spora.
Dodijeljena memorija ostaje dodijeljena dok se ne oslobodi (čuvajte se curenja memorije) ili dok aplikacija ne prekine svoje izvršavanje (u tom trenutku OS mora vratiti memoriju).
Dinamički dodijeljenoj memoriji se pristupa samo preko pokazivača. Dereferenciranje pokazivača je sporije od direktnog pristupa varijabli.
Pošto je hrpa veliki rezervoar memorije, koristi se za dodeljivanje velikih ili klasa.
stek poziva
stek poziva(ili jednostavno " stog”) ima mnogo zanimljiviju ulogu. Stog poziva prati sve aktivne funkcije (one koje su pozvane, ali još nisu dovršene) od početka programa do trenutne točke izvršenja, i upravlja dodjelom svih parametara funkcije i lokalnih varijabli.
Stek poziva je implementiran kao struktura podataka "Stog". Stoga, prije nego što govorimo o tome kako radi stek poziva, moramo razumjeti šta je "Stak" kao struktura podataka.
Struktura podataka "Stog"
Struktura podataka je mehanizam u programiranju za organizovanje podataka tako da se mogu efikasno koristiti. Već ste vidjeli nekoliko tipova struktura podataka kao što su nizovi i strukture. Oni pružaju mehanizme za efikasno skladištenje podataka i pristup. Postoji mnogo više dodatnih struktura podataka koje se obično koriste u programiranju, od kojih su neke implementirane u C++ standardnoj biblioteci, a "Stack" je jedna od njih.
Razmislite o hrpi (slopu) tanjira na stolu. Budući da je svaki tanjir težak i da su naslagani (jedna na drugu), možete učiniti samo jednu od sljedeće tri stvari:
Pogledajte površinu gornje ploče.
Uzmite gornju ploču iz hrpe (tako ćete otkriti sljedeću na dnu - ako je uopće ima).
Stavite novu ploču na vrh hrpe (sakrivajući najgornju ploču ispod nje - ako je postojala).
U kompjuterskom programiranju, stek je struktura podataka nalik kontejneru koja sadrži više varijabli (slično nizu). Međutim, dok vam niz omogućava pristup i modificiranje elemenata bilo kojim redoslijedom (koji se naziva " slučajni pristup”), tada je stog ograničeniji. Operacije koje se mogu izvesti na steku odgovaraju trima gore navedenim. Na hrpi možete:
Pogledajte gornji element na steku (pomoću funkcije top() ili peek() ).
Iskoči gornji element steka (pomoću funkcije pop() ).
Dodajte novi element na vrh steka (pomoću funkcije guranje() ).
Stack je struktura poput LIFO(Last In, First Out - zadnji ušao, prvi izašao). Posljednji element postavljen na vrh hrpe bit će prvi element koji će iskočiti iz hrpe. Ako stavite novi tanjir na hrpu drugih tanjira, on će biti prvi koji ćete uzeti. Kako se elementi postavljaju na stog, stog raste; kako se elementi uklanjaju iz hrpe, stog se smanjuje.
Na primjer, razmislite o kratkom nizu koji pokazuje kako funkcionira dodavanje i uklanjanje na hrpu:
stog: prazan
Gurnite 1
hrpa: 1
Gurnite 2
Stog: 1 2
Gurnite 3
Stog: 1 2 3
Gurnite 4
hrpa: 1 2 3 4
Pop
Stog: 1 2 3
Pop
Stog: 1 2
Pop
hrpa: 1
Hrpa ploča je prilično dobra analogija za to kako snop radi, ali postoji i bolja analogija. Na primjer, razmotrite nekoliko poštanskih sandučića koji su naslagani jedan na drugi. Svaki poštanski sandučić može sadržavati samo jednu stavku, a svi sandučići su u početku prazni. Osim toga, svako poštansko sanduče je prikovano za dno sandučića, tako da se broj poštanskih sandučića ne može mijenjati. Ako ne možemo promijeniti broj poštanskih sandučića, kako onda postići ponašanje poput steka?
Prvo, koristimo naljepnicu da označimo gdje je najdonji prazan poštanski sandučić. Na početku, ovo će biti prvi poštanski sandučić koji se nalazi na podu. Kada dodamo stavku u našu gomilu poštanskog sandučeta, stavit ćemo tu stavku u poštansko sanduče na kojem će biti naljepnica (tj. prvo prazno poštansko sanduče na podu), a zatim pomaknuti naljepnicu za jedno poštansko sanduče. Kada izbacimo stavku iz hrpe, pomjerimo naljepnicu za jedno poštansko sanduče prema dolje i uklonimo stavku iz poštanskog sandučeta. Sve ispod markera je na hrpi. Sve što se nalazi u kutiji sa naljepnicama i iznad nije u hrpi.
segment steka poziva
Segment steka poziva sadrži memoriju koja se koristi za stek poziva. Kada se aplikacija pokrene, operativni sistem gura funkciju main() na stek poziva. Tada program počinje da se izvršava.
Kada program naiđe na poziv funkcije, ta funkcija se gura u stek poziva. Kada se funkcija završi, uklanja se iz steka poziva. Dakle, gledajući funkcije dodane u stog, možemo vidjeti sve funkcije koje su pozvane do trenutne točke izvršenja.
Analogija našeg poštanskog sandučeta je zapravo način na koji radi stek poziva. Stek poziva ima fiksni broj memorijskih adresa (fiksna veličina). Poštanski sandučići su memorijske adrese i pozivaju se "elementi" koje dodamo i iskočimo na stog okviri(ili više " osoblje") steka. Okvir steka prati sve podatke povezane s jednim pozivom funkcije. "Naljepnica" je registar (mali komad memorije u CPU-u), tj pokazivač steka. Pokazivač steka prati gdje se nalazi vrh steka poziva.
Jedina razlika između stvarnog steka poziva i našeg hipotetičkog steka poštanskog sandučeta je u tome što kada izbacimo stavku iz steka poziva, ne moramo da obrišemo memoriju (tj. iskočimo sav sadržaj poštanskog sandučeta). Možemo samo ostaviti ovu memoriju za sljedeći element, koji će ga prepisati. Pošto će pokazivač steka biti ispod ove memorijske adrese, tada, kao što već znamo, ova memorijska lokacija neće biti na steku.
Stack poziva u praksi
Pogledajmo bliže kako radi stek poziva. Ispod je redoslijed koraka koji se poduzimaju kada se funkcija pozove:
Program nailazi na poziv funkcije.
Okvir steka se kreira i gura na stek, sastoji se od:
Adresa instrukcije koja stoji iza poziva funkcije (tzv. povratna adresa"). Dakle, procesor pamti gdje da se vrati nakon izvršavanja funkcije.
Argumenti funkcije.
Memorija za lokalne varijable.
Sačuvane kopije svih registara koje je modificirala funkcija koje će trebati vratiti nakon što funkcija završi svoje izvršavanje.
Procesor skače na početnu tačku izvršenja funkcije.
Instrukcije unutar funkcije počinju da se izvršavaju.
Nakon što se funkcija završi, izvode se sljedeći koraci:
Registri se vraćaju iz steka poziva.
Okvir steka je iskočio iz steka. Oslobađa se memorija svih lokalnih varijabli i argumenata.
Povratna vrijednost je obrađena.
CPU nastavlja izvršavanje koda (na osnovu povratne adrese).
Povratne vrijednosti mogu se obraditi na različite načine, ovisno o arhitekturi računala. Neke arhitekture smatraju da je povratna vrijednost dio okvira steka. Drugi koriste procesorske registre.
Poznavanje svih detalja o tome kako radi stek poziva nije toliko važno. Međutim, razumijevanje da se funkcije dodaju u stog kada se pozovu i uklanjaju iz steka kada završe izvršenje pruža osnove potrebne za razumijevanje rekurzije, kao i neke druge koncepte koji su korisni u .
Primjer steka poziva
Razmotrite sljedeći isječak koda:
Stack poziva ovog programa izgleda ovako:
boo() (uključujući b parametar)
main()
Stack Overflow
Stog ima ograničenu veličinu i stoga može sadržavati samo ograničenu količinu informacija. Za Windows, zadana veličina steka je 1 MB. Na nekim drugim Unix sistemima, ova veličina može biti do 8 MB. Ako program pokuša staviti previše informacija u stog, to će rezultirati prelivanjem steka. Stack Overflow(preklapanje steka) se javlja kada se napravi zahtjev za memorijom, u vrijeme kada je sva memorija steka već dodijeljena - u ovom slučaju, svi zahtjevi za dodjelu će početi da se prelijevaju (prelijevaju) u druge dijelove memorije.
Prelijevanje steka rezultat je dodavanja previše varijabli u stog i/ili kreiranja previše ugniježđenih poziva funkcija (npr. gdje funkcija A poziva funkciju B koja zauzvrat poziva funkciju C koja poziva funkciju D, itd. itd.). Prekoračenje steka obično uzrokuje pad programa.
Na primjer:
int main() (int stack; vrati 0;)
int main() int stack [ 100000000 ] ; return 0 ; |
Ovaj program pokušava da gurne ogroman niz u stek poziva. Budući da stek nije dovoljno velik za obradu takvog niza, njegovo dodavanje ide u druge dijelove memorije koje program ne može koristiti. Dakle, dobijamo neuspjeh.
Evo još jednog programa koji će uzrokovati prelijevanje steka, ali iz drugog razloga:
void boo() ( boo(); ) int main() ( boo(); vrati 0; )
(Engleski last in - first out, "last in - first out").
Najčešće se princip hrpe uspoređuje sa hrpom ploča: da biste uzeli drugu s vrha, morate ukloniti gornji.
U nekim jezicima (npr. Lisp, Python) bilo koja lista se može nazvati stekom, budući da su pop i push operacije dostupne za njih. U jeziku C++, standardna biblioteka ima klasu sa implementiranom strukturom i metodama. itd.
Softverski stog
Organizacija u pamćenju
Stek se često implementira kao jednostruko povezana lista (svaki element na listi sadrži, pored informacija pohranjenih na steku, pokazivač na sljedeći element steka).
Ali takođe je uobičajeno da stek bude u jednodimenzionalnom nizu sa uređenim adresama. Takva organizacija steka je zgodna ako informacijski element zauzima fiksni broj riječi u memoriji, na primjer, 1 riječ. Ovo eliminiše potrebu za pohranjivanjem eksplicitnog pokazivača na sljedeći element steka u elementu steka, čime se štedi memorija. U ovom slučaju, pokazivač steka ( pokazivač steka, - SP) je obično registar procesora i ukazuje na adresu glave steka.
Pretpostavimo na primjer da se glava steka nalazi na nižoj adresi, sljedeći elementi se nalaze na rastućim adresama. Svaki put kada se riječ ubaci u stek, SP se prvo smanjuje za 1, a zatim se adresa u SP upisuje u memoriju. Svaki put kada se riječ iskoči iz steka (iskače), trenutna adresa se prvo čita iz SP-a, a zatim se sadržaj SP-a povećava za 1.
Kada organizujete stek u obliku jednostruko usmerene liste, vrednost varijable steka je pokazivač na njen vrh - adresu vrha. Ako je stog prazan, tada je vrijednost pokazivača NULL.
Primjer implementacije steka u C:
struct stack ( char * podaci ; struct stack * sljedeći ; );
Stack operacije
Postoje tri operacije na steku: dodavanje elementa (aka push), uklanjanje elementa (pop) i čitanje elementa glave (peek).
Guranjem se dodaje novi element koji pokazuje na element koji je prethodno bio glava. Novi element sada postaje element glave.
Kada se element ukloni (pop ), prvi se uklanja, a onaj na koji je ovaj objekt imao pokazivač (sljedeći element) postaje glavni. Vraća se vrijednost uklonjenog elementa.
void push ( STACK * ps , int x ) // Dodavanje novog elementa u stog( if ( ps -> size == STACKSIZE ) // Je li stek prepun?( fputs ( "Greška: prekoračenje steka \n " , stderr); prekinuti (); ) else ( ps -> stavke [ ps -> size ++ ] = x ; ) ) int pop ( STACK * ps ) // Uklanjanje iz steka( ako ( ps -> veličina == 0 ) // Je li stek prazan?( fputs ( "Greška: stack underflow \n " , stderr); prekinuti (); ) else ( vrati ps -> stavke [ -- ps -> veličina ]; ) )
Područje primjene
Programski prikaz steka se koristi za prelazak struktura podataka, kao što su stablo ili graf. Kada se koriste rekurzivne funkcije, koristit će se i stek, ali njegov hardverski oblik. Pored ovih namena, stek se koristi za organizovanje mašine za stek koja sprovodi proračune u obrnutoj poljskoj notaciji.
Stek poziva se koristi za praćenje povratnih tačaka iz potprograma.
Ideja steka se koristi u stroju za stek među programskim jezicima steka.
Upotreba steka pojednostavljuje i ubrzava rad programa, jer se na istoj adresi pristupa više podataka.
hardverski stog
Prije upotrebe steka, on se mora inicijalizirati tako da SS:ESP registri upućuju na adresu glave steka u području fizičke RAM-a, a potreban broj memorijskih ćelija mora biti rezerviran za pohranjivanje podataka na stek (očigledno je da se stek u ROM-u, naravno, ne može organizovati). Aplikacioni programi, po pravilu, od operativnog sistema dobijaju stek spreman za upotrebu. U zaštićenom režimu procesora, segment stanja zadataka sadrži četiri selektora segmenta steka (za različite nivoe privilegija), ali se istovremeno koristi samo jedan stek.
Bilješke
- Turingova mašina: Uvod (neodređeno) . Pristupljeno 12. februara 2013.
Red
Red kao struktura podataka razumljiv je čak i ljudima koji nisu upoznati sa programiranjem. Red sadrži elemente, kao da su poređani jedan za drugim u lancu. Red ima početak i kraj. Nove elemente možete dodati samo na kraj reda, možete uzeti elemente samo od početka. Za razliku od običnog reda, koji se uvijek može ostaviti po želji, elementi se ne mogu ukloniti iz sredine redosleda programera.
Red se može predstaviti kao cijev. Kuglice se mogu dodavati na jedan kraj cijevi - elementi reda, a uklanjaju se s drugog kraja. Elementi u sredini reda, tj. kuglice unutar cijevi nisu dostupne. Kraj epruvete u koji se dodaju kuglice odgovara kraju reda, kraj iz kojeg se uklanjaju odgovara početku reda. Dakle, krajevi cijevi nisu simetrični, kuglice unutar cijevi kreću se samo u jednom smjeru.
U principu, može se dozvoliti da se elementi dodaju na oba kraja reda i da se uzimaju i sa oba kraja. Takva struktura podataka postoji i u programiranju, njen naziv je "dec", sa engleskog. Dvostruki red čekanja, tj. red sa dva kraja. Dec se koristi mnogo rjeđe nego red čekanja.
Upotreba reda u programiranju gotovo odgovara njegovoj ulozi u svakodnevnom životu. Red je gotovo uvijek povezan sa zahtjevima za servisiranje, u slučajevima kada oni ne mogu biti ispunjeni trenutno. Red takođe održava redosled kojim se zahtevi serviraju. Razmotrite, na primjer, šta se dešava kada osoba pritisne tipku na tastaturi računara. Dakle, osoba traži od računara da izvrši neku radnju. Na primjer, ako jednostavno ispisuje tekst, tada bi radnja trebala biti dodavanje jednog znaka u tekst, a može biti praćena ponovnim iscrtavanjem područja ekrana, pomicanjem prozora, preoblikovanjem pasusa i tako dalje.
Bilo koji, čak i najjednostavniji operativni sistem je u određenoj mjeri uvijek multitasking. To znači da u trenutku kada se pritisne tipka, operativni sistem može biti zauzet nekim drugim poslom. Međutim, operativni sistem ni pod kojim okolnostima nema pravo da ignoriše pritisak na taster. Zbog toga se računar prekida, pamti svoje stanje i prelazi na obradu pritiska na taster. Takva obrada treba da bude vrlo kratka kako ne bi ometala druge zadatke. Komanda data pritiskom na tipku jednostavno se dodaje na kraj reda zahtjeva koji čekaju da se izvrše. Nakon toga prekid se završava, računar vraća svoje stanje i nastavlja rad koji je prekinut pritiskom na tipku. Zahtjev u redu čekanja neće biti izvršen odmah, već samo kada dođe na red.
U Windows-u, prozorske aplikacije se oslanjaju na poruke koje se šalju tim aplikacijama. Na primjer, postoje poruke o pritiskanju tipke miša, o zatvaranju prozora, o potrebi da se ponovo iscrta oblast prozora, o odabiru stavke menija i tako dalje. Svaki program ima red zahtjeva. Kada program primi svoj odsječak vremena izvršenja, odabire sljedeći zahtjev iz glave reda i izvršava ga. Dakle, posao prozorske aplikacije je, pojednostavljeno rečeno, sekvencijalno izvršavanje zahtjeva iz njenog reda. Red se održava od strane operativnog sistema.
Pristup programiranju koji ne poziva procedure direktno, već šalje poruke koje se unose red zahtjeva, ima mnoge prednosti i jedno je od obilježja objektno orijentiranog programiranja. Tako, na primjer, ako se prozorski program iz nekog razloga mora prekinuti, najbolje je ne izdavati odmah naredbu za završetak, što je opasno jer narušava logiku rada i može dovesti do gubitka podataka. Umjesto toga, program sam sebi šalje poruku o isključivanju koja će biti isporučena red zahtjeva i završeno nakon prethodnih zahtjeva.
Implementacija reda na bazi niza
Kao što je već spomenuto, niz se daje programeru odozgo, sve ostale strukture podataka moraju biti implementirane na njegovoj osnovi. Naravno, takva implementacija može biti višestepena, a niz ne djeluje uvijek kao direktna baza implementacije. U slučaju reda čekanja, dvije implementacije su najpopularnije: kontinuirano zasnovano na nizu, koje se naziva i implementacija zasnovana na prstenastom baferu, i referentna implementacija, ili implementacija zasnovana na listi. Referentne implementacije bit će riječi u nastavku.
Uz kontinuiranu implementaciju reda, baza je niz fiksne dužine N, tako da je red ograničen i ne može sadržavati više od N elemenata. Indeksi elemenata niza variraju od 0 do N-1. Pored niza, implementacija reda pohranjuje tri jednostavne varijable: indeks početka reda, indeks kraja reda, broj elemenata reda. Elementi reda su sadržani u rasponu niza od početnog indeksa do krajnjeg indeksa.
Prilikom dodavanja novog elementa na kraj reda, krajnji indeks se prvo povećava za jedan, a zatim se novi element upisuje u ćeliju niza s ovim indeksom. Slično, kada se izvlači element iz glave reda, sadržaj ćelije niza s indeksom glave reda se pohranjuje kao rezultat operacije, a zatim se indeks glave reda povećava za jedan . I početni i krajnji indeks pomiču se s lijeva na desno tijekom rada. Šta se dešava kada indeks kraja reda dođe do kraja niza, tj. N-1?
Ključna ideja implementacije reda čekanja je da je niz mentalno, takoreći, upetljan u prsten. Smatra se da iza posljednjeg elementa niza slijedi njegov prvi element (podsjetimo da posljednji element ima indeks N - 1, a prvi - indeks 0). Prilikom pomicanja indeksa kraja reda udesno, u slučaju kada pokazuje na posljednji element niza, on skače na prvi element. Dakle, kontinuirani segment niza koji zauzimaju elementi reda može proći kroz kraj niza do njegovog početka.
Stack
Stog je najpopularnija i vjerovatno najvažnija struktura podataka u programiranju. Stog je uređaj za pohranu iz kojeg se stavke iskaču obrnutim redoslijedom kojim su dodane. To je kao pogrešan red, u kojem prvi služi onog ko je zadnji ušao. U programskoj literaturi opšte su prihvaćene skraćenice koje označavaju disciplinu reda i steka. Disciplina reda je označena FIFO, što znači prvi ušao - prvi izašao (First In First Out). Disciplina steka je označena sa LIFO, posljednji ušao prvi je izašao (Last In First Out).
Stog se može zamisliti kao cijev sa dnom oprugom postavljenim okomito. Gornji kraj cijevi je otvoren, možete dodati ili, kako kažu, gurnuti elemente u njega. Općenito prihvaćeni engleski termini u tom pogledu su vrlo šareni, operacija dodavanja elementa u stog označava se sa push, što znači "push, shove". Novododani element gura elemente koji su prethodno gurnuti na stog jednu poziciju prema dolje. Kada se elementi uklone iz steka, izgledaju kao da su gurnuti prema gore, na engleskom pop ("pucaj").
Primjer hrpe je plast sijena, hrpa papira na stolu, hrpa tanjira i tako dalje. Otuda i naziv steka, što na engleskom znači stek. Ploče se uklanjaju iz hrpe obrnutim redoslijedom kojim su dodane. Dostupan je samo gornji činele, tj. ploča na vrhu hrpe. Dobar primjer bi također bila željeznička slijepa ulica u koju se mogu slagati vagoni.
Korištenje steka u programiranju
Stack se koristi prilično često iu raznim situacijama. Objedinjuje ih sljedeći cilj: trebate sačuvati neki posao koji još nije završen do kraja, ako se trebate prebaciti na drugi zadatak. Stog se koristi za privremeno pohranjivanje stanja nedovršenog posla. Nakon što sačuva stanje, računar se prebacuje na drugi zadatak. Na kraju njegovog izvršenja, stanje zadatka na čekanju se vraća iz steka, a računar nastavlja prekinuti rad.
Zašto se stog koristi za pohranjivanje stanja prekinutog posla? Pretpostavimo da računar radi zadatak A. U procesu njegovog izvršenja postaje neophodno izvršiti zadatak B. Stanje zadatka A se pamti i računar nastavlja da izvršava zadatak B. Ali na kraju krajeva, čak i kada izvršava zadatak B, računar se može prebaciti na drugi zadatak C i biće potrebno sačuvati stanje zadatka B pre nego što se pređe na C. Kasnije, na kraju C, prvo će se vratiti stanje zadatka B, a zatim će se na kraju B vratiti stanje zadatka A. Dakle, obnavljanje se događa obrnutim redoslijedom od spremanja, što odgovara disciplini steka.
Stek vam omogućava da organizujete rekurziju, tj. pozivanje potprograma sebi, bilo direktno ili kroz lanac drugih poziva. Neka, na primjer, potprogram A izvrši algoritam koji ovisi o ulaznom parametru X i, eventualno, o stanju globalnih podataka. Za najjednostavnije vrijednosti X, algoritam se implementira direktno. Za složenije X vrijednosti, algoritam se implementira kao redukcija na primjenu istog algoritma na jednostavnije X vrijednosti. U ovom slučaju, potprogram A poziva sam sebe, prenoseći jednostavniju vrijednost X kao parametar. Sa ovim pozivom, prethodna vrijednost parametra X, kao i sve lokalne varijable potprograma A, pohranjuju se na stek. Zatim se kreira novi skup lokalnih varijabli i varijabla koja sadrži novu (jednostavniju) vrijednost parametra X. Pozvani potprogram A radi na novom skupu varijabli bez uništavanja prethodnog skupa. Na kraju poziva, stari skup lokalnih varijabli i staro stanje ulaznog parametra X se vraćaju iz steka, a potprogram se nastavlja tamo gdje je stao.
U stvari, ne morate čak ni da spremate vrednosti lokalnih varijabli potprograma na stog na poseban način. Činjenica je da lokalne varijable potprograma (tj. njegove unutrašnje, radne varijable, koji se kreiraju na početku njegovog izvršavanja i uništavaju na kraju) se stavljaju na stek implementiran u hardveru zasnovanom na konvencionalnoj RAM memoriji. Na samom početku rada, potprogram zauzima mjesto na steku za svoje lokalne varijable, ovaj dio memorije na hardverskom steku se obično naziva blok lokalnih varijabli ili na engleskom okvir("okvir"). U trenutku završetka, potprogram oslobađa memoriju uklanjanjem bloka svojih lokalnih varijabli iz steka.
Pored lokalnih varijabli, povratne adrese za pozive potprograma su pohranjene na hardverskom stogu. Neka potprogram bude pozvan u nekom trenutku programa A B. Prije nego što se pozove potprogram B, adresa instrukcije koja slijedi nakon instrukcije poziva B se pohranjuje u stog. Ova tzv povratna adresa za program A. Kada je potprogram B gotov, iskakanje povratne adrese programa A iz steka i vraćanje kontrole na tu adresu. Dakle, računar nastavlja izvršavanje programa A, počevši od instrukcije koja slijedi nakon instrukcije poziva. Većina procesora ima posebne instrukcije koje podržavaju pozivanje potprograma sa povratnom adresom postavljenom na stog i vraćanje iz potprograma na adresu iskačenu iz steka. Obično se naredba poziva zove call, a naredba za povratak je return.
Parametri potprograma ili funkcije se također stavljaju na stog prije nego što se pozovu. Redosled kojim se postavljaju na stog zavisi od konvencija u jezicima visokog nivoa. Dakle, u C ili C++, prvi argument funkcije je na vrhu steka, drugi je ispod njega, i tako dalje. U Pascalu je obrnuto, na vrhu steka je posljednji argument funkcije. (Tako da su, usput, varijable funkcije poput printf moguće u C, ali ne u Pascalu.)
U Fortranu-4, jednom od najstarijih i najuspješnijih programskih jezika, argumenti se prolaze kroz posebno područje memorije, koje se možda ne nalazi na steku, jer je do kraja 70-ih godina XX vijeka još uvijek bilo računara kao što su IBM 360 ili EC računari bez hardverske implementacije. Povratne adrese su također pohranjene ne na stog, već na fiksne memorijske lokacije za svaki potprogram. Programeri takvu memoriju nazivaju statičkom u smislu da statičke varijable uvijek zauzimaju isto mjesto u memoriji u bilo koje vrijeme kada se program izvodi. Kada se koristi samo statička memorija, rekurzija nije moguća, jer se prethodne vrijednosti lokalnih varijabli uništavaju pri novom pozivu. U referentnom Fortranu-4 korištene su samo statičke varijable, a rekurzija je zabranjena. Do sada se jezik Fortran široko koristio u naučnim i inženjerskim proračunima, međutim, moderni Fortran-90 standard već uvodi memoriju steka, eliminirajući nedostatke ranijih verzija jezika.
Implementacija steka zasnovana na nizu
Implementacija steka zasnovana na nizu je klasik programiranja. Ponekad čak ni sam koncept steka nije sasvim ispravno identificiran sa ovom implementacijom.
Osnova implementacije je niz veličine N, tako da se implementira stek ograničene veličine čija maksimalna dubina ne može preći N. Indeksi ćelija niza variraju od 0 do N-1. Elementi steka se pohranjuju u niz na sljedeći način: element na dnu steka nalazi se na početku niza, tj. na indeksu ćelije 0. Element iznad najnižeg elementa steka se pohranjuje na indeks ćelije 1, i tako dalje. Vrh steka je pohranjen negdje u sredini niza. Indeks elementa na vrhu steka pohranjen je u posebnoj varijabli, koja se obično naziva pokazivač N - 1 . Elementi steka zauzimaju neprekidni deo niza, počevši od ćelije čiji je indeks pohranjen u pokazivaču steka i završavajući poslednjom ćelijom u nizu. U ovoj varijanti, stek raste u smjeru opadanja indeksa. Ako je stek prazan, tada pokazivač steka sadrži vrijednost N (koja je za jedan veći od indeksa posljednje ćelije u nizu).
Stog je kolekcija čiji se elementi preuzimaju po principu "poslednji ušao, prvi izašao". (Last-In-First-Out ili LIFO). To znači da ćemo imati pristup samo posljednjem dodanom elementu.
Za razliku od lista, ne možemo pristupiti proizvoljnom elementu steka. Elemente možemo dodati ili ukloniti samo pomoću posebnih metoda. Stog također nema Contains metodu kao što to imaju liste. Takođe, stek nema iterator. Da bismo razumjeli zašto je stek toliko ograničen, pogledajmo kako funkcionira i kako se koristi.
Najčešća analogija za objašnjenje hrpe je hrpa ploča. Bez obzira koliko ploča ima u hrpi, uvijek možemo ukloniti gornju. Čiste tanjire se postavljaju na vrh hrpe na isti način, a mi ćemo uvek prvi uzeti tanjir koji je poslednji postavljen.
Ako spustimo, na primjer, crvenu ploču, pa plavu, pa zelenu, onda ćemo prvo morati ukloniti zelenu, pa plavu i na kraju crvenu. Glavna stvar koju treba zapamtiti je da se ploče uvijek postavljaju na vrh hrpe. Kada neko uzme tanjir, skine ga i odozgo. Ispada da se ploče rastavljaju obrnutim redoslijedom od onog u kojem su postavljene.
Sada kada smo shvatili kako radi stek, uvedemo neke pojmove. Operacija dodavanja elementa u stog naziva se "push", uklanjanje - "pop". Posljednji dodani element naziva se vrh steka ili "vrh" i može se vidjeti pomoću operacije "peek". Pogledajmo sada stub klase koja implementira stek.
Stack klasa
Klasa Stack definira Push, Pop, Peek metode za pristup elementima i polje Count. U implementaciji ćemo koristiti LinkedList
Javna klasa Stack ( LinkedList _items = new LinkedList(); public void Push(T vrijednost) (baci novi NotImplementedException(); ) public T Pop() (baci novi NotImplementedException(); ) public T Peek() (baci novi NotImplementedException( ); ) public int Count ( get; ) )
Push metoda
- ponašanje: Dodaje element na vrh hrpe.
- složenost: O(1).
Pošto koristimo povezanu listu za skladištenje elemenata, možemo samo dodati novu na kraj liste.
Public void Push(T vrijednost) (_items.AddLast(value); )
Pop metoda
- ponašanje: Uklanja element sa vrha steka i vraća ga. Ako je stog prazan, izbacuje InvalidOperationException .
- složenost: O(1).
Push dodaje elemente na kraj liste, tako da će ih pokupiti i s kraja. Ako je lista prazna, bit će izbačen izuzetak.
Public T Pop() ( if (_items.Count == 0) ( izbaci novi InvalidOperationException("Stog je prazan"); ) T rezultat = _items.Tail.Value; _items.RemoveLast(); vrati rezultat; )
Peek Method
- ponašanje: Vraća gornji element steka, ali ga ne uklanja. Ako je stog prazan, izbacuje InvalidOperationException .
- složenost: O(1).
Count Method
- ponašanje: Vraća broj elemenata na steku.
- složenost: O(1).
Zašto trebamo znati koliko elemenata ima na steku ako im ionako nemamo pristup? Sa ovim poljem možemo provjeriti ima li elemenata na steku ili je prazan. Ovo je vrlo korisno s obzirom na to da Pop metoda izbacuje izuzetak.
Primjer: kalkulator u obrnutoj notaciji.
Klasičan primjer korištenja steka je kalkulator u obrnutoj poljskoj ili postfiksnoj notaciji. U njemu je napisan operator poslije njihove operande. Odnosno, pišemo:
<операнд> <операнд> <оператор>
umjesto tradicionalnog:
<операнд> <оператор> <операнд>
Drugim riječima, umjesto "4 + 2" pisaćemo "4 2 +". Ako vas zanima porijeklo obrnute poljske notacije i njeno ime, možete saznati o tome na Wikipediji ili u tražilici.
Kako se izračunava obrnuta poljska notacija i zašto je stek toliko koristan kada se koristi, može se jasno vidjeti iz sljedećeg algoritma:
Za svaku ulaznu vrijednost, ako je vrijednost cijeli broj, gurnite vrijednost na stog operanda, inače ako je vrijednost operator, iskoči lijevu i desnu vrijednost iz steka procijeni operator gurne rezultat na stog iskoči odgovor iz steka .
To jest, za izraz "4 2 +" radnje će biti sljedeće:
push(4) push(2) push(pop() + pop())
Na kraju će biti jedna vrijednost na steku - 6.
Slijedi kompletan kod za jednostavan kalkulator koji čita izraz (npr. 4 2 +) sa konzole, dijeli unos na razmake (["4", "2", "+"]) i izvršava algoritam izračuna . Računanje se nastavlja sve dok se ne naiđe na riječ quit.
Void RpnLoop() ( while (true) (Console.Write("> "); string input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") ( break; ) // Stog vrijednosti još nije obrađen. Vrijednosti stog = new Stack(); foreach (token niza u input.Split(new char ( " " ))) ( // Ako je vrijednost cijeli broj... int vrijednost; if (int. TryParse(token, out value)) ( // ... gurnite ga na stog. values.Push(value); ) else ( // inače, izvršite operaciju... int rhs = vrijednosti .Pop(); int lhs = values.Pop(); // ... i vratimo rezultat u. switch (token) ( case "+": values.Push(lhs + rhs); break; case "- ": vrijednosti.Push(lhs - rhs ); prekid; slučaj "*": vrijednosti.Push(lhs * rhs); prekid; slučaj "/": vrijednosti.Push(lhs / rhs); prekid; slučaj "%": values.Push(lhs % rhs); break; default: // Ako operacija nije +, -, * ili / izbaci novi ArgumentException(string.Format("Neprepoznati token: (0)", token)); ) ) ) // Zadnji element na steku je rezultat Console.WriteLine(values.Pop()); ) )
Red
Redovi su vrlo slični stogovima. Oni također ne daju pristup proizvoljnom elementu, ali, za razliku od steka, elementi se stavljaju (u redu) i penjati se (u redu) sa raznih krajeva. Ova metoda se zove "prvi ušao, prvi izašao" (First-In-First-Out ili FIFO). To jest, mi ćemo uzeti elemente iz reda u istom redoslijedu u koji smo ih stavili. Kao pravi red ili pokretna traka.
Redovi se često koriste u programima za obezbjeđivanje bafera u koji se element može smjestiti za dalju obradu, čuvajući redoslijed dolaska. Na primjer, ako baza podataka podržava samo jednu vezu, možete koristiti red niti koje će, začudo, čekati svoj red za pristup bazi podataka.
Klasa u redu čekanja
Klasa Queue, kao i stek, biće implementirana pomoću povezane liste. On će pružiti metode Enqueue za dodavanje elementa, Dequeue za uklanjanje, Peek i Count . Kao i klasa Stack, ona neće implementirati ICollection interfejs
Public class Queue ( LinkedList _items = new LinkedList(); public void Enqueue(T vrijednost) (baci novi NotImplementedException(); ) public T Dequeue() (baci novi NotImplementedException(); ) public T Peek() (baci novi NotImplementedException( ); ) public int Count ( get; ) )
Metoda čekanja
- ponašanje: Dodaje element u red čekanja.
- složenost: O(1).
Novi elementi reda mogu se dodati i na početak i na kraj liste. Važno je samo da se elementi isporučuju sa suprotne ivice. U ovoj implementaciji, dodaćemo nove elemente na početak interne liste.
Public void Enqueue (T vrijednost) ( _items.AddFirst(value); )
Metoda dequeue
- ponašanje: Uklanja prvi gurnuti element iz reda čekanja i vraća ga. Ako je red prazan, izbacuje InvalidOperationException .
- složenost: O(1).
Pošto elemente ubacujemo na početak liste, uklonićemo ih sa kraja. Ako je lista prazna, izbacuje se izuzetak.
Public T Dequeue() ( if (_items.Count == 0) (baci novi InvalidOperationException("Red je prazan"); ) T last = _items.Tail.Value; _items.RemoveLast(); vrati zadnji; )
Peek Method
- ponašanje: Vraća element koji će vratiti sljedeći poziv metode Dequeue. Red ostaje nepromijenjen. Ako je red prazan, izbacuje InvalidOperationException .
- složenost: O(1).
Count Method
- ponašanje:
- složenost: O(1).
Dvosmjerni red
Dvosmjerni red (dvostrani red), ili dec (deque), proširuje ponašanje reda. U nizu možete dodavati ili uklanjati elemente i s početka i s kraja reda. Ovo ponašanje je korisno u mnogim zadacima, kao što je planiranje izvođenja niti ili implementacija drugih struktura podataka. Kasnije ćemo pogledati kako se stek može implementirati koristeći deque.
Deque class
Deque klasa se najlakše implementira korištenjem dvostruko povezane liste. Omogućava vam pregled, brisanje i dodavanje stavki na početak i kraj liste. Glavna razlika između dequea i regularnog niza je u tome što su metode Enqueue, Dequeue i Peek podijeljene u parove kako bi radile na oba kraja liste.
Javna klasa Deque ( LinkedList _items = new LinkedList(); public void EnqueueFirst(T vrijednost) (baci novi NotImplementedException(); ) public void EnqueueLast(T vrijednost) (baci novi NotImplementedException(); ) public T DequeueFirst( ) (baci novi NotImplementedException(); ) public T DequeueLast() (baci novi NotImplementedException(); ) public T PeekFirst() (baci novi NotImplementedException(); ) public T PeekLast() (baci novi NotImplementedException(); ) public int Računaj (dobi; ))
EnqueueFirst Method
- ponašanje:
- složenost: O(1).
EnqueueLast Method
- ponašanje:
- složenost: O(1).
DequeueFirst metoda
- ponašanje: Uklanja element s prednje strane reda i vraća ga. Ako je red prazan, izbacuje InvalidOperationException .
- složenost: O(1).
DequeueLast metoda
- ponašanje:
- složenost: O(1).
PeekFirst Method
- ponašanje: Vraća element iz glave reda bez modifikacije. Ako je red prazan, izbacuje InvalidOperationException .
- složenost: O(1).
PeekLast metoda
- ponašanje:
- složenost: O(1).
Count Method
- ponašanje: Vraća broj elemenata u redu, ili 0 ako je red prazan.
- složenost: O(1).
Primjer: implementacija steka
Deque se često koristi za implementaciju drugih struktura podataka. Pogledajmo primjer implementacije steka pomoću njega.
Možda se pitate zašto implementirati stek zasnovan na redu čekanja umjesto povezane liste. Dva su razloga: performanse i ponovna upotreba koda. Povezana lista ima troškove kreiranja čvorova i nema garancije za lokalizaciju podataka: elementi se mogu nalaziti bilo gdje u memoriji, što uzrokuje veliki broj promašaja i degradaciju performansi na nivou procesora. Učinkovitija implementacija dequea zahtijeva niz za držanje elemenata.
Međutim, implementacija steka ili reda s nizom nije lak zadatak, ali implementacija dequea na ovaj način i korištenje kao osnove za druge strukture podataka će nam dati značajno povećanje performansi i omogućiti nam ponovno korištenje koda. Ovo smanjuje troškove podrške.
Kasnije ćemo pogledati varijantu niza reda, ali prvo pogledajmo stack klasu koristeći deque:
Javna klasa Stack ( Deque _items = new Deque(); public void Push(T vrijednost) ( _items.EnqueueFirst(value); ) public T Pop() ( return _items.DequeueFirst(); ) public T Peek() ( return _items .PeekFirst(); ) public int Count ( get ( return _items.Count; ) ) )
Imajte na umu da je svo rukovanje greškama sada u klasi Deque, a osim toga, svaka optimizacija reda će se također odraziti na stog. Implementacija konvencionalnog deka je toliko jednostavna da je ostavljamo kao vježbu čitaocu.
Čuvanje elemenata u nizu
Kao što je već spomenuto, postoje prednosti implementacije reda pomoću niza. Izgleda jednostavno, ali u stvari postoji niz nijansi koje treba uzeti u obzir.
Pogledajmo probleme koji se mogu pojaviti i kako ih riješiti. Osim toga, trebat će nam informacije o rastu unutrašnjeg niza iz posljednjeg članka o dinamičkim nizovima.
Kada se kreira red, unutar njega se kreira niz nulte dužine. Crvena slova "h" i "t" označavaju pokazivače _head i _tail, respektivno.
Deque deq = new Deque(); deq.EnqueueFirst(1);
Deq.EnqueueLast(2);
Deq.EnqueueFirst(0);
Primijetite da je indeks "glave" reda skočio na vrh liste. Sada je prvi element koji se vraća pri pozivanju metode DequeueFirst 0 (indeks 3).
Deq.EnqueueLast(3);
Niz je pun, tako da kada se doda element, dogodit će se sljedeće:
- Algoritam rasta će odrediti veličinu novog niza.
- Elementi će biti kopirani u novi niz od "head" do "tail".
- Dodat će se novi element.
Sada da vidimo šta se dešava kada se element ukloni:
Deq.DequeueFirst();
Deq.DequeueLast();
Ključna stvar: bez obzira na kapacitet ili punoću unutrašnjeg niza, logično, sadržaj reda su elementi od „glave“ do „repa“, uzimajući u obzir „petlju“. Ovo ponašanje se još naziva i "međuspremnik prstena".
Pogledajmo sada implementaciju.
Deque class (koristeći niz)
Interfejs reda koji se zasniva na nizu je isti kao u slučaju implementacije povezane liste. Nećemo to ponoviti. Međutim, pošto je lista zamijenjena nizom, dodali smo nova polja - sam niz, njegovu veličinu i pokazivače na "rep" i "glavu" reda.
Javna klasa Deque ( T _items = new T; // Broj stavki u redu. int _size = 0; // Indeks prve (najstarije) stavke. int _head = 0; // Indeks posljednje (najnovije) stavke int _tail = -1; ... )
algoritam rasta
Kada ponestane slobodnog prostora u unutrašnjem nizu, potrebno ga je povećati, kopirati elemente i ažurirati pokazivače na "rep" i "glavu". Ova operacija se izvodi ako je potrebno tokom dodavanja elementa. Parametar startingIndex se koristi za označavanje koliko polja na početku treba ostaviti praznih (ako se dodaju na početku).
Obratite pažnju na to kako se podaci preuzimaju kada morate skočiti na početak niza pri prelasku sa "glave" na "rep".
Privatni void allocateNewArray(int startingIndex) ( int newLength = (_size == 0) ? 4: _size * 2; T newArray = new T; if (_size > 0) ( int targetIndex = startingIndex; // Kopiraj sadržaj... / / Ako niz nije u petlji, samo kopirajte elemente. // U suprotnom kopirajte od glave do kraja, a zatim od početka niza do repa. // Ako je rep manji od glave, idite na početak. ako (_rep< _head) { // Копируем _items.._items в newArray..newArray[N]. for (int index = _head; index < _items.Length; index++) { newArray = _items; targetIndex++; } // Копируем _items.._items в newArray.. for (int index = 0; index <= _tail; index++) { newArray = _items; targetIndex++; } } else { // Копируем _items.._items в newArray..newArray[N] for (int index = _head; index <= _tail; index++) { newArray = _items; targetIndex++; } } _head = startingIndex; _tail = targetIndex - 1; } else { // Массив пуст. _head = 0; _tail = -1; } _items = newArray; }
EnqueueFirst Method
- ponašanje: Dodaje element na početak reda. Ovaj element će biti preuzet iz sljedećeg reda kada se pozove metoda DequeueFirst.
- složenost:
EnqueueLast Method
- ponašanje: Dodaje element na kraj reda. Ovaj element će biti preuzet iz reda nakon što se pozove metoda DequeueLast.
- složenost: O(1) u većini slučajeva; O(n) kada je potrebno proširenje niza.
DequeueFirst metoda
- ponašanje: Uklanja element s prednje strane reda i vraća ga. Ako je red prazan, izbacuje InvalidOperationException .
- složenost: O(1).
DequeueLast metoda
- ponašanje: Uklanja element s kraja reda i vraća ga. Ako je red prazan, izbacuje InvalidOperationException .
- složenost: O(1).
PeekFirst Method
- ponašanje: Vraća element s početka reda bez promjene. Ako je red prazan, izbacuje InvalidOperationException .
- složenost: O(1).
PeekLast metoda
- ponašanje: Vraća element s kraja reda bez promjene. Ako je red prazan, izbacuje InvalidOperationException .
- složenost: O(1).
Count Method
- ponašanje: Vraća broj elemenata u redu, ili 0 ako je red prazan.
- složenost: O(1).
Nastavlja se
Tako smo završili četvrti dio naše serije članaka. U njemu smo pogledali hrpe i redove. Sljedeći put ćemo prijeći na stabla binarnog pretraživanja.
