Tietojenkäsittelytieteessäpino (engl.stack) onabstrakti tietotyyppi.
Pinon toimintaperiaate onviimeksi 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:
Lisäksi usein:
Joskus myös:
Kaikki pinolle määritetyt operaatiot saadaan suoriutumaanvakioajassa eli koosta riippumatta, jos pino toteutetaan esimerkiksilinkitettynä listana.
Suorittimen käskykantaan on usein sisäänrakennettuajonaikainen pino, joka hallitseealiohjelmien kutsu- ja paluuosoitteita, kutsuparametreja ja paikallisia muuttujia. Arkkitehtuureissa, kutenMIPS-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önrekursiivisten aliohjelmien toteuttamiseen.
Pinoa voidaan käyttää apunajäsentämisessä. Tietokoneen pitää laskea esimerkiksi seuraava laskutoimitus:
((1+2)*(3+4)/3)+3 = 10
Yhtälö voidaan muuttaapostfix-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 ] |
Tietokoneisiin on lähes aina sisäänrakennettu erityinenajonaikainen pino, joka on varattu aliohjelmakutsujen toteutukseen ja toimii nopeilla konekäskyillä. Aliohjelman kutsussa pinoon lisätään ainakin:
Tätä arvokokoelmaa kutsutaanaktivaatiotietueeksi. 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 osoittavanapino-osoitinrekisterinä. Päättymätön rekursio aiheuttaakin pinon täyttymisen ja ajonaikaisenpinon ylivuotovirheen (engl.stack overflow).
Kuvia tai muita tiedostoja aiheestaPinoWikimedia Commonsissa