Ero sivun ”Pino” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Ei muokkausyhteenvetoa |
|||
Rivi 2:
*''push'': lisää alkion pinon päällimmäiseksi
*''pop'': poimii pinon päällimmäisen alkion (eli samanaikaisesti palauttaa ja poistaa sen)
*''empty'': tarkistaa, onko pino
Lisäksi usein:
*''peek'' tai ''top'': palauttaa pinon päällimmäisen alkion poistamatta sitä (sama kuin peräkkäiset ''pop'' ja ''push'') <!-- ei täysin välttämätön pino-operaatio, usein määriteltynä vain =pop+push -->
Rivi 8:
*''full'': tarkistaa, onko pino täysi
Kaikki pinolle määritetyt operaatiot saadaan suoriutumaan [[asymptoottinen suoritusaika|vakioajassa]] eli koosta riippumatta, jos
[[Suoritin|Suorittimen]] käskykantaan on lähes aina sisäänrakennettu tehokas '''ajonaikainen pino''', joka hallitsee aliohjelmien kutsu- ja paluuosoitteita, kutsuparametreja ja paikallisia muuttujia. Se on välttämätön rekursiivisten aliohjelmien toteuttamiseen.
Rivi 17:
((1+2)*(3+4)/3)+3 = 10
Yhtälö voidaan muuttaa [[Käänteinen puolalainen notaatio|postfix-muotoon]] eli muotoon, jossa ei tarvita sulkuja. Muunnos voidaan tehdä [[Shunting yard]] -algoritmilla, joka sekin käyttää pinoa.
1 2 + 3 4 + * 3 / 3 +
Tämän jälkeen laskutoimitus on helppo toteuttaa pinon avulla: Edetään askel askeleelta vasemmalta oikealle lisäten lukuja pinoon. Kun törmätään operaattoriin, pinosta poimitaan tarvittava määrä lukuja ja tehdään operaattorin määrittämä laskutoimitus niiden välillä. Laskutoimituksen tulos tallennetaan takaisin pinoon. Syötteen loputtua vastaus on luettavissa pinosta.
Rivi 62 ⟶ 60:
* uudet paikalliset muuttujat
Tätä arvokokoelmaa kutsutaan [[aktivaatiotietue]]eksi. Se lisätään pinoon jokaisen kutsun yhteydessä
Ajonaikainen pino on yleisesti toteutettu kiinteänä muistialueena ja pinon päähän osoittavana ''pino-osoitinrekisterinä''. Päättymätön rekursio aiheuttaakin pinon täyttymisen ja ajonaikaisen virheen.
| |||