Mikä on pino? Tietorakenteet: yleinen käsite, toteutus. Yksinkertaisimmat tietorakenteet: jono, pino. Pinon ja käänteisen puolan merkintätavan käyttäminen

Stack on ohjelmointiilmiö ja luonnollinen ratkaisu. Stack tuli välittömästi tietokonealalle ja siitä tuli niin "natiivi", ikään kuin siitä kaikki alkoi.

Ilman pinoa prosessori ei toimi, ei ole rekursiota, ja tehokkaiden toimintokutsujen järjestäminen on mahdotonta. Mikä tahansa algoritmi pärjää ilman jonoa, luetteloa, kokoelmaa, taulukkoa tai järjestettyjen objektien järjestelmää, mutta mikään ei toimi ilman muistia ja pinoa, mukaan lukien kaikki edellä mainitut.

Alun kynnyksellä: prosessori, muisti ja pino

Ihanteellinen muisti tarjoaa osoitteen suoraan arvoon - nämä ovat korkean tason kone- ja kielitasoja. Ensimmäisessä tapauksessa prosessori iteroi peräkkäin muistiosoitteiden läpi ja suorittaa käskyjä. Toisessa tapauksessa ohjelmoija käsittelee taulukoita. Molemmat jaksot sisältävät:

• osoite = arvo;
• indeksi = arvo.

Osoite voi olla absoluuttinen ja suhteellinen, indeksi voi olla digitaalinen ja assosiatiivinen. Osoite ja indeksi voivat sisältää muun osoitteen kuin arvon, mutta nämä ovat epäsuoran osoittamisen yksityiskohtia. Ilman muistia prosessori ei voi toimia, ja ilman komentojen ja tietojen pinoa se on kuin vene ilman airoja.

Lautaspino on perinteinen novelli pinon olemuksesta: pinon käsitteestä ja käännöksestä yhteisessä tietoisuudessa. Et voi ottaa lautasta alhaalta, voit ottaa sen vain ylhäältä, ja sitten kaikki lautaset ovat ehjiä.

Se mikä tulee pinossa viimeisenä, menee ensin. Täydellinen ratkaisu. Pohjimmiltaan pino, toimintojen käännöksenä toiseksi, muuttaa idean algoritmista toimintosarjaksi.

Pinon olemus ja käsite

Prosessori ja muisti - pää rakenneosat tietokone. Prosessori suorittaa käskyjä, käsittelee muistiosoitteita ja hakee ja muuttaa arvoja näissä osoitteissa. Ohjelmointikielessä tämä kaikki muunnetaan muuttujiksi ja niiden arvoiksi. Pinon olemus ja viimeinen ensin ulos (LIFO) -konsepti pysyvät ennallaan.

Lyhennettä LIFO ei enää käytetä niin usein kuin ennen. Luultavasti siksi, että listat on muunnettu objekteiksi ja FIFO-jonoja käytetään tarpeen mukaan. Tietotyyppien dynamiikka on menettänyt merkityksensä muuttujien kuvauksen yhteydessä, mutta on saanut merkityksensä lausekkeiden suoritushetkellä: tiedon tyyppi määräytyy sen käyttöhetkellä, ja siihen asti voidaan kuvata. mitä tahansa ja miten haluat.

Joten pino - mikä se on? Nyt tiedät, että tämä on sopimaton kysymys. Loppujen lopuksi ilman pinoa ei ole moderni ohjelmointi. Mikä tahansa funktiokutsu tarkoittaa parametrien ja paluuosoitteen välittämistä. Funktio voi kutsua toista funktiota - tämä taas välittää parametreja ja paluuosoitetta. Arvojen kutsumismekanismin luominen ilman pinoa on ylimääräistä työtä, vaikka saavutettavissa oleva ratkaisu on varmasti mahdollinen.

Monet ihmiset kysyvät: "Pino - mikä se on?" Funktiokutsun yhteydessä se koostuu kolmesta toiminnosta:

• palautusosoitteen tallentaminen;
• tallentaa kaikki siirretyt muuttujat tai osoitteet niihin;
• toimintokutsu.

