zadnji ušao - prvi izašao, "zadnji ušao - prvi izašao").

Najčešće se princip rada hrpe uspoređuje s hrpom ploča: da biste uzeli drugu s vrha, morate ukloniti gornju.

U nekim jezicima (na primjer, Lisp, Python), bilo koji popis može se nazvati stogom, budući da su za njih dostupne pop i push operacije. U C++ standardna biblioteka ima klasu s implementiranom strukturom i metodama. itd.

Enciklopedijski YouTube

1 / 3

Informatika. Strukture podataka: Stog. Foxfordov centar za online učenje

#9. Stog / 1. Asembler i procedure / Programiranje od nule

Osnove podatkovnih mreža. OSI model i stog TCP protokoli IP. Osnove Etherneta.

titlovi

Softverski skup

Organizacija u memoriji

Često se stog implementira kao jednosmjerna lista (svaki element na listi sadrži, osim informacija pohranjenih u stogu, pokazivač na sljedeći element niza).

Ali stog se također često nalazi u jednodimenzionalnom nizu s uređenim adresama. Ova organizacija stogova je prikladna ako element informacija zauzima memoriju fiksna količina riječi, na primjer, 1 riječ. Time se eliminira potreba za pohranjivanjem eksplicitnog pokazivača na sljedeći element niza u elementu niza, što štedi memoriju. U ovom slučaju, pokazivač steka ( Pokazivač snopa, - SP) obično je registar procesora i pokazuje na adresu glave steka.

Na primjer, pretpostavimo da se glava steka nalazi na nižoj adresi, sljedeći elementi nalaze se na rastućim adresama. Svaki put kad se riječ gurne na stog, SP se prvo smanji za 1, a zatim se adresa iz SP-a zapisuje u memoriju. Svaki put kada se riječ izbaci iz stoga, ona prvo čita trenutnu adresu iz SP-a, a zatim povećava sadržaj SP-a za 1.

Kada se stog organizira kao jednosmjerna lista, vrijednost varijable steka je pokazivač na njegov vrh - adresu vrha. Ako je stog prazan, tada je vrijednost pokazivača NULL.

Primjer implementacije stoga u C-u:

struct stack (char * data; struct stack * next;);

Operacije snopa

Postoje tri moguće operacije na stogu: dodavanje elementa (aka guranje), uklanjanje elementa (pop) i čitanje elementa glave (peek).

Prilikom guranja (guranja) dodaje se novi element, koji pokazuje na element koji je prethodno bio glava. Novi element sada postaje glavni.

Prilikom brisanja elementa (pop), prvi se uklanja, a glavni postaje onaj na koji je ovaj objekt imao pokazivač (sljedeći element). U tom slučaju vraća se vrijednost uklonjenog elementa.

void push (STACK * ps, int x) // Dodavanje novog elementa u stog( if ( ps -> size == STACKSIZE ) // Je li stog prepun?( fputs ( "Pogreška: stack overflow \n ", stderr); abort (); ) else ( ps -> items [ ps -> size ++ ] = x ; ) ) int pop ( STACK * ps ) // Ukloni sa stoga(ako (ps -> veličina == 0) // Je li stog prazan?( fputs ( "Pogreška: stack underflow \n ", stderr); abort (); ) else ( return ps -> items [ -- ps -> size ]; ) )

Područje primjene

Programski prikaz hrpe koristi se za prelaženje podatkovnih struktura, poput stabla ili grafikona. Korištenje rekurzivne funkcije Stog će se također koristiti, ali njegov hardverski tip. Osim u ove svrhe, stog se koristi za organiziranje

Slični se procesi događaju tijekom hardverskog prekida (X86 procesor s hardverski prekid automatski sprema registar oznaka na stog). Osim toga, prevoditelji postavljaju lokalne varijable procedure na stog (ako procesor ima pristup nasumičnim lokacijama stoga).

Prije nego što se stog može koristiti, mora se inicijalizirati tako da SS:ESP registri pokazuju na adresu glave stoga u fizičkom području. RAM memorija, a za pohranu podataka u stog potrebno je rezervirati potreban broj memorijskih ćelija (očito se stog u ROM-u, naravno, ne može organizirati). Aplikacijski programi, u pravilu, od operacijski sustav dobiti hrpu spremnog za jelo. U zaštićenom načinu rada procesora, segment stanja zadatka sadrži četiri birača segmenta stoga (za različite razine privilegije), ali se istovremeno koristi samo jedan stog.

Stog je programski fenomen i prirodno rješenje. Stack je odmah ušao u posao s računalima i postao toliko “domaći”, kao da je tu sve počelo.

Bez stoga procesor ne radi, nema rekurzije i nemoguće je organizirati učinkovite pozive funkcija. Svaki algoritam može bez reda čekanja, popisa, zbirke, niza ili sustava organiziranih objekata, ali ništa ne radi bez memorije i hrpa, uključujući sve gore navedeno.

U osvit početka: procesor, memorija i stog

