Pino
Tietojenkäsittelytieteessä pino (engl. stack) on abstrakti tietotyyppi.
Periaate
[muokkaa | muokkaa wikitekstiä]Pinon toimintaperiaate on viimeksi sisään, ensimmäiseksi ulos (LIFO-periaate, Last In First Out; vrt. jono). Sitä voidaan verrata pöydällä olevaan lautaspinoon, koska sen alta tai keskivälistä ei voi poimia alkioita. Pinolle on määritelty seuraavat operaatiot:
- push: lisää alkion pinon päällimmäiseksi
- pop: poimii pinon päällimmäisen alkion (eli samanaikaisesti palauttaa ja poistaa sen)
- empty: tarkistaa, onko pino tyhjä
Lisäksi usein:
- peek tai top: palauttaa pinon päällimmäisen alkion poistamatta sitä (sama kuin peräkkäiset pop ja push)
Joskus myös:
- full: tarkistaa, onko pino täysi
Kaikki pinolle määritetyt operaatiot saadaan suoriutumaan vakioajassa eli koosta riippumatta, jos pino toteutetaan esimerkiksi linkitettynä listana.
Käyttökohteet, suorittimet ja aliohjelmat
[muokkaa | muokkaa wikitekstiä]
Suorittimen käskykantaan on usein sisäänrakennettu ajonaikainen pino, joka hallitsee aliohjelmien kutsu- ja paluuosoitteita, kutsuparametreja ja paikallisia muuttujia. Arkkitehtuureissa, kuten MIPS-arkkitehtuuri, joissa suoritin ei toteuta käskyjä pinon käsittelyyn se on toteutettava ohjelmallisesti.[1] FORTRAN 77 ei tukenut pinoa vaan funktioilla oli oma muistialueensa argumenteille ja datalle.[1]
Joissakin tapauksissa suorittimella voi olla sisäänrakennettuna pieni muistialue nimenomaan pinoa varten.[2] Tämä voi olla ohjelmallisesti käsiteltävää SRAM-muistia tai tarkoitukseen tehtyä laitteistoa, joka käyttäytyy muistin tavoin mutta pinon kokoa ei voi tällöin muuttaa.[2]
Pinon käsittely on välttämätön rekursiivisten aliohjelmien toteuttamiseen.
Sovelluksia
[muokkaa | muokkaa wikitekstiä]Jäsennys
[muokkaa | muokkaa wikitekstiä]Pinoa voidaan käyttää apuna jäsentämisessä. Tietokoneen pitää laskea esimerkiksi seuraava laskutoimitus:
((1+2)*(3+4)/3)+3 = 10
Yhtälö voidaan muuttaa 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.
| syöte | operaatio | pinon sisältö |
|---|---|---|
| [ ] | ||
| 1 | Lisää | [ 1 ] |
| 2 | Lisää | [ 1, 2 ] |
| + | Summa | [ 3 ] |
| 3 | Lisää | [ 3, 3 ] |
| 4 | Lisää | [ 3, 3, 4 ] |
| + | Summa | [ 3, 7 ] |
| * | Tulo | [ 21 ] |
| 3 | Lisää | [ 21, 3 ] |
| / | Osamäärä | [ 7 ] |
| 3 | Lisää | [ 7, 3 ] |
| + | Summa | [ 10 ] |
Ajonaikainen pino
[muokkaa | muokkaa wikitekstiä]Tietokoneisiin on lähes aina sisäänrakennettu erityinen ajonaikainen pino, joka on varattu aliohjelmakutsujen toteutukseen ja toimii nopeilla konekäskyillä. Aliohjelman kutsussa pinoon lisätään ainakin:
- välitettävät parametrit
- paluuosoite
- uudet paikalliset muuttujat
Tätä arvokokoelmaa kutsutaan aktivaatiotietueeksi. Se lisätään pinoon jokaisen kutsun yhteydessä ja poistetaan aliohjelman palatessa. Näin aliohjelmia voidaan kutsua sisäkkäin ja ne voivat myös kutsua itseään.
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 pinon ylivuotovirheen (engl. stack overflow).
Katso myös
[muokkaa | muokkaa wikitekstiä]Vastaavia abstrakteja tietotyyppejä
[muokkaa | muokkaa wikitekstiä]Toteutukseen sopivia tietorakenteita
[muokkaa | muokkaa wikitekstiä]Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ a b Understanding the Stack cs.umd.edu. Arkistoitu 26.3.2015. Viitattu 29.9.2017. (englanniksi)
- ↑ a b Stack ece353.engr.wisc.edu. Viitattu 19.9.2022. (englanniksi)
Aiheesta muualla
[muokkaa | muokkaa wikitekstiä]
Kuvia tai muita tiedostoja aiheesta Pino Wikimedia Commonsissa