Kun kutsuttu toiminto on suorittanut tehtävänsä, se yksinkertaisesti palauttaa ohjauksen palautusosoitteeseen. Funktio voi kutsua mitä tahansa muita toimintoja, koska raja on vain pinon koko.

Pinon ominaisuudet

Pino ei ole abstrakti tietotyyppi, vaan todellinen mekanismi. Prosessoritasolla se on "moottori", joka jalostaa ja täydentää pääprosessorisyklin työtä. Kuten bittiaritmetiikka, pino tallentaa yksinkertaiset ja ilmeiset toimintasäännöt. Se on luotettava ja turvallinen.

Pinon tunnusomaisia ​​ominaisuuksia ovat sen koko ja elementtien pituus. Prosessoritasolla kaiken määrää bittikapasiteetti, muistin osoitus ja siihen pääsyn fysiikka. Mielenkiintoinen ominaisuus ja perinne: pino kasvaa alaspäin, eli kohti väheneviä muistiosoitteita ja ohjelma- ja datamuisti - ylöspäin. Tämä on yleistä, mutta ei pakollista. Merkitys tässä on tärkeä - hän tuli viimeisenä ja lähti ensimmäisenä. Tämän yllättävän yksinkertaisen säännön avulla voit rakentaa mielenkiintoisia algoritmeja, jotka toimivat ensisijaisesti kielillä korkeatasoinen. Nyt et kysy, mikä on pino?

Moitteeton työ laitteisto on ollut normi jo pitkään, mutta eturintamassa tietotekniikat Ajatus pinosta on saamassa uusia ja lupaavia sovelluksia.

Pohjimmiltaan sillä ei ole väliä, mikä pino on prosessoritasolla. Se on luonnollinen osa tietokonearkkitehtuuria. Mutta ohjelmoinnissa pino riippuu tietystä sovelluksesta ja ohjelmoijan kyvystä.

Taulukot, kokoelmat, luettelot, jonot... Pino!

Ihmiset kysyvät usein kysymyksen: "Pino - mikä se on?" "Ohjelmointi" ja "järjestelmästäminen" ovat mielenkiintoisia käsitteitä: ne eivät ole synonyymejä, mutta ne liittyvät läheisesti toisiinsa. Ohjelmointi on mennyt niin pitkälle hyvin nopeasti, että saavutetut huiput näyttävät ihanteellisilta. Näin ei todennäköisesti ole. Mutta ilmeisesti jotain muuta.

Ajatus pinosta on tullut tutuksi paitsi tasolla eri kieliä ohjelmointia, mutta myös niiden suunnittelun ja tietotyyppien luontikyvyn tasolla. Kaikissa taulukoissa on push ja pop, ja käsitteistä "taulukon ensimmäinen ja viimeinen elementti" on tullut perinteisiä. Aiemmin oli vain taulukkoelementtejä, mutta nykyään niitä on:

• matriisin elementit;
• taulukon ensimmäinen elementti;
• taulukon viimeinen elementti.

Elementin sijoittaminen taulukkoon siirtää osoitinta, ja elementin hakeminen taulukon alusta tai sen lopusta vaikuttaa asiaan. Pohjimmiltaan tämä on sama pino, mutta sitä sovelletaan muihin tietotyyppeihin.

On erityisen huomionarvoista, että suosituilla ohjelmointikielillä ei ole pinorakennetta. Mutta he tarjoavat hänen ideansa kehittäjälle kokonaisuudessaan.

Käytämme yhä kehittyneempiä ohjelmointikieliä, joiden avulla voimme kirjoittaa vähemmän koodia ja saada erinomaisia ​​tuloksia. Sinun on maksettava tästä. Koska käsittelemme matalan tason juttuja yhä harvemmin, on normaalia, että monet meistä eivät täysin ymmärrä, mitä pino ja kasa ovat, miten kääntäminen käytännössä toimii, mitä eroa on staattisen ja dynaamisen kirjoittamisen välillä jne. En väitä, että kaikki ohjelmoijat eivät tietäisi näistä käsitteistä - mielestäni vain, että joskus kannattaa palata sellaisiin vanhan koulukunnan asioihin.

Tänään puhumme vain yhdestä aiheesta: pino ja pino. Sekä pino että pino viittaavat eri paikkoihin, joissa muistinhallinta tapahtuu, mutta tämän hallinnan strategia on radikaalisti erilainen.