Idealna memorija omogućuje adresiranje izravno na vrijednost - to su strojna i jezična razina visoki stupanj. U prvom slučaju, procesor sekvencijalno ponavlja memorijske adrese i izvršava instrukcije. U drugom slučaju, programer manipulira nizovima. Obje epizode sadrže:

• adresa = vrijednost;
• indeks = vrijednost.

Adresa može biti apsolutna i relativna, indeks može biti digitalni i asocijativni. Adresa i indeks mogu sadržavati drugu adresu osim vrijednosti, ali to su detalji neizravnog adresiranja. Bez memorije procesor ne može raditi, a bez hrpe naredbi i podataka je kao čamac bez vesala.

Hrpa tanjura tradicionalna je priča o biti hrpe: pojmu hrpe i prijevodu u općoj svijesti. Ne možete uzeti tanjur odozdo, možete ga uzeti samo odozgo, i tada će svi tanjuri biti netaknuti.

Što god dođe zadnje na hrpi, ide prvo. Savršeno rješenje. U biti, stack, kao prijevod jedne radnje u drugu, transformira ideju algoritma kao niza operacija.

Bit i pojam steka

Procesor i memorija glavni su građevni blokovi računala. Procesor izvršava instrukcije, manipulira memorijskim adresama te dohvaća i mijenja vrijednosti na tim adresama. U programskom jeziku sve se to pretvara u varijable i njihove vrijednosti. Suština steka i koncept zadnji ušao prvi izašao (LIFO) ostaje nepromijenjen.

Akronim LIFO više se ne koristi tako često kao prije. Vjerojatno zato što su liste pretvorene u objekte, a po potrebi se koriste redovi čekanja prvi ušao, prvi izašao (FIFO). Dinamika tipova podataka izgubila je na važnosti u kontekstu opisa varijabli, ali je dobila na značaju u trenutku izvođenja izraza: tip podatka je određen u trenutku njegove upotrebe, a do tog trenutka možete opisati bilo što i kako god želite.

Dakle, stack - što je to? Sada znate da je ovo neprikladno pitanje. Uostalom, bez stog nema moderno programiranje. Svaki poziv funkcije znači prosljeđivanje parametara i povratne adrese. Funkcija može pozvati drugu funkciju - to opet prosljeđuje parametre i povratnu adresu. Postavljanje mehanizma za pozivanje vrijednosti bez stoga dodatni je posao, iako je ostvarivo rješenje svakako moguće.

Mnogi ljudi pitaju: "Stack - što je to?" U kontekstu poziva funkcije, sastoji se od tri akcije:

• spremanje povratne adrese;
• spremanje svih prenesenih varijabli ili adresa na njih;
• poziv funkcije.

Nakon što pozvana funkcija završi svoju misiju, jednostavno će vratiti kontrolu na povratnu adresu. Funkcija može pozvati bilo koji broj drugih funkcija, budući da je ograničenje samo veličina stoga.

Svojstva skupa

Stog nije apstraktni tip podataka, već stvarni mehanizam. Na razini procesora, to je "motor" koji oplemenjuje i nadopunjuje rad ciklusa glavnog procesora. Poput aritmetike bitova, stog bilježi jednostavna i očita pravila rada. Pouzdan je i siguran.

Karakteristična svojstva steka su njegova veličina i duljina njegovih elemenata. Na razini procesora sve je određeno bitnim kapacitetom, adresiranjem memorije i fizikom pristupa njoj. Zanimljiva značajka i tradicija: stog raste prema dolje, odnosno prema opadanju memorijskih adresa, a programska i podatkovna memorija - prema gore. Ovo je uobičajeno, ali nije obavezno. Ovdje je važno značenje - došao je zadnji i otišao prvi. Ovo iznenađujuće jednostavno pravilo omogućuje vam izradu zanimljivih algoritama koji prvenstveno rade na jezicima visoka razina. Sada se više nećete pitati što je hrpa?

Besprijekoran rad hardver je već jako dugo norma, ali na čelu informacijske tehnologije Ideja hrpe dobiva nove i obećavajuće primjene.

U biti, nije važno kakav je stog na razini procesora. To je prirodni dio računalne arhitekture. Ali u programiranju, stog ovisi o specifičnoj primjeni i sposobnosti programera.

Nizovi, kolekcije, liste, redovi čekanja... Stog!

Ljudi često postavljaju pitanje: "Stack - što je to?" “Programiranje” i “sistematizacija” zanimljivi su pojmovi: nisu sinonimi, ali su tako blisko povezani. Programiranje je prešlo tako dug put vrlo brzo da se dosegnuti vrhunci čine idealnima. To najvjerojatnije nije slučaj. Ali očito nešto drugo.

Ideja stoga postala je poznata ne samo na razini različitih programskih jezika, već i na razini njihovog dizajna i mogućnosti kreiranja tipova podataka. Svaki niz ima push i pop, a koncepti "prvog i posljednjeg elementa niza" postali su tradicionalni. Ranije su postojali samo elementi niza, ali danas postoje:

• elementi niza;
• prvi element niza;
• zadnji element niza.

Operacija postavljanja elementa u niz pomiče pokazivač, a dohvaćanje elementa s početka ili s kraja niza čini razliku. U biti ovo je isti stog, ali primijenjen na druge vrste podataka.

