Koristimo sve naprednije programske jezike koji nam omogućavaju da napišemo manje koda i postignemo odlične rezultate. Morate platiti za ovo. Kako radimo sve manje stvari niskog nivoa, postaje normalno da mnogi od nas ne razumiju u potpunosti što su stog i hrpa, kako se zapravo kompilacija događa, koja je razlika između statičkog i dinamičkog kucanja itd. Ne kažem da svi programeri ne znaju za ove koncepte - samo mislim da je ponekad vrijedno vratiti se tako starim stvarima.
Danas ćemo razgovarati samo o jednoj temi: steku i hrpi. I stog i hrpa se odnose na različite lokacije na kojima se dešava upravljanje memorijom, ali strategija za ovo upravljanje je dramatično drugačija.
Stack
Stack je područje RAM-a koje se kreira za svaku nit. Radi u LIFO (Last In, First Out) redoslijedu, to jest, posljednji komad memorije dodan u stog će biti prvi u redu za izlaz iz steka. Svaki put kada funkcija deklarira novu varijablu, ona se gura u stog, a kada ta varijabla izađe izvan opsega (na primjer, kada se funkcija završi), automatski se izbacuje iz steka. Kada se varijabla steka oslobodi, ovo područje memorije postaje dostupno za druge varijable steka.
Ova priroda steka čini upravljanje memorijom vrlo logičnim i jednostavnim za izvođenje na CPU-u; ovo dovodi do velike brzine, posebno zato što je vrijeme ciklusa za ažuriranje bajta steka vrlo kratko, tj. ovaj bajt je najvjerovatnije vezan za keš procesora. Međutim, postoje nedostaci ovog strogog oblika vladavine. Veličina steka je fiksna vrijednost, a prekoračenje memorije dodijeljene na stogu rezultirat će prelivanjem steka. Veličina se postavlja kada se tok kreira, a svaka varijabla ima maksimalnu veličinu ovisno o tipu podataka. Ovo vam omogućava da ograničite veličinu nekih varijabli (na primjer, cijelih brojeva) i prisiljava vas da unaprijed deklarirate veličinu složenijih tipova podataka (na primjer, nizova), budući da im stog neće dozvoliti da je mijenjaju. Osim toga, varijable koje se nalaze na steku su uvijek lokalne.
Kao rezultat toga, stek vam omogućava da upravljate memorijom na najefikasniji način - ali ako trebate koristiti dinamičke strukture podataka ili globalne varijable, onda biste trebali obratiti pažnju na hrpu.
Hrpa
Hrpa je memorijska pohrana, također smještena u RAM-u, koja omogućava dinamičku dodjelu memorije i ne radi kao stog: to je samo skladište za vaše varijable. Kada dodijelite dio memorije na hrpi za pohranjivanje varijable, možete mu pristupiti ne samo u niti, već iu cijeloj aplikaciji. Ovako se definišu globalne varijable. Kada se aplikacija završi, sva dodijeljena memorijska područja se oslobađaju. Veličina hrpe se postavlja kada se aplikacija pokrene, ali, za razliku od steka, ona je samo fizički ograničena i to vam omogućava da kreirate dinamičke varijable.
Sa hrpom komunicirate putem referenci, koje se obično nazivaju pokazivači — varijable čije su vrijednosti adrese drugih varijabli. Kreiranjem pokazivača, pokazujete na memorijsku lokaciju na hrpi, koja postavlja početnu vrijednost za varijablu i govori programu gdje da pristupi toj vrijednosti. Zbog dinamičke prirode hrpe, CPU ne učestvuje u njenoj kontroli; u jezicima bez sakupljača smeća (C, C ++), programer mora ručno osloboditi memorijske dijelove koji više nisu potrebni. Ako to ne učinite, to može dovesti do curenja memorije i fragmentacije, što će značajno usporiti hrpu.
U poređenju sa stekom, hrpa je sporija jer su varijable raštrkane u memoriji umjesto da se nalaze na vrhu steka. Nepravilno upravljanje memorijom u hrpi usporava njen rad; međutim, to ne umanjuje njegovu važnost - ako trebate raditi sa dinamičkim ili globalnim varijablama, koristite hrpu.
IBM je napravio dramatičnu grešku što nije obezbijedio hardversku implementaciju za stog. Ova serija je sadržavala mnoga druga neuspješna rješenja, ali je, nažalost, kopirana u Sovjetskom Savezu pod imenom ES EVM (United Series), a sav vlastiti razvoj je obustavljen. To je sovjetsku industriju vratilo mnogo godina unazad na polju razvoja računara.Red
Red čekanja 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 stavke možete dodavati samo na kraj reda; stavke možete preuzimati samo od početka. Za razliku od običnog reda, koji uvijek možete napustiti ako želite, ne možete ukloniti stavke iz sredine reda čekanja programatora.
Red se može zamisliti kao cijev. Kuglice se mogu dodati na jedan kraj cijevi - elementi reda, s drugog kraja se uklanjaju. Stavke u sredini reda, tj. kuglice unutar cijevi nisu dostupne. Kraj epruvete u koji se dodaju kuglice odgovara kraju reda, kraj s kojeg se odvode na početak reda. Dakle, krajevi cijevi nisu simetrični, kuglice unutar cijevi kreću se samo u jednom smjeru.
U principu, bilo bi moguće dopustiti da se stavke dodaju na oba kraja reda i da se pokupe 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 je ista kao i njegova uloga u svakodnevnom životu. Red je gotovo uvijek povezan sa zahtjevima za posluživanje, u slučajevima kada se ne mogu izvršiti trenutno. Red također održava redoslijed po kojem se zahtjevi 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 on samo ispisuje tekst, tada bi se radnja trebala sastojati od dodavanja jednog znaka tekstu i može biti popraćena ponovnim iscrtavanjem područja ekrana, pomicanjem prozora, preformatiranjem pasusa itd.
Bilo koji, čak i najjednostavniji, operativni sistem je u ovoj ili onoj 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 nema pravo zanemariti pritisak na tipku u bilo kojoj situaciji. Zbog toga se računar prekida, pamti svoje stanje i prelazi na obradu pritiska na taster. Ova obrada treba da bude vrlo kratka kako ne bi ometala druge zadatke. Komanda izdata pritiskom na tipku jednostavno se dodaje na kraj čekajućeg reda zahtjeva. 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ć tek 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 ponovnog iscrtavanja područja prozora, o odabiru stavke menija itd. 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, rad prozorske aplikacije sastoji se, jednostavno rečeno, u sekvencijalnom izvršavanju zahtjeva iz njenog reda. Red čekanja održava operativni sistem.
Pristup programiranju, koji se ne sastoji u direktnom pozivanju procedura, već u slanju poruka koje se stavljaju u red zahtjeva, ima mnoge prednosti i jedna je od karakteristika objektno orijentisanog programiranja. Tako, na primjer, ako se prozorski program iz bilo kojeg razloga mora prekinuti, bolje je ne pozivati odmah naredbu za izlaz, š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 izvršeno prema ranijim zahtjevima.
Implementacija reda niza
Kao što je već pomenuto, 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 baza za neposrednu implementaciju. U slučaju reda čekanja, dvije najpopularnije implementacije su kontinuirana implementacija zasnovana na nizu, koja se također naziva implementacija kružnog bafera, i referentna implementacija, ili implementacija zasnovana na listi. Referentne implementacijeće biti razmotreno u nastavku.
Uz kontinuiranu implementaciju reda, niz fiksne dužine N djeluje kao baza, tako da je red ograničen i ne može sadržavati više od N elemenata. Indeksi elemenata niza se kreću od 0 do N - 1. Pored niza, implementacija reda pohranjuje tri jednostavne varijable: indeks početka reda, indeks kraja reda i broj elemenata u redu. Elementi reda su sadržani u segmentu niza od početnog indeksa do završnog 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, pri preuzimanju elementa iz glave reda, sadržaj ćelije niza s indeksom glave reda se pohranjuje kao rezultat operacije, tada 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 na kraju reda dođe do kraja niza, tj. N - 1?
Ključna ideja iza implementacije reda je da se niz mentalno upetlja u prsten. Smatra se da iza posljednjeg elementa niza slijedi njegov prvi element (podsjetimo da posljednji element ima indeks N - 1, a prvi ima indeks 0). Prilikom pomjeranja indeksa kraja reda udesno, u slučaju kada pokazuje na posljednji element niza, ide 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 od njihovog dodavanja. To je kao pogrešan red, u kojem prvi služi onaj koji je zadnji ušao. U literaturi za programiranje općenito 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. Disciplina steka je označena sa LIFO, posljednji ušao prvi je izašao.
Stog se može zamisliti kao vertikalna cijev sa oprugom na dnu. Gornji kraj cijevi je otvoren, možete dodati ili, kako kažu, gurnuti elemente u njega. Uobičajeni engleski termini u tom pogledu su vrlo šareni, operacija dodavanja elementa u stog označava se push, što znači "push, push". Novododata stavka gura stavke gurnute na stog ranije za jednu poziciju naniže. Kada se elementi izbace iz steka, izgleda da su gurnuti prema gore, na engleskom pop ("pucaj").
Primjer hrpe je plast sijena, hrpa papira na stolu, hrpa tanjira i slično. Odatle potiče naziv steka, što na engleskom znači stek. Ploče se uklanjaju iz hrpe obrnutim redoslijedom od dodavanja. Dostupna je samo gornja ploča, tj. ploča na vrhu hrpe... Dobar primjer bi također bila željeznička slijepa ulica u koju se mogu montirati vagoni.
Korišćenje steka u programiranju
Stack se koristi prilično često iu raznim situacijama. Ujedinjuje ih sljedeći cilj: potrebno je sačuvati do kraja neki posao koji još nije završen, ako se trebate prebaciti na drugi zadatak. Stog se koristi za privremeno pohranjivanje stanja nedovršenog posla do kraja. Nakon što sačuva stanje, računar se prebacuje na drugi zadatak. Na kraju njegovog izvršenja, stanje posla na čekanju se vraća iz steka, a računar nastavlja prekinuti rad.
Zašto se stek koristi za čuvanje stanja prekinutog posla? Pretpostavimo da računar obavlja 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, prilikom izvršavanja zadatka B, računar se može prebaciti na drugi zadatak C, i biće potrebno sačuvati stanje zadatka B pre prelaska 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, oporavak se događa obrnutim redoslijedom od spremanja, što je u skladu sa disciplinom steka.
Stek vam omogućava da organizujete rekurziju, tj. poziv potprograma samom sebi, bilo direktno ili kroz lanac drugih poziva. Na primjer, pretpostavimo da potprogram A izvršava algoritam koji ovisi o ulaznom parametru X i, moguće, o stanju globalnih podataka. Za najjednostavnije vrijednosti X algoritam se direktno implementira. Za složenije X vrijednosti, algoritam se implementira kao redukcija na primjenu istog algoritma na jednostavnije X vrijednosti. U ovom slučaju, potprogram A upućuje na sebe, prosljeđujući jednostavniju vrijednost X kao parametar. U takvom pozivu, 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 od tačke gdje je prekinut.
Zapravo, ne morate čak ni pohranjivati vrijednosti 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) stavljaju se na stog implementiran u hardveru zasnovan na običnoj memoriji slučajnog pristupa. Na samom početku svog rada, potprogram zauzima mjesto na steku za svoje lokalne varijable, ovaj dio memorije u hardverskom stogu se obično naziva blok lokalne varijabli ili na engleskom okvir("okvir"). Na kraju svog rada, potprogram oslobađa memoriju uklanjanjem bloka svojih lokalnih varijabli iz steka.
Pored lokalnih varijabli, hardverski stog pohranjuje povratne adrese za pozive potprograma. Neka potprogram bude pozvan u nekom trenutku programa A B... Prije nego što se pozove potprogram B, adresa instrukcije koja slijedi nakon instrukcije koja poziva B se pohranjuje u stog. Ovo je tzv povratna adresa za program A. Na kraju svog rada, potprogram B izbacuje povratnu adresu programu A iz steka i vraća kontrolu na ovu adresu. Dakle, računar nastavlja da izvršava program A iz instrukcije koja sledi instrukciju za pozivanje. Većina procesora ima posebne instrukcije koje podržavaju pozivanje potprograma tako što prvo guraju povratnu adresu u stog i vraćaju se iz potprograma na adresu izbačenu iz steka. Obično se naredba za pozivanje zove poziv, a naredba za povratak je return.
Parametri potprograma ili funkcije se također guraju u stog prije pozivanja. Redosled kojim se oni guraju na stek zavisi od konvencija jezika 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. (Stoga, inače, funkcije s promjenjivim brojem argumenata, kao što je printf, moguće su u C-u, ali ne i u Pascalu.)
U Fortranu-4, jednom od najstarijih i najuspješnijih programskih jezika, argumenti se prosljeđuju kroz posebno područje memorije, koje se možda ne nalazi na steku, budući da su računari poput IBM 360 ili ES računara bez hardverske implementacije još uvijek postojali. do kraja 70-ih godina XX veka. Povratne adrese su također bile pohranjene ne u stog, već na memorijske lokacije fiksne 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 prilikom novog poziva uništavaju prethodne vrijednosti lokalnih varijabli. U referentnom Fortran-4 korištene su samo statičke varijable, a rekurzija je bila 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 biti veća od N. Indeksi ćelija niza se kreću 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. kod indeksa 0, stavka iznad najdonjeg elementa steka je pohranjena na indeksu 1, i tako dalje. Vrh steka je pohranjen negdje u sredini niza. Indeks stavke na vrhu hrpe pohranjen je u posebnoj varijabli koja se obično naziva pokazivač N - 1. Elementi steka zauzimaju neprekidni segment niza, počevši od ćelije čiji je indeks pohranjen u pokazivaču steka i završavajući posljednjom ć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 više od indeksa posljednje ćelije u nizu).
Zdravo, ja sam student druge godine na tehničkom fakultetu. Nakon što sam preskočio nekoliko parova programiranja iz zdravstvenih razloga, naišao sam na nerazumijevanje tema kao što su "Stack" i "Queue". Putem pokušaja i grešaka, nakon nekoliko dana, konačno mi je sinulo šta je to i sa čime se jede. Kako vam razumijevanje ne bi oduzelo toliko vremena, u ovom članku ću vam reći šta je "Stack", kako i na kojim primjerima sam shvatio šta je to. Ako vam se sviđa, napisat ću drugi dio, koji će se dotaknuti koncepta kao što je "Red"
Teorija
Na Wikipediji, definicija steka je:
Stack (engleski stack - stek; stek se čita) je apstraktni tip podataka koji je lista elemenata organizovanih prema LIFO principu (engleski last in - first out, "last in - first out").
Ovo je prilično potpuna definicija, ali početnicima će možda biti malo teško razumjeti.
Stoga, prva stvar na koju bih želio da se fokusiram je predstavljanje hrpe u obliku stvari iz života. Prvo što mi je palo na pamet bila je interpretacija u obliku hrpe knjiga, gdje je gornja knjiga vrh.
Zapravo, snop se može predstaviti kao hrpa bilo kojih objekata, bilo da je to hrpa listova, bilježnica, košulja i slično, ali primjer s knjigama, mislim, će biti najoptimalniji.
Dakle, od čega se sastoji stek?
Stog se sastoji od ćelija (u primjeru su to knjige), koje su predstavljene u obliku strukture koja sadrži neke podatke i pokazivač na tip ove strukture na sljedeći element.
Teško? Nema veze, hajde da to shvatimo.
Ova slika prikazuje šematski stog. Blok "Podaci / * sljedeći" je naša ćelija. * next, kao što vidimo, pokazuje na sljedeći element, drugim riječima, pokazivač * next pohranjuje adresu sljedeće ćelije. * TOP pokazivač pokazuje na vrh steka, odnosno pohranjuje njegovu adresu.
Kada je teorija završena, idemo na praksu.
Vježbajte
Prvo, moramo stvoriti strukturu koja će biti naša "ćelija"
C++ kod
struct comp (// Struktura nazvana comp (od riječi komponenta) int Data; // Neki podaci (mogu biti bilo koji, na primjer, možete napisati int ključ; char Data; možete dodati još neke podatke) comp * sljedeći ; // Pokazivač tipa comp na sljedeći element);
Za početnike možda neće biti jasno zašto je naš pokazivač comp tipa, odnosno pokazivač tipa comp strukture. Dozvolite mi da objasnim da da bi * sljedeći pokazivač mogao pohraniti comp strukturu, on mora naznačiti tip ove strukture. Drugim riječima, specificirajte šta će pokazivač pohraniti.
Nakon što smo postavili "Cell", idemo na kreiranje funkcija.
Funkcije
Funkcija kreiranja "Stack" / dodavanja stavke u "Stack"
Prilikom dodavanja elementa imat ćemo dvije situacije:
- Stog je prazan i treba ga kreirati
- Stog već postoji i samo treba da mu dodate novi element
C++ kod
void s_push (comp ** top, int D) (// funkcija tipa void (ne vraća ništa) koja uzima pokazivač na vrh steka i varijablu koja će biti upisana u ćeliju comp * q; // Kreirajte novi pokazivač q tipa strukture comp. u stvari, ovo je naš novi element q = new comp (); // dodijeli memoriju za novi element q-> Data = D; // Upiši traženi broj u element podataka ako (top == NULL) (// Ako nema vrha, odnosno stek je prazan * top = q; // vrh steka će biti novi element) inače // ako stek nije prazan ( q-> next = * top; // Povezujemo se od novog elementa do vrha. To jest, stavljamo knjigu na vrh steka. * top = q; // Označavamo da je vrh sada novi element))
Hajdemo malo više detalja.
Prvo, zašto funkcija uzima ** top, odnosno pokazivač na pokazivač, radi jasnoće, ovo pitanje ostavljam za kasnije. Drugo, hajde da razgovaramo detaljnije o tome q-> sljedeći = * vrh i šta to znači ->
.
-> znači da, grubo govoreći, idemo u našu strukturu i odatle dobijamo element ove strukture. U redu q-> sljedeći = * vrh dobijamo iz naše ćelije pokazivač na sljedeći element * sljedeći i zamjenjujemo ga pokazivačem koji pokazuje na vrh steka * top. Drugim riječima, mi komuniciramo, od novog elementa do vrha steka. Ovdje nema ništa komplikovano, baš kao kod knjiga. Novu knjigu stavljamo tačno na vrh hrpe, odnosno pravimo vezu od nove knjige do vrha hrpe knjiga. Nakon toga, nova knjiga automatski postaje vrh, pošto hrpa nije hrpa knjiga, moramo naznačiti da je novi element vrh, za to pišemo: * vrh = q;.
Funkcija uklanjanja elementa iz "Stack" prema podacima
Ova funkcija će ukloniti element iz steka ako je broj podataka ćelije (q-> Data) jednak broju koji ćemo sami odrediti.
Mogu postojati takve opcije:
- Ćelija koju treba da izbrišemo je vrh steka
- Ćelija koju trebamo izbrisati nalazi se na kraju, ili između dvije ćelije
C++ kod
void s_delete_key (comp ** top, int N) (// funkcija koja zauzima vrh i broj koji treba obrisati comp * q = * top; // kreirajte pokazivač tipa comp i izjednačite ga (stavite) na vrh stack comp * prev = NULL; // kreiramo pokazivač na prethodni element, od početka će biti prazan dok (q! = NULL) (// sve dok q pokazivač nije prazan, izvršićemo kod u petlja, ako se i dalje završava praznom petljom if (q-> Podaci == N) (// ako su podaci elementa jednaki broju koji trebamo obrisati if (q == * vrh) (/ / ako je takav pokazivač jednak vrhu, odnosno element koji trebamo izbrisati je vrh * top = q- > next; // pomakni vrh na sljedeći element slobodno (q); // obrišite ćelija q-> Podaci = NULL; // Zatim, da bismo izbjegli greške, nuliramo varijable u izbrisanoj ćeliji, budući da u nekim prevodiocima obrisana ćelija ima vrijednosti varijabli koje nisu NULL, ali doslovno "Čitanje memorije je nemoguće" ili brojevi " -2738568384" ili drugi, ovisno o kompajleru. q-> next = NULL;) else // if element n zadnji ili između dva druga elementa (prev-> next = q-> next; // Veza od prethodnog elementa do sljedećeg slobodnog (q); // očisti ćeliju q-> Data = NULL; // nulti varijable q -> sljedeći = NULL; )) // ako Podaci elementa NISU jednaki broju koji trebamo ukloniti prev = q; // zapamtite trenutnu ćeliju kao prethodnu q = q-> next; // pomaknite q pokazivač na sljedeći element))
U ovom slučaju, pokazivač q igra istu ulogu kao i pokazivač u bilježnici, prelazi preko cijelog hrpa sve dok ne postane NULL ( dok (q! = NULL)), drugim riječima, dok se stog ne završi.
Za bolje razumijevanje brisanja elementa, povučemo analogiju sa već poznatim hrpom knjiga. Ako trebamo ukloniti knjigu s vrha, uklanjamo je, a knjiga ispod nje postaje vrh. I ovdje je isto, samo na početku moramo odrediti da će sljedeći element postati vrh. * vrh = q-> sljedeći; i tek onda uklonite element besplatno (q);
Ako je knjiga koju treba ukloniti između dvije knjige ili između knjige i stola, prethodna knjiga će ležati na sljedećoj ili na stolu. Kao što smo već shvatili, naša knjiga je ćelija, a tabela je NULL, odnosno nema sljedećeg elementa. Ispada na isti način kao i kod knjiga, označavamo da će prethodna ćelija biti povezana sa sljedećom prev-> next = q-> next;, to je vrijedno napomenuti prev-> next može biti jednako ćeliji i nuli, ako q-> next = NULL, odnosno nema ćelije (knjiga će ležati na stolu), nakon toga obrišemo ćeliju besplatno (q).
Također je vrijedno napomenuti da ako ne uspostavite ovu vezu, dio ćelija koji leži nakon obrisane ćelije postat će nedostupan, jer će se sama veza koja povezuje jednu ćeliju s drugom izgubiti i ovaj dio će jednostavno biti izgubljen u memoriji
Funkcija prikaza podataka steka
Najjednostavnija funkcija:
C++ kod
void s_print (comp * top) (// uzima pokazivač na vrh steka comp * q = top; // postavlja q na vrh dok (q) (// dok q nije prazan (dok je (q) ekvivalentno while (q! = NULL )) printf_s ("% i", q-> Podaci); // prikazujemo podatke ćelije steka q = q-> sljedeće; // nakon što smo prikazali, pomjerimo q na sljedeći element (ćelija)))
Ovdje mislim da je sve jasno, samo želim reći da q treba shvatiti kao klizač, prolazi kroz sve ćelije odozgo, gdje smo ga instalirali na početku: * q = vrh;, do zadnje stavke.
Glavna funkcija
Pa, zapisali smo glavne funkcije za rad sa stekom, zovemo ih.
Pogledajmo kod:
C++ kod
void main () (comp * top = NULL; // na početku programa nemamo red, tako da nema vrha, dajemo mu NULL vrijednost // Zatim počinjemo sa dodavanjem brojeva od 1 do 5 u naš stack s_push (& top, 1); s_push (& top, 2); s_push (& top, 3); s_push (& top, 4); s_push (& top, 5); // nakon izvršavanja funkcija na steku , imat ćemo 54321 s_print (vrh); // ispisati s_delete_key (& top, 4); // Zatim izbrišemo 4, stog dobija 5321 printf_s ("\ n"); // prijenos u novi red s_print (vrh ); // sistem ispisa ("pauza"); // pauza)
Vratimo se zašto smo u funkciju proslijedili pokazivač na pokazivač vrha. Činjenica je da ako bismo u funkciju uveli samo pokazivač na vrh, onda bi se "Stack" kreirao i mijenjao samo unutar funkcije, au glavnoj funkciji bi vrh također bio NULL. Prenošenjem pokazivača na pokazivač, mijenjamo top * top u glavnoj funkciji. Ispostavilo se da ako funkcija promijeni stek, trebate prenijeti vrh na njega kao pokazivač na pokazivač, kao što smo imali u funkciji s_push, s_delete_key. U funkciji s_print, "stack" se ne bi trebao mijenjati, tako da samo proslijeđujemo pokazivač na vrh.
Umjesto cifara 1,2,3,4,5, možete koristiti i varijable tipa int.
Zaključak
Cijeli programski kod:
C++ kod
#include
Rezultat izvršenja
Budući da se stavke stalno guraju na vrh hrpe, stavke će biti prikazane obrnutim redoslijedom
U zaključku, želio bih da vam se zahvalim na vremenu posvećenom mom članku, zaista se nadam da je ovaj materijal pomogao nekim programerima početnicima da shvate šta je "Stack", kako ga koristiti, a u budućnosti neće imati bilo kakvih problema više. Napišite u komentarima svoje mišljenje, kao i kako da poboljšam svoje članke u budućnosti. Hvala na pažnji.
Tagovi: Stack, C stek, implementacija steka, stek na nizu, dinamički rastući stog, stek na pojedinačno povezanom disku
Stack
C tech je vjerovatno najjednostavnija struktura podataka koju ćemo naučiti i koju ćemo stalno koristiti. Stog je struktura podataka u kojoj elementi podržavaju LIFO (“Last in first out”) princip: posljednji ušao, prvi izašao. Ili prvi koji ulazi - zadnji izlazi.
Stog vam omogućava pohranjivanje stavki i obično podržava dvije osnovne operacije:
- GURANJE- stavlja predmet na vrh hrpe
- POP- iskače element sa vrha hrpe, pomerajući vrh na sledeći element
Takođe je uobičajeno da PEEK operacija dobije stavku na vrhu hrpe, ali ne i da je izbaci odatle.
Stog je jedna od osnovnih struktura podataka i koristi se ne samo u programiranju, već i u električnim kolima, i jednostavno u proizvodnji, za implementaciju tehnoloških procesa itd.; stek se koristi kao pomoćna struktura podataka u mnogim algoritmima i drugim složenijim strukturama.
Na primjer, recimo da imamo hrpu brojeva. Pokrenimo nekoliko naredbi. U početku, stek je prazan. Vrh steka je pokazivač na prvi element, ne pokazuje nigdje. U slučaju c, može biti NULL.
Stog se sada sastoji od jednog elementa, broja 3. Vrh hrpe pokazuje na broj 3.
Stog se sastoji od dva elementa, 5 i 3, sa vrhom snopa koji pokazuje na 5.
Stog se sastoji od tri elementa, vrh snopa pokazuje na 7.
Vratiće vrijednost 7, 5 i 3 će ostati na steku. Vrh će pokazivati na sljedeći element - 5.
Vratiće 5, na steku će ostati samo jedan element, 3, na koji će biti pokazan vrh steka.
Vratiće 3, stog će biti prazan.
Hrpa se često poredi sa hrpom tanjira. Da biste dobili sljedeću ploču, morate ukloniti prethodne. Vrh hrpe je vrh hrpe ploča.
Kada radimo sa stekom, moguće su dvije glavne i uobičajene greške:
- 1. Poništavanje steka: Pokušaj izbacivanja stavke iz praznog snopa
- 2. Stack Overflow: Pokušaj stavljanja nove stavke na stog koji više ne može rasti (na primjer, nema dovoljno RAM-a)
Implementacija softvera
Razmotrite tri jednostavne implementacije steka:
Stog fiksne veličine izgrađen na nizu
Posebnost je jednostavnost implementacije i maksimalna brzina izvršenja. Takav stek se može koristiti kada je njegova maksimalna veličina unaprijed poznata ili se zna da je mala.
Prvo određujemo maksimalnu veličinu niza i vrstu podataka koji će biti pohranjeni u njemu:
#define STACK_MAX_SIZE 20 typedef int T;
Sada sama struktura
Typedef struct Stack_tag (T podaci; veličina_t veličine;) Stack_t;
Ovdje je veličina varijable broj elemenata, au isto vrijeme i pokazivač na vrh steka. Vrh će pokazivati na sljedeći element niza u koji će biti upisana vrijednost.
Stavljamo novu stavku na stog.
Void push (Stack_t * stack, const T vrijednost) (stack-> data = value; stack-> size ++;)
Jedini problem je što možete izaći van niza. Stoga uvijek trebate provjeriti da nema greške prekoračenja steka:
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push (Stack_t * stack, const T vrijednost) (ako (sklad-> veličina> = STACK_MAX_SIZE) (izlaz (STACK_OVERFLOW);) stek-> podaci = vrijednost; stog-> veličina ++ ;)
Slično, definiramo Pop operaciju koja vraća element s vrha i nastavlja na sljedeći
T pop (Stack_t * stog) (ako (stog-> veličina == 0) (izlaz (STACK_UNDERFLOW);) stog-> veličina--; vrati stog-> podaci;)
I funkcija zavirivanja koja vraća trenutnu stavku s vrha
T zaviri (konstant Stack_t * stog) (ako (sklad-> veličina<= 0) { exit(STACK_UNDERFLOW); } return stack->podaci; )
Još jedna važna napomena - nemamo funkciju za kreiranje steka, tako da morate ručno resetirati vrijednost veličine
Pomoćne funkcije za ispis stavki snopa
Void printStackValue (const T vrijednost) (printf ("% d", vrijednost);) void printStack (const Stack_t * stog, void (* printStackValue) (const T)) (int i; int len = stack-> size - 1 ; printf ("stog% d>", stog-> veličina); za (i = 0; i< len; i++) { printStackValue(stack->podaci [i]); printf ("|"); ) if (stack-> size! = 0) (printStackValue (stack-> data [i]);) printf ("\ n"); )
Imajte na umu da koristimo int u funkciji ispisa, a ne size_t, jer len može postati negativan. Funkcija prvo ispisuje veličinu steka, a zatim njegov sadržaj, odvajajući elemente sa |
Ispitivanje
Stack_t stack; stack.size = 0; push (& stack, 3); printStack (& stack, printStackValue); push (& stack, 5); printStack (& stack, printStackValue); push (& stack, 7); printStack (& stack, printStackValue); printf ("% d \ n", pop (& stack)); printStack (& stack, printStackValue); printf ("% d \ n", pop (& stack)); printStack (& stack, printStackValue); printf ("% d \ n", pop (& stack)); printStack (& stack, printStackValue); _getch ();
Razmotrite i situacije u kojima postoje greške u korištenju. Underflow
Void main () (Stack_t stack; stack.size = 0; push (& stack, 3); pop (& stack); pop (& stack); _getch ();)
Void main () (Stack_t stack; size_t i; stack.size = 0; za (i = 0; i< 100; i++) { push(&stack, i); } _getch(); }
Dinamički rastući stog na nizu
Dinamički rastući stek se koristi kada broj elemenata može biti značajan i nije poznat u trenutku rješavanja problema. Maksimalna veličina steka može biti ograničena nekim brojem ili veličinom RAM-a.
Stog će se sastojati od pokazivača na podatke, veličine niza (maksimalno) i broja elemenata u nizu. Ovaj broj će također označavati vrh.
Typedef struct Stack_tag (T * podaci; veličina_t veličina; veličina_t vrh;) Stack_t;
Za početak, potrebna vam je neka početna veličina niza, neka bude jednaka 10
#define INIT_SIZE 10
Algoritam rada je sljedeći: provjeravamo da li je vrijednost vrha premašila vrijednost veličine. Ako je vrijednost prekoračena, tada povećavamo veličinu niza. Postoji nekoliko opcija kako povećati niz. Možete dodati broj, možete pomnožiti s nekom vrijednošću. Koja je od opcija bolja ovisi o specifičnostima zadatka. U našem slučaju, veličinu ćemo pomnožiti brojem MNOŽITELJ
#define MNOŽITELJ 2
Nećemo postavljati maksimalnu veličinu. Program će se srušiti pri prekoračenju steka ili nedostatku steka. Implementiraćemo isti interfejs (pop, push, peek). Osim toga, pošto je niz dinamičan, napravićemo neke pomoćne funkcije za kreiranje steka, uklanjanje i čišćenje.
Prvo, funkcije za kreiranje i uklanjanje steka i nekoliko grešaka
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t * createStack () (Stack_t * out = NULL; out = malloc (sizeof (Stack_t)); if (out == NULL_OUT) out-> size = INIT_SIZE; out-> data = malloc (out-> size * sizeof (T)); if (out-> data == NULL) (slobodan (out); izlaz (OUT_OF_MEMORY);) out- > top = 0; return out;) void deleteStack (Stack_t ** stog) (besplatno ((* stog) -> podaci); besplatno (* stog); * stog = NULL;)
Sve je krajnje jednostavno i jasno, nema prljavih trikova. Kreiramo stek sa početnom dužinom i nula vrijednosti.
Sada napišimo pomoćnu funkciju za promjenu veličine.
Poništavanje promjene veličine (Stack_t * stog) (stog-> veličina * = MNOŽITELJ; stog-> podaci = realloc (stog-> podaci, stog-> veličina * sizeof (T)); if (stog-> podaci == NULL) ( izlaz (STACK_OVERFLOW);))
Ovdje, imajte na umu, u slučaju da se ne može dodijeliti dovoljno memorije, izaći će sa STACK_OVERFLOW.
Push funkcija provjerava da li smo izvan granica niza. Ako je tako, onda povećajte njegovu veličinu.
Void push (Stack_t * stog, T vrijednost) (ako (sklad-> vrh> = stog-> veličina) (promijeni veličinu (sklad);) stek-> podaci = vrijednost; stog-> vrh ++;)
Funkcije pop i peek slične su onima koje se koriste za niz fiksne veličine.
T pop (Stack_t * stog) (ako (stack-> top == 0) (izlaz (STACK_UNDERFLOW);) stack-> top--; vrati stack-> podaci;) T zaviri (konst. Stack_t * stog) (ako ( stog-> vrh<= 0) { exit(STACK_UNDERFLOW); } return stack->podaci; )
Provjeri
Void main () (int i; Stack_t * s = createStack (); for (i = 0; i< 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }
Napišimo drugu funkciju, implode, koja smanjuje niz na veličinu jednaku broju elemenata u nizu. Može se koristiti kada je već poznato da više neće biti umetnuti elementi i da se memorija može djelomično osloboditi.
Void implode (Stack_t * stog) (stack-> size = stack-> top; stack-> data = realloc (stack-> data, stack-> size * sizeof (T));)
Možemo koristiti u našem slučaju
Za (i = 0; i< 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }
Ova jednonitna implementacija steka koristi malo pristupa memoriji, prilično je jednostavna i raznovrsna, radi brzo i može se implementirati, ako je potrebno, za nekoliko minuta. U daljem tekstu se uvijek koristi, osim ako nije drugačije naznačeno.
Ima nedostatak vezan za metodu povećanja utrošene memorije. Kod množenja sa 2 (u našem slučaju) potrebno je malo pristupa memoriji, ali svako naredno povećanje može dovesti do greške, posebno kod male količine memorije u sistemu. Ako koristite blaži način dodjeljivanja memorije (na primjer, svaki put dodajte 10), tada će se broj poziva povećati, a brzina će pasti. Danas obično nema problema sa veličinom memorije, a menadžeri memorije i sakupljači smeća (koji nisu u C-u) su brzi, pa preovladavaju agresivne promene (na primer, implementacija cele Java standardne biblioteke).
Implementacija steka na jednostruko povezanu listu
Šta je jednostruko povezana lista,. Ukratko: jednostruko povezana lista sastoji se od čvorova, od kojih svaki sadrži korisne informacije i vezu do sljedećeg čvora. Posljednji čvor se odnosi na NULL.
Nećemo imati maksimalne i minimalne veličine (iako u opštem slučaju može biti). Svaki novi element se kreira iznova. Prvo, definirajmo strukturu čvora
#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag (T vrijednost; struct Node_tag * next;) Node_t;
Funkcija za umetanje prvog elementa je jednostavna: kreiramo novi čvor. Bacamo sljedeći pokazivač na stari čvor. Zatim, pokazivač na vrh steka se prenosi na novokreirani čvor. Vrh steka sada pokazuje na novi čvor.
Void push (Node_t ** glava, T vrijednost) (Node_t * tmp = malloc (sizeof (Node_t)); if (tmp == NULL) (izlaz (STACK_OVERFLOW);) tmp-> next = * head; tmp-> vrijednost = vrijednost; * glava = tmp;)
Funkcija pop uzima prvi element (onaj na koji ukazuje vrh), skače pokazivač na sljedeći element i vraća prvi. Ovdje postoje dvije opcije - možete vratiti čvor ili vrijednost. Ako vratimo vrijednost, tada ćemo morati izbrisati čvor unutar funkcije
Node_t * pop1 (Node_t ** glava) (Čvor_t * izlaz; ako ((* glava) == NULL) (izlaz (STACK_UNDERFLOW);) out = * glava; * glava = (* glava) -> sljedeći; povratak; )
T pop2 (Čvor_t ** glava) (Čvor_t * izlaz; T vrijednost; ako (* glava == NULL) (izlaz (STACK_UNDERFLOW);) out = * glava; * glava = (* glava) -> sljedeće; vrijednost = van -> vrijednost; besplatno (out); povratna vrijednost;)
Sada, umjesto provjere dužine niza, svuda se koristi NULL provjera vrha steka.
Jednostavna funkcija zavirivanja
T peek (const Node_t * head) (if (head == NULL) (izlaz (STACK_UNDERFLOW);) vrati head-> vrijednost;)
Iteracija je prilično zanimljiva. Samo se krećemo od jednog čvora do drugog dok ne dođemo do kraja.
Void printStack (const Node_t * glava) (printf ("stack>"); while (head) (printf ("% d", head-> value); head = head-> next;))
I još jedan problem - sada ne možete samo gledati na veličinu steka. Morate ići od početka do kraja i prebrojati sve elemente. Na primjer, tako
Size_t getSize (const Node_t * head) (size_t size = 0; while (head) (size ++; head = head-> next;) return size;)
Naravno, veličinu možete pohraniti zasebno, možete umotati stog sa svim podacima u još jednu strukturu, itd. Razmotrimo sve ovo kada detaljnije pregledamo liste.
zadnji ušao - prvi izašao, "poslednji ušao - prvi izašao").Najčešće se princip rada hrpe uspoređuje sa hrpom ploča: da biste drugi uzeli odozgo, morate ukloniti gornji.
U nekim jezicima (npr. Lisp, Python) bilo koja lista se može nazvati stekom, jer su za njih dostupne pop i push operacije. U C ++ standardna biblioteka ima klasu sa implementiranom strukturom i metodama. itd.
Collegiate YouTube
1 / 3
Računarska nauka. Strukture podataka: Stack. Foxford Online Learning Center
#devet. Stack / 1. Asembler i procedure / Programiranje od nule
Osnove mreža za prenos podataka. OSI model i stog TCP IP protokola. Osnove Etherneta.
Titlovi
Softverski stog
Organizacija u sjećanju
Često se stek implementira kao jednosmjerna lista (svaka stavka na listi sadrži, pored informacija pohranjenih u steku, pokazivač na sljedeću stavku na steku).
Ali takođe se često stek nalazi u jednodimenzionalnom nizu sa uređenim adresama. Takva organizacija steka je zgodna ako stavka informacije zauzima fiksni broj riječi u memoriji, na primjer, 1 riječ. Ovo eliminira potrebu za pohranjivanjem eksplicitnog pokazivača na sljedeći element steka u elementu steka, čime se štedi memorija. U ovom slučaju, pokazivač steka ( Stack Pointer, - 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č gurne u stek, SP se prvo smanjuje za 1, a zatim se upisuje u memoriju na adresi sa SP-a. Svaki put kada se riječ iskoči iz steka (iskače), ona prvo čita trenutnu adresu iz SP-a, a zatim povećava SP sadržaj za 1.
Kada organizujete stek u obliku jednosmerne 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 * next;);
Stack operacije
Moguće su tri operacije steka: dodavanje stavke (u suprotnom guranje), uklanjanje stavke (pop) i čitanje glavne stavke (peek).
Guranje dodaje novi element koji pokazuje na element koji je prethodno bio glava. Novi element sada postaje glavni.
Kada se element obriše (pop), prvi se uklanja, a glava postaje ona na koju je ovaj objekt imao pokazivač (sljedeći element). U tom slučaju se vraća vrijednost uklonjenog elementa.
void push (STACK * ps, int x) // Dodaj novu stavku u stog(ako (ps -> veličina == STACKSIZE) // Je li stek prepun?(fputs ("Greška: prekoračenje steka \ n", stderr); prekinuti ();) else (ps -> stavke [ps -> size ++] = x;)) int pop (STACK * ps) // Uklonite iz steka(ako (ps -> veličina == 0) // Je li stek prazan?(fputs ("Greška: stek underflow \ n", stderr); abort ();) else (povratak ps -> items [- ps -> size];))
Područje primjene
Programski prikaz steka koristi se za prelazak struktura podataka kao što su stablo ili graf. Kada koristite rekurzivne funkcije, koristit će se i stek, ali njegov hardverski izgled. Pored ovih zadataka, stek se koristi za organizovanje
Slični procesi se dešavaju sa hardverskim prekidom (X86 procesor automatski sprema registar zastavica na stog tokom hardverskog prekida). Pored toga, prevodioci dodeljuju varijable lokalne procedure na steku (ako procesor obezbeđuje pristup proizvoljnoj lokaciji steka).
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 u stek (očigledno je da se stek u ROM-u, naravno, ne može organizovati). Aplikacioni programi, po pravilu, dobijaju od operativnog sistema stek spreman za upotrebu. U zaštićenom režimu procesora, segment stanja zadatka sadrži četiri selektora segmenta steka (za različite nivoe privilegija), ali se istovremeno koristi samo jedan stek.