Pino

Pino on alue RAM-muisti, joka luodaan jokaiselle säikeelle. Se toimii LIFO-järjestyksessä (Last In, First Out), mikä tarkoittaa, että viimeinen pinoon työnnetty muisti on ensimmäinen, joka ponnahtaa pois pinosta. Joka kerta kun funktio ilmoittaa uuden muuttujan, se lisätään pinoon, ja kun kyseinen muuttuja menee soveltamisalan ulkopuolelle (esimerkiksi funktion päättyessä), se poistetaan automaattisesti pinosta. Kun pinomuuttuja vapautetaan, tämä muistialue vapautuu muille pinomuuttujille.

Pinon tämän luonteen vuoksi muistinhallinta on erittäin loogista ja helppoa suorittimella; Tämä johtaa suuri nopeus, varsinkin koska pinotavujen päivitysjakson aika on hyvin lyhyt, ts. tämä tavu on todennäköisesti sidottu prosessorin välimuistiin. Tässä tiukassa hallintomuodossa on kuitenkin myös haittoja. Pinon koko on kiinteä arvo, ja pinolle varatun muistin rajan ylittäminen johtaa pinon ylivuotoon. Koko asetetaan lankaa luotaessa, ja jokaisella muuttujalla on enimmäiskoko, riippuen tietotyypistä. Tämän avulla voit rajoittaa joidenkin muuttujien (kuten kokonaislukujen) kokoa ja pakottaa sinut ilmoittamaan monimutkaisempien tietotyyppien (kuten taulukoiden) koon etukäteen, koska pino ei anna niiden muuttaa sitä. Lisäksi pinossa olevat muuttujat ovat aina paikallisia.

Loppujen lopuksi pinon avulla voit hallita muistia tehokkaimmalla tavalla - mutta jos sinun on käytettävä dynaamiset rakenteet dataa tai globaaleja muuttujia, sinun tulee kiinnittää huomiota kasaan.

Pino

Kasa on muistivarasto, joka sijaitsee myös RAM-muistissa ja joka mahdollistaa dynaamisen muistin varauksen eikä toimi pinon tavoin: se on vain muuttujien varasto. Kun varaat keon muistin muuttujan tallentamista varten, sitä voidaan käyttää paitsi säikeessä, myös koko sovelluksessa. Näin määritellään globaalit muuttujat. Kun sovellus sulkeutuu, kaikki varattu muisti vapautetaan. Pinon koko asetetaan sovelluksen käynnistyessä, mutta toisin kuin pino, se on vain fyysisesti rajoitettu, mikä mahdollistaa dynaamisten muuttujien luomisen.

Olet vuorovaikutuksessa kasan kanssa viitteiden kautta, joita kutsutaan yleisesti osoittimiksi - nämä ovat muuttujia, joiden arvot ovat muiden muuttujien osoitteita. Kun luot osoittimen, osoitat kasan muistipaikkaan, joka määrittää alkuarvo muuttuja ja kertoo ohjelmalle, mistä tämä arvo pääsee käsiksi. Keon dynaamisesta luonteesta johtuen CPU ei osallistu sen hallintaan; Kieleillä, joissa ei ole roskakoria (C, C++), kehittäjän on vapautettava manuaalisesti muistialueita, joita ei enää tarvita. Jos näin ei tehdä, voi tapahtua muistivuotoja ja pirstoutumista, mikä hidastaa kasaa merkittävästi.

Pinoon verrattuna kasa on hitaampi, koska muuttujat ovat hajallaan muistissa sen sijaan, että ne olisivat pinon päällä. Virheellinen muistinhallinta kasassa johtaa sen toiminnan hidastumiseen; Tämä ei kuitenkaan vähennä sen merkitystä - jos sinun on työskenneltävä dynaamisten tai globaalien muuttujien kanssa, käytä pinoa.

Ohjelmien käyttämä muisti koostuu useista osista − segmenttejä:

koodisegmentti(tai "tekstisegmentti"), jossa käännetty ohjelma sijaitsee. Koodisegmentti on yleensä vain luku -tilassa;