Posebno je vrijedno istaknuti da popularni jezici programiranje nemaju konstrukciju stoga. Ali oni daju njegovu ideju programeru u cijelosti.

Stog je zbirka čiji se elementi dobivaju po principu zadnji ušao, prvi izašao. (Last-In-First-Out ili LIFO). To znači da ćemo imati pristup samo zadnjem dodanom elementu.

Za razliku od lista, ne možemo pristupiti proizvoljnom elementu steka. Elemente možemo dodavati ili uklanjati samo posebnim metodama. Nizovi također nemaju metodu Sadrži kao popisi. Također, stog nema iterator. Da bismo razumjeli zašto su takva ograničenja postavljena na stog, pogledajmo kako funkcionira i kako se koristi.

Najčešća analogija za objašnjenje hrpe je hrpa tanjura. Bez obzira na to koliko je ploča u hrpi, uvijek možemo ukloniti gornju. Čisti tanjuri se stavljaju na vrh hrpe na isti način, a uvijek ćemo prvi uzeti tanjur koji je zadnji stavljen.

Ako stavimo, na primjer, crvenu ploču, zatim plavu, pa zelenu, onda ćemo prvo morati ukloniti zelenu, zatim plavu i na kraju crvenu. Najvažnije je zapamtiti da se tanjuri uvijek stavljaju na vrh hrpe. Kad netko uzme tanjur, makne ga i s vrha. Ispada da se ploče rastavljaju suprotnim redoslijedom od onog u kojem su postavljene.

Sada kada razumijemo kako stog funkcionira, predstavimo nekoliko pojmova. Operacija dodavanja elementa u stog naziva se "push", a njegovo uklanjanje naziva se "pop". Posljednji dodan element naziva se vrh hrpe ili "vrh" i može se vidjeti pomoću operacije "peek". Pogledajmo sada predložak klase koja implementira stog.

Stack klasa

Klasa Stack definira metode Push, Pop, Peek za pristup elementima i polje Count. U implementaciji ćemo koristiti LinkedList za skladištenje elemenata.