bss-segmentti(tai "alustamaton datasegmentti"), johon tallennetaan globaalit ja nolla-alustetut arvot;

datasegmentti(tai "alustettu datasegmentti"), johon alustetut globaalit ja staattiset muuttujat tallennetaan;

Vastaanottajaopetusta(kasa), josta dynaamiset muuttujat allokoidaan;

kutsupino, johon on tallennettu paikallisia muuttujia ja muuta toimintoihin liittyvää tietoa.

Tässä opetusohjelmassa tarkastellaan vain kasaa ja pinoa, koska siellä kaikki hauska tapahtuu.

Pino

Kasan segmentti(tai yksinkertaisesti" Muutama") pitää kirjaa dynaamiseen varaukseen käytetystä muistista. Olemme jo puhuneet hieman kasasta.

C++:ssa, kun käytät uutta operaattoria dynaamisen muistin varaamiseen, tämä muisti varataan sovelluksen omaan kasasegmenttiin.

int *ptr = uusi int; // ptr varaa 4 tavua pinosta int *array = new int; // taulukko varaa 40 tavua kasasta

Uusi operaattori välittää varatun muistin osoitteen takaisin, ja se voidaan sitten tallentaa hakemistoon. Tietoja tallennus- ja allokointimekanismista vapaa muisti Meillä ei ole nyt mitään hätää. On kuitenkin syytä tietää, että peräkkäiset muistipyynnöt eivät aina johda peräkkäisten muistiosoitteiden allokointiin!

int *ptr1 = uusi int; int *ptr2 = uusi int; // ptr1:llä ja ptr2:lla ei välttämättä ole peräkkäisiä osoitteita

Kun dynaamisesti varattu muuttuja poistetaan, muisti palautetaan takaisin kasaan, ja se voidaan sitten osoittaa uudelleen (myöhempien pyyntöjen perusteella). Muista, että osoittimen poistaminen ei poista muuttujaa, se yksinkertaisesti palauttaa kyseisen osoitteen muistin takaisin käyttöjärjestelmään.

Kasalla on hyvät ja huonot puolensa:

Muistin varaaminen kasassa on suhteellisen hidasta.

Varattu muisti pysyy varattuna, kunnes se vapautetaan (varo muistivuotoja) tai kunnes sovellus sulkeutuu (jolloin käyttöjärjestelmän on otettava muisti takaisin).

Dynaamisesti varattuun muistiin pääsee vain osoittimen kautta. Osoittimen viittauksen purkaminen on hitaampaa kuin muuttujan käyttäminen suoraan.

Koska kasa on suuri muistivarasto, sitä käytetään suurten luokkien jakamiseen.

Kutsupino

Kutsupino(tai yksinkertaisesti" pino") on paljon mielenkiintoisempi rooli. Kutsupino pitää kirjaa kaikista aktiivisista toiminnoista (ne jotka on kutsuttu mutta joita ei ole vielä suoritettu) ohjelman alusta nykyinen piste suoritus ja hoitaa kaikkien funktioparametrien ja paikallisten muuttujien allokoinnin.

Puhelupino on toteutettu pinotietorakenteena. Joten ennen kuin puhumme puhelupinon toiminnasta, meidän on ymmärrettävä, mikä "pino" on tietorakenteena.

Pinotietorakenne

Tietorakenne on ohjelmoinnin mekanismi tiedon järjestämiseksi, jotta sitä voidaan käyttää tehokkaasti. Olet jo nähnyt useita tietorakenteita, kuten taulukoita ja rakenteita. Ne tarjoavat mekanismeja tietojen tehokkaaseen tallentamiseen ja käyttöön. Ohjelmoinnissa yleisesti käytettyjä lisätietorakenteita on monia muitakin, joista osa on toteutettu tavallinen kirjasto C++ ja "Stack" on yksi niistä.

Harkitse lautaspinoa pöydällä. Koska jokainen levy on painava ja ne on pinottu (toistensa päälle), voit tehdä vain yhden seuraavista kolmesta asiasta:

Katso ylälevyn pintaa.

Ota ylälevy pinosta (näin paljastaa seuraavan, joka on alla - jos sellaista on ollenkaan).

Aseta uusi lautanen pinon päälle (piilottaen ylimmän lautasen alle, jos sellainen oli).

SISÄÄN tietokoneohjelmointi Pino on konttimainen tietorakenne, joka sisältää useita muuttujia (samanlainen kuin taulukko). Vaikka taulukon avulla voit kuitenkin käyttää ja muuttaa elementtejä missä tahansa järjestyksessä (ns. satunnainen pääsy"), pino on rajoitetumpi. Toiminnot, jotka voidaan suorittaa pinossa, vastaavat kolmea edellä lueteltua. Pinolla voit:

Katso yläelementti pinossa (käyttämällä toimintoa alkuun() tai kurkistaa() ).

Vedä pinon yläosa ulos (käytä toimintoa pop() ).

Lisätä uusi elementti pinon yläosaan (käytä toimintoa työntää() ).

Pino on rakenteen kaltainen LIFO(Viimeinen sisään, ensimmäinen ulos - viimeisenä saapuva, ​​ensimmäisenä lähtevä). Viimeinen elementti, joka on sijoitettu pinon päälle, tulee ensimmäisenä pois pinosta. Jos asetat uuden lautasen pinon päälle muita lautasia, se on ensimmäinen, jonka poimit. Kun elementtejä työnnetään pinoon, pino kasvaa, kun elementtejä poistetaan pinosta, pino kutistuu.

Harkitse esimerkiksi lyhyttä sarjaa, joka näyttää kuinka pinon lisääminen ja poistaminen toimii:

Pino: tyhjä
Työnnä 1
Pino: 1
Työnnä 2
Pino: 12
Työnnä 3
Pino: 1 2 3
Työnnä 4
Pino: 1 2 3 4
Pop
Pino: 1 2 3
Pop
Pino: 12
Pop
Pino: 1

Levypino on melko hyvä analogia pinon toimivuudelle, mutta on olemassa parempi analogia. Harkitse esimerkiksi useita postilaatikoita, jotka sijaitsevat päällekkäin. Jokainen postilaatikko voi sisältää vain yhden viestin, ja kaikki postilaatikot ovat aluksi tyhjiä. Lisäksi jokainen postilaatikko on naulattu postilaatikon pohjaan, joten postilaatikoiden määrää ei voi muuttaa. Jos emme voi muuttaa postilaatikoiden määrää, kuinka voimme saada pinoa muistuttavan toiminnan?

Ensin käytämme tarraa osoittamaan, missä on alin tyhjä postilaatikko. Aluksi tämä on ensimmäinen postilaatikko, joka on lattialla. Kun lisäämme lähetyksen postilaatikkopinoihimme, sijoitamme sen postilaatikkoon, jossa tarra tulee olemaan (eli ensimmäiseen tyhjään postilaatikkoon lattialla), ja siirrämme sitten tarran yhden postilaatikon korkeammalle. Kun ponnamme elementin pinosta, siirrämme tarraa yhden postilaatikon alaspäin ja poistamme elementin postilaatikko. Kaikki merkin alla oleva on pinossa. Kaikki, mikä on laatikossa, jossa on tarra tai yli, ei ole pinossa.

Puhelupinon segmentti

Puhelupinosegmentti sisältää muistia, jota käytetään puhelupinolle. Kun aloitat sovelluksen, päätoiminto() työnnetään puhelupinoon käyttöjärjestelmä. Sen jälkeen ohjelma aloittaa suoritusnsa.

Kun ohjelma kohtaa funktiokutsun, funktio työnnetään kutsupinoon. Kun funktio on suorittanut loppuun, se poistetaan kutsupinosta. Tällä tavalla pinoon lisättyjä toimintoja tarkasteltaessa voimme nähdä kaikki funktiot, jotka on kutsuttu nykyiseen suorituspisteeseen.

Postilaatikko-analogiamme on todella se, miten puhelupino toimii. Puhelupinossa on kiinteä määrä muistiosoitteita ( kiinteä koko). Postilaatikot ovat muistiosoitteita, ja pinoon lisäämämme ja pinoon asettamamme "kohteet" kutsutaan kehyksiä(tai enemmän " henkilöstöä") pino. Pinokehys pitää kirjaa kaikista yhteen toimintokutsuun liittyvistä tiedoista. "Tarra" on rekisteri ( pieni osa CPU:n muisti), joka on pinoosoitin. Pinoosoitin seuraa, missä puhelupinon yläosa sijaitsee.

Ainoa ero todellisen puhelupinon ja hypoteettisen postilaatikkopinon välillä on se, että kun ponnamme elementin puhelupinosta, meidän ei tarvitse tyhjentää muistia (eli ponnahtaa postilaatikon koko sisältöä). Voimme jättää tämän muiston vain seuraava elementti, joka korvaa sen. Koska pinoosoitin on tämän muistiosoitteen alapuolella, niin kuten jo tiedämme, tämä muistipaikka ei ole pinossa.

Puhelupino käytännössä

Katsotaanpa tarkemmin, kuinka puhelupino toimii. Alla on funktiota kutsuttaessa suoritettavien vaiheiden sarja:

Ohjelma kohtaa funktiokutsun.

Pinokehys luodaan ja asetetaan pinoon, se koostuu:

Sen käskyn osoite, joka sijaitsee funktiokutsun takana (ns. palautusosoite "). Näin prosessori muistaa minne palata toiminnon suorittamisen jälkeen.

Funktioargumentit.

Muisti paikallisille muuttujille.

Tallennetut kopiot kaikista funktion muokkaamista rekistereistä, jotka on palautettava sen jälkeen, kun toiminto on suorittanut loppuun.

Prosessori siirtyy toiminnon aloituspisteeseen.

Toiminnon sisällä olevat ohjeet alkavat suorittaa.

Kun toiminnot on suoritettu, ne suoritetaan Seuraavat vaiheet :

Rekisterit palautetaan puhelupinosta.

Pinon runko pompataan pinosta. Kaikkien paikallisten muuttujien ja argumenttien muisti vapautetaan.

Palautusarvo käsitellään.

CPU jatkaa koodin suorittamista (palautusosoitteen perusteella).

Palautusarvot voidaan käsitellä eri tavoilla, riippuen tietokoneen arkkitehtuurista. Jotkut arkkitehtuurit pitävät palautusarvoa osana pinokehystä. Toiset käyttävät prosessorirekistereitä.

Kaikkien puhelupinon toiminnan yksityiskohtien tunteminen ei ole niin tärkeää. Kuitenkin sen ymmärtäminen, että funktioita lisätään pinoon kutsuttaessa ja poistetaan pinosta kutsuttaessa, antaa perustiedot, joita tarvitaan rekursion ymmärtämiseen sekä joitain muita hyödyllisiä käsitteitä .

Esimerkki puhelupinosta

Harkitse seuraavaa koodinpätkää:

Tämän ohjelman puhelupino näyttää tältä:

boo() (mukaan lukien parametri b)
pää()

Pinon ylivuoto

Pinon koko on rajoitettu ja siksi siihen mahtuu vain rajoitettu määrä tietoa. SISÄÄN Windowsin koko Pinon oletuskoko on 1 MB. Joissakin muissa Unix-järjestelmissä tämä koko voi olla 8 Mt. Jos ohjelma yrittää työntää pinoon liikaa tietoa, se johtaa pinon ylivuotoon. Pinon ylivuoto(pinon ylivuoto) tapahtuu, kun muistipyyntö tapahtuu, kun kaikki pinomuisti on jo varattu - tässä tapauksessa kaikki allokointipyynnöt alkavat virrata (ylivuodon) muihin muistiosiin.

Pinon ylivuoto on myös lisäyksen tulos suuri numero muuttujat pinossa ja/tai luomisessa Suuri määrä sisäkkäisiä funktiokutsuja (esimerkiksi missä funktio A kutsuu funktiota B, joka puolestaan ​​kutsuu funktiota C, joka kutsuu funktiota D, jne. jne.). Pinon ylivuoto aiheuttaa yleensä ohjelman kaatumisen.

Esimerkiksi:

int main() ( int pino; return 0; )

Tämä ohjelma yrittää lisätä valtavan joukon puhelupinoon. Koska pinon koko ei riitä käsittelemään tällaista taulukkoa, sen lisääminen menee muihin muistin osiin, joita ohjelma ei voi käyttää. Siksi saamme epäonnistumisen.

Tässä on toinen ohjelma, joka aiheuttaa pinon ylivuodon, mutta eri syystä:

void boo() ( boo(); ) int main() ( boo(); return 0; )

Pino

Pino on ohjelmoinnin suosituin ja ehkä tärkein tietorakenne. Pino on tallennuslaite, josta elementit poistetaan niiden lisäämisen käänteisessä järjestyksessä. Se on kuin epäsäännöllinen jono, jossa ensimmäisenä palvellaan se, joka pääsi viimeiseksi. Ohjelmointikirjallisuudessa lyhenteet hyväksytään yleisesti kuvaamaan jonon ja pinon kurinalaisuutta. Jonokuri on nimetty FIFO, mikä tarkoittaa First In First Out. Pinon laji on nimetty LIFO, last in first out (Last In First Out).

Pino voidaan ajatella putkena, jossa on jousikuormitettu pohja ja joka sijaitsee pystysuorassa. Putken yläpää on avoin, elementtejä voidaan lisätä tai, kuten sanotaan, työntää siihen. Yleisesti hyväksytty Englanninkieliset termit tässä suhteessa ne ovat erittäin värikkäitä, kun elementin lisääminen pinoon on nimeltään push, käännettynä "työnnä, työnnä". Uusi lisättävä elementti työntää pinoon aiemmin asetetut elementit yhden aseman alaspäin. Kun elementit pompataan pinosta, ne työnnetään ylöspäin, englanniksi pop ("ampua").

Esimerkki pinosta olisi heinäsuovasta, pino papereita pöydällä, pino lautasia jne. Tästä tulee nimi pino, joka tarkoittaa pinoa englanniksi. Levyt poistetaan pinosta päinvastaisessa järjestyksessä niiden lisäämisessä. Vain ylälevyyn pääsee käsiksi, ts. lautanen pinon päällä. Hyvä esimerkki toimii myös rautatien umpikujana, johon voidaan pinota vaunuja.

Pinoa käytetään melko usein ja useimmissa erilaisia ​​tilanteita. Niitä yhdistää seuraava tavoite: sinun on tallennettava työ, jota ei ole vielä suoritettu, jos sinun on vaihdettava toiseen tehtävään. Pinoa käytetään väliaikaisesti sellaisen tehtävän tilan tallentamiseen, jota ei ole vielä suoritettu. Tilan tallennuksen jälkeen tietokone vaihtaa toiseen tehtävään. Kun se on suoritettu, siirretyn tehtävän tila palautetaan pinosta ja tietokone jatkaa keskeytettyä toimintaa.

Miksi pinoa käytetään keskeytetyn työn tilan tallentamiseen? Oletetaan, että tietokone suorittaa tehtävää A. Sen suorituksen aikana syntyy tarve suorittaa tehtävä B. Tehtävän A tila muistetaan ja tietokone jatkaa tehtävän B suorittamiseen. Mutta tehdessäänkin B tietokone voi vaihtaa toiseen tehtävään C, ja se on tallennettava tehtävän B tila ennen kuin siirrytään tehtävään C. Myöhemmin, kun tehtävä C on suoritettu, palautetaan ensin tehtävän B tila ja sitten tehtävän B suorittamisen jälkeen tehtävän B tila tehtävä A. Näin ollen palautus tapahtuu tallennuksen käänteisessä järjestyksessä, mikä vastaa pinon kurinalaisuutta.

Pinon avulla voit järjestää rekursion, ts. aliohjelma kutsuu itseään joko suoraan tai muiden kutsujen ketjun kautta. Suorittakoon esimerkiksi alirutiini A algoritmi riippuen syöttöparametri X ja mahdollisesti globaalien tietojen tila. Useimmille yksinkertaiset arvot X-algoritmi toteutetaan suoraan. Enemmän tapauksessa monimutkaisia ​​merkityksiä X-algoritmi toteutetaan pelkistyksenä saman algoritmin soveltamiseen yksinkertaisemmille X:n arvoille. Tässä tapauksessa alirutiini A viittaa itseensä ja välittää yksinkertaisemman arvon X parametrina parametrin X arvo sekä kaikki alirutiinin A paikalliset muuttujat säilyvät pinossa. Seuraava luodaan uusi setti paikalliset muuttujat ja muuttuja, joka sisältää parametrin X uuden (yksinkertaisemman) arvon. Kutsuttu alirutiini A toimii uudella muuttujajoukolla tuhoamatta edellistä joukkoa. Puhelun lopussa vanha paikallismuuttujajoukko ja syöteparametrin X vanha tila palautetaan pinosta ja rutiini jatkuu siitä mihin se jäi.

Itse asiassa sinun ei tarvitse edes tallentaa aliohjelman paikallisten muuttujien arvoja pinoon erityisellä tavalla. Tosiasia on, että aliohjelman paikalliset muuttujat (eli sen sisäiset, työskentelymuuttujat, jotka luodaan sen suorittamisen alussa ja tuhotaan lopussa) sijoitetaan pinoon, joka on toteutettu tavalliseen RAM-muistiin perustuvalla laitteistolla. Työnsä alussa aliohjelma nappaa pinosta tilaa paikallisille muuttujilleen, tätä laitteistopinon muistialuetta kutsutaan yleensä paikallinen muuttujalohko tai englanniksi kehys("kehys"). Työn valmistuttua aliohjelma vapauttaa muistia poistamalla pinosta paikallisten muuttujiensa lohkon.

Paikallisten muuttujien lisäksi laitteistopinoon on tallennettu aliohjelman kutsujen paluuosoitteet. Kutsutaan aliohjelma jossain vaiheessa ohjelmaa A B. Ennen kuin alirutiini B kutsutaan, B:tä kutsuvaa käskyä seuraavan käskyn osoite tallennetaan pinoon. Tämä on ns palautusosoite ohjelmaan A. Kun se on valmis, alirutiini B ponnahtaa ohjelman A paluuosoitteen pinosta ja palauttaa ohjauksen tähän osoitteeseen. Tällöin tietokone jatkaa ohjelman A suorittamista aloittaen kutsukäskyä seuraavasta käskystä. Useimmissa prosessoreissa on erikoisjoukkueet, jotka tukevat aliohjelman kutsumista työntämällä ensin paluuosoite pinoon ja palaamalla aliohjelmasta pinosta ponnahtamaan osoitteeseen. Yleensä kutsukomentoa kutsutaan nimellä call, paluukomentoa kutsutaan paluuksi.

Myös aliohjelman tai funktion parametrit työnnetään pinoon ennen kuin sitä kutsutaan. Järjestys, jossa ne sijoitetaan pinoon, riippuu korkean tason kielten käytännöistä. Joten C- tai C++-kielessä ensimmäinen funktion argumentti on pinon yläosassa, toinen sen alapuolella ja niin edelleen. Pascalissa se on päinvastoin: funktion viimeinen argumentti on pinon yläosassa. (Siksi muuten, toimii kanssa muuttuva numero argumentit, kuten printf, mutta Pascal ei.)

Fortran-4:ssä, yhdessä vanhimmista ja menestyneimmistä ohjelmointikielistä, argumentit välitetään erityisen muistialueen läpi, joka ei välttämättä sijaitse pinossa, koska 1900-luvun 70-luvun loppuun asti siellä oli vielä tietokoneita, kuten IBM 360- tai ES-tietokoneet ilman laitteistototeutuspinoa. Paluuosoitteita ei myöskään tallennettu pinoon, vaan kullekin aliohjelmalle vahvistettuihin muistisoluihin. Ohjelmoijat kutsuvat tällaista muistia staattiseksi siinä mielessä, että staattiset muuttujat ovat aina saman paikan muistissa aina kun ohjelma on käynnissä. Vain käytettynä staattinen muisti rekursio ei ole mahdollista, koska uusi kutsu tuhoaa paikallisten muuttujien aikaisemmat arvot. Viite Fortran 4 käytti vain staattisia muuttujia, ja rekursio oli kielletty. Tähän asti Fortran-kieltä on käytetty laajalti tieteellisissä ja teknisissä laskelmissa, mutta moderni standardi Fortran 90 on jo esitelty pino muisti, poistaa puutteet aikaisemmat versiot Kieli.