Javna klasa Stack ( LinkedList _items = new LinkedList(); public void Push(T value) ( ​​​​throw new NotImplementedException(); ) public T Pop() ( throw new NotImplementedException(); ) public T Peek() ( throw new NotImplementedException( ) public int Count ( get ; ) )

Push metoda

• Ponašanje: Dodaje element na vrh hrpe.
• Složenost: O(1).

Budući da koristimo povezani popis za pohranu elemenata, možemo jednostavno dodati novi na kraj popisa.

Javni void Push(T value) ( ​​​​_items.AddLast(value); )

Pop metoda

• Ponašanje: Uklanja element s vrha stoga i vraća ga. Ako je stog prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

Push dodaje elemente na kraj liste, tako da će ih uzeti i s kraja. Ako je popis prazan, bit će izbačena iznimka.

Public T Pop() ( if (_items.Count == 0) ( throw new InvalidOperationException("Stop je prazan"); ) T rezultat = _items.Tail.Value; _items.RemoveLast(); vrati rezultat; )

Peek metoda

• Ponašanje: Povratak gornji element stog, ali ga ne briše. Ako je stog prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

public T Peek() ( if (_items.Count == 0) ( throw new InvalidOperationException("Stop je prazan"); ) return _items.Tail.Value; )

Metoda brojanja

• Ponašanje: Vraća broj elemenata u nizu.
• Složenost: O(1).

Zašto trebamo znati koliko je elemenata na stogu ako im ionako nemamo pristup? Ovim poljem možemo provjeriti ima li elemenata na stogu ili je prazan. Ovo je vrlo korisno s obzirom na to Pop metoda baca iznimku.

Primjer: kalkulator u obrnutom poljskom zapisu.

Klasičan primjer korištenja hrpe je kalkulator u obrnutom poljskom ili postfiksnom zapisu. U njemu je napisan operator nakon njihovi operandi. Odnosno, pišemo:

<операнд> <операнд> <оператор>

umjesto tradicionalnog:

<операнд> <оператор> <операнд>

Drugim riječima, umjesto “4 + 2” napisat ćemo “4 2 +”. Ako vas zanima podrijetlo obrnutog poljskog zapisa i njegov naziv, o tome se možete informirati na Wikipediji ili u tražilici.

Kako se izračunava obrnuta poljska notacija i zašto je stog 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čite lijevu i desnu vrijednost sa stoga procijenite operator gurnite rezultat na stog iskočite odgovor sa stoga .

To jest, za izraz "4 2 +" akcije će biti sljedeće:

Push(4) push(2) push(pop() + pop())

Na kraju će na hrpi biti jedna vrijednost - 6.

Sljedeće je puni kod jednostavan kalkulator, koji čita izraz (na primjer, 4 2 +) s konzole, dijeli unos razmacima (["4", "2", "+"]) i izvodi algoritam izračuna. Evaluacija 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; ) / / Stack vrijednosti koje još nisu obrađene. Stack values ​​​​= new Stack(); foreach (string token in input. Split(new char ( " ")) ( // Ako je vrijednost cijeli broj... int value; if (int. TryParse(token, out value)) ( // ... stavi na stog. values.Push(value); ) else ( // u protivnom izvrši operaciju... int rhs = values .Pop(); int lhs (); : vrijednosti.Push(lhs); break(lhs); break(lhs); Ako operacija nije +, -, * ili / throw new ArgumentException(string.Format("Unrecognized token: (0)", token) ) // Zadnji element na stogu je rezultat. Console.WriteLine(values .Pop()); ) )

Red

Redovi su vrlo slični hrpama. Oni također ne daju pristup proizvoljnom elementu, ali, za razliku od stoga, elementi su složeni (u red) i penjati se (izbaci iz reda) s raznih krajeva. Ova metoda se zove "prvi ušao, prvi izašao" (First-In-First-Out ili FIFO). To jest, pokupit ćemo elemente iz reda čekanja istim redoslijedom kojim smo ih stavili. Kao pravi red ili pokretna traka.

Redovi čekanja često se koriste u programima da bi se osigurao međuspremnik u koji se stavke mogu smjestiti za kasniju obradu uz očuvanje redoslijeda kojim stižu. Na primjer, ako baza podataka podržava samo jednu vezu, možete koristiti red niti koje će, čudno, čekati svoj red za pristup bazi podataka.

Klasa čekanja

Klasa Queue, kao i stog, bit će implementirana pomoću povezane liste. Omogućit će Enqueue za dodavanje elementa, Dequeue za uklanjanje, Peek i Count metode. Poput klase Stack, neće implementirati ICollection sučelje , budući da se radi o zbirkama posebne namjene.

Javna klasa Queue ( LinkedList _items = new LinkedList(); public void Enqueue(T value) ( ​​​​throw new NotImplementedException(); ) public T Dequeue() ( throw new NotImplementedException(); ) public T Peek() ( throw new NotImplementedException( ) public int Count ( get ; ) )

Metoda stavljanja u red čekanja

• Ponašanje: Dodaje element u red čekanja.
• Složenost: O(1).

Novi elementi reda mogu se dodati ili na početak ili na kraj liste. Važno je samo da se do elemenata dohvati sa suprotnog ruba. U ovoj implementaciji ćemo dodati nove elemente na početak interne liste.

Public void Enqueue(T value) ( ​​​​_items.AddFirst(value); )

Metoda dequeue

• Ponašanje: Uklanja prvi postavljeni element iz reda i vraća ga. Ako je red prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

Budući da elemente umećemo na početak liste, uklonit ćemo ih s kraja. Ako je popis prazan, izbacuje se iznimka.

Public T Dequeue() ( if (_items.Count == 0) ( throw new InvalidOperationException("Red je prazan"); ) T last = _items.Tail.Value; _items.RemoveLast(); return last; )

Peek metoda

• Ponašanje: Vraća element koji će biti vraćen sljedećim pozivom metode Dequeue. Red čekanja ostaje nepromijenjen. Ako je red prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

public T Peek() ( if (_items.Count == 0) ( throw new InvalidOperationException("Red je prazan"); ) return _items.Tail.Value; )

Metoda brojanja

• Ponašanje:
• Složenost: O(1).

public int Count ( get ( return _items.Count; ) )

Dvosmjerni red

Dvosmjerni red (Dvostruki red čekanja), ili pro (Deque), proširuje ponašanje reda čekanja. U dequeu možete dodati ili ukloniti elemente i s početka i s kraja reda. Ovo ponašanje je korisno u mnogim zadacima, kao što je planiranje niti ili implementacija drugih struktura podataka. Kasnije ćemo pogledati implementaciju stoga pomoću deque-a.

Deque klasa

Klasu Deque najlakše je implementirati korištenjem dvostruko povezane liste. Omogućuje pregled, brisanje i dodavanje elemenata na početak i kraj popisa. Glavna razlika između deque i običnog reda čekanja je u tome što su metode Enqueue, Dequeue i Peek podijeljene u parove kako bi radile s oba kraja popisa.

Javna klasa Deque ( LinkedList _items = new LinkedList(); public void EnqueueFirst(T value) ( ​​​​throw new NotImplementedException(); ) public void EnqueueLast(T value) ( ​​​​throw new NotImplementedException(); ) public T DequeueFirst( ) (baci novu NotImplementedException(); ) public T DequeueLast() (baci novu NotImplementedException(); ) public T PeekFirst() (baci novu NotImplementedException(); ) public T PeekLast() (baci novu NotImplementedException(); ) public int Broji (dobi;))

Metoda EnqueueFirst

• Ponašanje:
• Složenost: O(1).

public void EnqueueFirst(T value) ( ​​​​_items.AddFirst(value); )

Metoda EnqueueLast

• Ponašanje:
• Složenost: O(1).

public void EnqueueLast(T value) ( ​​​​_items.AddLast(value); )

Metoda DequeueFirst

• Ponašanje: Uklanja element s početka reda čekanja i vraća ga. Ako je red prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

public T DequeueFirst() ( if (_items.Count == 0) ( throw new InvalidOperationException("DequeueFirst pozvan kada je deque prazan"); ) T temp = _items.Head.Value; _items.RemoveFirst(); return temp; )

Metoda DequeueLast

• Ponašanje:
• Složenost: O(1).

public T DequeueLast() (if (_items.Count == 0) ( throw new InvalidOperationException("DequeueLast pozvan kada je deque prazan"); ) T temp = _items.Tail.Value; _items.RemoveLast(); return temp; )

PeekFirst metoda

• Ponašanje: Vraća element s početka reda bez njegove izmjene. Ako je red prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

public T PeekFirst() ( if (_items.Count == 0) ( throw new InvalidOperationException("PeekFirst pozvan kada je deque prazan"); ) return _items.Head.Value; )

PeekLast metoda

• Ponašanje:
• Složenost: O(1).

public T PeekLast() ( if (_items.Count == 0) ( throw new InvalidOperationException("PeekLast pozvan kada je deque prazan"); ) return _items.Tail.Value; )

Metoda brojanja

• Ponašanje: Vraća broj elemenata u redu ili 0 ako je red prazan.
• Složenost: O(1).

public int Count ( get ( return _items.Count; ) )

Primjer: Implementacija snopa

Deque se često koristi za implementaciju drugih struktura podataka. Pogledajmo primjer implementacije stoga pomoću njega.

Možda se pitate zašto implementirati stog temeljen na redu čekanja umjesto na povezanom popisu. Dva su razloga: izvedba i ponovno koristiti kodirati. Povezani popis ima dodatne troškove stvaranja čvorova i nema jamstva za lokalitet podataka: elementi se mogu nalaziti bilo gdje u memoriji, što uzrokuje veliki broj promašaja i degradacije performansi na razini procesora. Učinkovitija implementacija deque zahtijeva niz za pohranjivanje elemenata.

Međutim, implementacija stoga ili reda pomoću niza jest nije lak zadatak, ali implementacija deque-a na ovaj način i njegovo korištenje kao osnove za druge strukture podataka dat će nam ozbiljne prednosti u izvedbi i omogućiti nam ponovnu upotrebu koda. Time se smanjuju troškovi podrške.

Kasnije ćemo pogledati varijantu reda koja koristi niz, ali prvo pogledajmo klasu stog koja koristi dequeue:

Javna klasa Stack ( Deque _items = new Deque(); public void Push(T value) ( ​​​​_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 se svim rukovanjem pogreškama sada bavi klasa Deque, a osim toga, svaka optimizacija reda čekanja također će se odraziti na stog. Implementacija redovnog povratnog reda čekanja toliko je jednostavna da ćemo to ostaviti kao vježbu za čitatelja.

Pohranjivanje elemenata u nizu

Kao što je već spomenuto, implementacija reda pomoću niza ima svoje prednosti. Izgleda jednostavno, ali zapravo 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 povećanju unutarnjeg niza iz prethodnog članka o dinamičkim nizovima.

Kada se kreira red čekanja, unutar njega se stvara niz nulte duljine. Crvena slova "h" i "t" označavaju pokazivače _head i _tail pokazivače.

Deque deq = novi Deque(); deq.EnqueueFirst(1);

Deq.EnqueueLast(2);

Deq.EnqueueFirst(0);

Imajte na umu: indeks "glave" reda skočio je na početak popisa. Sada je prvi element koji će biti vraćen prilikom pozivanja metode DequeueFirst 0 (indeks 3).

Deq.EnqueueLast(3);

Niz je pun, pa će se prilikom dodavanja elementa dogoditi sljedeće:

• Algoritam rasta odredit će veličinu novog niza.
• Elementi se kopiraju u novi niz od glave do repa.
• Dodat će se novi element.

deq.EnqueueLast(4);

Sada da vidimo što se događa kada se element ukloni:

Deq.DequeueFirst();

Deq.DequeueLast();

Ključni trenutak: bez obzira na kapacitet ili popunjenost unutarnjeg niza, logično, sadržaj reda su elementi od “glave” do “repa”, uzimajući u obzir “cirkularnost”. Ovo se ponašanje također naziva "međuspremnik zvona".

Sada pogledajmo implementaciju.

Deque klasa (koristeći niz)

Sučelje reda čekanja temeljenog na nizu je isto kao u slučaju implementacije povezane liste. Nećemo ponavljati. Međutim, budući da je popis zamijenjen nizom, dodali smo nova polja - sam niz, njegovu veličinu i pokazivače na "rep" i "glavu" reda čekanja.

Javna klasa Deque ( T _items = new T; // Broj elemenata u redu. int _size = 0; // Indeks prvog (najstarijeg) elementa. int _head = 0; // Indeks posljednjeg (najnovijeg) elementa . int _tail = -1;

Algoritam rasta

Kada slobodno mjesto u unutarnjim krajevima polja potrebno ga je povećati, kopirati elemente i ažurirati pokazivače na "rep" i "glavu". Ova se operacija izvodi ako je potrebno tijekom dodavanja elementa. Parametar startingIndex koristi se za označavanje koliko polja treba ostaviti praznim na početku (u slučaju dodavanja na početak).

Primijetite kako se podaci dohvaćaju kada morate skočiti na početak niza kada idete od glave do repa.

Private void allocateNewArray(int initialIndex) ( int newLength = (_size == 0) ? 4: _size * 2; T newArray = new T; if (_size > 0) ( int targetIndex = initialIndex; // Kopiraj sadržaj... / / Ako niz nije u petlji, samo kopirajte elemente // U suprotnom, kopirajte od početka niza do kraja. // Ako je rep manji od glave, idite na početak (_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; }

Metoda EnqueueFirst

• Ponašanje: Dodaje element na početak reda čekanja. Ovaj će element biti uzet iz reda sljedeći kada se pozove metoda DequeueFirst.
• Složenost:

public void EnqueueFirst(T item) ( // Provjerite treba li niz povećati: if (_items.Length == _size) ( allocateNewArray(1); ) // Budući da niz nije pun i _head je veći od 0, // znamo da postoji razmak na početku niza if (_head > 0) ( _head--; ) else ( // U suprotnom moramo raditi u petlji. _head = _items.Length - 1; ) _items[_head] = item _size++ if ( _size == 1) ( // Ako smo dodali prvi element u prazan // red čekanja, on će biti i zadnji, tako da // moramo ažurirati i _tail. _tail = _head; ) )

Metoda EnqueueLast

• Ponašanje: Dodaje element na kraj reda čekanja. Ovaj će se element sljedeći put uzeti iz reda kada se pozove metoda DequeueLast.
• Složenost: O(1) u većini slučajeva; O(n) kada je potrebno proširenje polja.

public void EnqueueLast(T item) ( // Provjerite treba li niz povećati: if (_items.Length == _size) ( allocateNewArray(0); ) // Sada kada imamo odgovarajući niz, // if _tail je na kraju niza, moramo ići na početak if (_tail == _items.Length - 1) ( _tail = 0; ) else ( _tail++; ) _items[_tail] = item (_size == 1) ( // Ako smo dodali zadnji element u prazan // red čekanja, on će biti i prvi, tako da // moramo ažurirati _head _head = _tail;

Metoda DequeueFirst

• Ponašanje: Uklanja element s početka reda čekanja i vraća ga. Ako je red prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

public T DequeueFirst() ( if (_size == 0) ( throw new InvalidOperationException("The deque is empty"); ) T value = _items[_head]; if (_head == _items.Length - 1) ( // If head je postavljen na zadnji indeks, idi na početak niza _head = 0; else ( // Prijeđi na sljedeći element. _head++; ) _size--;

Metoda DequeueLast

• Ponašanje: Uklanja element s kraja reda čekanja i vraća ga. Ako je red prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

public T DequeueLast() ( if (_size == 0) ( throw new InvalidOperationException("The deque is empty"); ) T value = _items[_tail]; if (_tail == 0) ( // Ako je tail postavljen na početni niz, idi na kraj _items.Length - 1; // Idi na prethodni element. _tail--; _size--;

PeekFirst metoda

• Ponašanje: Vraća element s početka reda bez mijenjanja. Ako je red prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

public T PeekFirst() ( if (_size == 0) ( throw new InvalidOperationException("Deque is prazan"); ) return _items[_head]; )

PeekLast metoda

• Ponašanje: Vraća element s kraja reda bez njegove izmjene. Ako je red prazan, izbacuje InvalidOperationException.
• Složenost: O(1).

public T PeekLast() ( if (_size == 0) ( throw new InvalidOperationException("Deque is prazan"); ) return _items[_tail]; )

Metoda brojanja

• Ponašanje: Vraća broj elemenata u redu ili 0 ako je red prazan.
• Složenost: O(1).

public int Count ( get ( return _size; ) )

Nastavit će se

Sada smo završili četvrti dio naše serije članaka. U njemu smo promatrali hrpe i redove. Sljedeći put ćemo prijeći na stabla binarnog pretraživanja.

Koristimo sve naprednije programske jezike koji nam omogućuju pisanje manje koda i postizanje odličnih rezultata. Moraš platiti za ovo. Kako se sve rjeđe bavimo stvarima niske razine, normalno je da mnogi od nas ne razumiju baš što su hrpa i hrpa, kako zapravo funkcionira kompilacija, koja je razlika između statičkog i dinamičkog tipkanja itd. Ne kažem da svi programeri ne znaju za te koncepte - samo mislim da se ponekad isplati vratiti se takvim starim stvarima.

Danas ćemo govoriti samo o jednoj temi: hrpa i gomila. I stog i gomila odnose se na različite lokacije na kojima se odvija upravljanje memorijom, ali strategija za ovo upravljanje je radikalno drugačija.

Stog

Stog je područje RAM-a koje se stvara za svaku nit. Radi prema LIFO (Last In, First Out) redoslijedu, što znači da će posljednji komad memorije gurnut na stog biti prvi u redu koji će biti izbačen sa stoga. Svaki put kada funkcija deklarira novu varijablu, ona se dodaje na stog, a kada ta varijabla izađe iz opsega (na primjer, kada funkcija završi), automatski se uklanja sa stoga. Kada se varijabla steka oslobodi, to područje memorije postaje dostupno za druge varijable steka.

Zbog ove prirode hrpe, upravljanje memorijom je vrlo logično i jednostavno za CPU; ovo rezultira velikom brzinom, posebno zato što je vrijeme ciklusa ažuriranja bajta steka vrlo kratko, tj. ovaj bajt je najvjerojatnije vezan za predmemoriju procesora. Međutim, postoje i nedostaci ovog strogog oblika upravljanja. Veličina stoga je fiksna vrijednost, a prekoračenje ograničenja memorije dodijeljenog stogu rezultirat će prekoračenjem stoga. Veličina se postavlja kada se stream kreira, a svaka varijabla ima maksimalnu veličinu ovisno o tipu podataka. To vam omogućuje da ograničite veličinu nekih varijabli (kao što su cijeli brojevi) i prisiljava vas da deklarirate veličinu složenijih tipova podataka (kao što su nizovi) unaprijed, budući da im stog neće dopustiti da je promijene. Osim toga, varijable koje se nalaze na stogu uvijek su lokalne.

U konačnici, stog vam omogućuje da upravljate memorijom na najučinkovitiji način - ali ako trebate koristiti dinamičke strukture podataka ili globalne varijable, trebali biste pogledati hrpu.

Hrpa

Hrpa je spremište memorije, također smješteno u RAM-u, koje omogućuje dinamičku dodjelu memorije i ne funkcionira kao stog: to je samo skladište za vaše varijable. Kada dodijelite dio memorije na gomili za pohranjivanje varijable, može joj se pristupiti ne samo u niti, već u cijeloj aplikaciji. Ovako se definiraju globalne varijable. Kada se aplikacija prekine, oslobađa se sva dodijeljena memorija. Veličina hrpe se postavlja kada se aplikacija pokrene, ali je, za razliku od stoga, samo fizički ograničena, a to vam omogućuje stvaranje dinamičkih varijabli.

S hrpom komunicirate putem referenci, koje se obično nazivaju pokazivači - to su varijable čije su vrijednosti adrese drugih varijabli. Kada stvorite pokazivač, pokazujete na memorijsku lokaciju na gomili, koja postavlja početnu vrijednost varijable i govori programu gdje da pristupi toj vrijednosti. Zbog dinamičke prirode hrpe, CPU ne sudjeluje u njenoj kontroli; U jezicima bez skupljača smeća (C, C++), programer mora ručno osloboditi područja memorije koja više nisu potrebna. Ako se to ne učini, može doći do curenja memorije i fragmentacije, što će značajno usporiti hrpu.

U usporedbi sa stogom, hrpa je sporija jer su varijable razbacane po memoriji umjesto da stoje na vrhu stoga. Neispravno upravljanje memorijom u hrpi dovodi do usporavanja njezina rada; međutim, to ne umanjuje njegovu važnost - ako trebate raditi s dinamičkim ili globalnim varijablama, koristite gomilu.

Stog

Stog je najpopularnija i možda najvažnija struktura podataka u programiranju. Stog je uređaj za pohranu iz kojeg se elementi uklanjaju obrnutim redoslijedom od njihovog dodavanja. To je poput nepravilnog reda u kojem je prvi uslužen onaj koji je zadnji došao u red. U literaturi o programiranju općenito su prihvaćene kratice za označavanje discipline reda i stoga. Disciplina čekanja označena je kao FIFO, što znači prvi ušao prvi izašao. Disciplina slaganja označena je kao LIFO, posljednji ušao prvi izašao (Last In First Out).

Stog se može zamisliti kao cijev s dnom s oprugom, smještena okomito. Gornji kraj cijevi je otvoren, mogu se dodavati elementi, ili, kako se kaže, uguravati u njega. Uobičajeni engleski izrazi u tom pogledu vrlo su šareni; operacija dodavanja elementa u hrpu označava se kao push, što se prevodi kao "gurnuti, gurnuti". Novi element koji se dodaje gura elemente koji su prethodno postavljeni na hrpu jednu poziciju prema dolje. Kada se elementi iskaču iz hrpe, oni se guraju prema gore, na engleskom pop (“pucaj”).

Primjer hrpe bio bi plast sijena, hrpa papira na stolu, hrpa tanjura itd. Odatle dolazi naziv stack, što na engleskom znači hrpa. Ploče se uklanjaju iz hrpe obrnutim redoslijedom od dodavanja. Dostupna je samo gornja ploča, tj. tanjur na vrhu hrpe. Dobar primjer bi također bila željeznička slijepa ulica u kojoj se mogu slagati automobili.

Stog se koristi prilično često iu raznim situacijama. Ujedinjuje ih sljedeći cilj: trebate spremiti neki posao koji još nije dovršen, ako se trebate prebaciti na drugi zadatak. Stog se koristi za privremeno pohranjivanje stanja zadatka koji još nije dovršen. Nakon spremanja stanja računalo prelazi na drugi zadatak. Po završetku njegovog izvršenja, stanje odgođenog zadatka se vraća sa stoga, a računalo nastavlja prekinuti rad.

Zašto se stog koristi za spremanje stanja prekinutog posla? Pretpostavimo da računalo izvršava zadatak A. Tijekom njegovog izvršavanja javlja se potreba za izvršenjem zadatka B. Stanje zadatka A se pamti i računalo nastavlja s izvršavanjem zadatka B. Ali čak i kada izvršava zadatak B, računalo se može prebaciti drugom zadatku C, i morat će se spremiti stanje zadatka B prije prelaska na C. Kasnije, nakon završetka C, prvo će se vratiti stanje zadatka B, a zatim, nakon završetka B, stanje zadatak A. Dakle, restauracija se odvija obrnutim redoslijedom od spremanja, što odgovara disciplini slaganja.

Stog vam omogućuje organiziranje rekurzije, tj. potprogram poziva sam sebe, bilo izravno ili kroz lanac drugih poziva. Na primjer, neka rutina A izvrši algoritam koji ovisi o ulaznom parametru X i eventualno o stanju globalnih podataka. Za najjednostavnije vrijednosti X, algoritam se implementira izravno. U slučaju složenijih vrijednosti X, algoritam se implementira kao redukcija na primjenu istog algoritma za jednostavnije vrijednosti X. U ovom slučaju, potprogram A pristupa sebi, prosljeđujući jednostavniju vrijednost X kao s ovim pristupom, prethodna vrijednost parametra X, kao i sve lokalne varijable rutine A pohranjuju se na stog. Zatim se kreira novi skup lokalnih varijabli i varijabla koja sadrži novu (jednostavniju) vrijednost parametra X. Pozvana podrutina A radi na novom skupu varijabli bez uništavanja prethodnog skupa. Na kraju poziva, stari skup lokalnih varijabli i staro stanje ulaznog parametra X vraćaju se iz stoga, a rutina nastavlja tamo gdje je stala.

Zapravo, ne morate čak ni spremati vrijednosti lokalnih varijabli potprograma na stog na poseban način. Činjenica je da su lokalne varijable potprograma (tj. njegove interne, radne varijable, koje se stvaraju na početku njegovog izvođenja i uništavaju na kraju) smještene na hrpu implementiranu u hardveru temeljenom na običnom RAM-u. Na samom početku svog rada potprogram grabi prostor na stogu za svoje lokalne varijable; ovo područje memorije u hardverskom stogu se obično zove blok lokalne varijable ili na engleskom okvir("okvir"). U trenutku završetka rada, potprogram oslobađa memoriju uklanjanjem bloka svojih lokalnih varijabli sa stoga.

Uz lokalne varijable, povratne adrese za pozive potprograma pohranjene su na hardverskom stogu. Neka potprogram bude pozvan u nekom trenutku u programu A B. Prije nego što se pozove potprogram B, adresa instrukcije koja slijedi nakon instrukcije koja poziva B pohranjuje se na stog. Ovo je tzv Povratna adresa u program A. Kada završi, potprogram B izbacuje povratnu adresu programa A iz stoga i vraća kontrolu na tu adresu. Dakle, računalo nastavlja izvršavati program A, počevši od instrukcije koja slijedi nakon instrukcije poziva. Većina procesora ima posebne instrukcije koje podržavaju pozivanje potprograma tako da prvo gurnu povratnu adresu na stog i vrate se iz potprograma na adresu izvađenu sa stoga. Obično se naredba poziva zove poziv, naredba povratka se zove povratak.

Parametri potprograma ili funkcije također se guraju na stog prije nego što se pozove. Redoslijed kojim su postavljeni na stog ovisi o konvencijama jezika visoke razine. Dakle, u jeziku C ili C++, prvi argument funkcije je na vrhu stoga, drugi je ispod njega, i tako dalje. U Pascalu je obrnuto: zadnji argument funkcije je na vrhu stoga. (Ovo je razlog zašto su, usput rečeno, funkcije s promjenjivim brojem argumenata, kao što je printf, moguće u C-u, ali ne i u Pascalu.)

U Fortran-4, jednom od najstarijih i najuspješnijih programskih jezika, argumenti se propuštaju kroz posebno memorijsko područje, koje se ne smije nalaziti na stogu, budući da su do kraja 70-ih godina 20. stoljeća još uvijek postojala računala poput IBM 360 ili ES računala bez sklopa implementacije hardvera. Povratne adrese također nisu bile pohranjene na stogu, već u memorijskim ćelijama fiksiranim 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 tijekom izvođenja programa. Kada se koristi samo statička memorija, rekurzija nije moguća jer se prethodne vrijednosti lokalnih varijabli uništavaju kada se napravi novi poziv. Referentni Fortran 4 koristio je samo statičke varijable, a rekurzija je bila zabranjena. Do sada se jezik Fortran široko koristi u znanstvenim i inženjerskim izračunima, međutim, moderni standard Fortran-90 već uvodi memoriju stogova, uklanjajući nedostatke ranijih verzija jezika.