Pino vs. Kasa
Pino on järjestetty lista, jossa luettelokohteiden lisääminen ja poistaminen voidaan tehdä vain yhdessä päässä, jota kutsutaan yläpääksi. Tästä syystä pinoa pidetään Last in First out (LIFO) -tietorakenteena. Keko on erityinen tietorakenne, joka perustuu puihin ja joka täyttää erityisominaisuuden, jota kutsutaan keon ominaisuudeksi. Myös kasa on täydellinen puu, mikä tarkoittaa, että puun lehtien välissä ei ole aukkoja eli kokonaisessa puussa jokainen taso täytetään ennen uuden tason lisäämistä puuhun ja tietyn tason solmut täytetään alkaen vasemm alta oikealle.
Mikä on Stack?
Kuten aiemmin mainittiin, pino on tietorakenne, jossa elementtejä lisätään ja poistetaan vain toisesta päästä, jota kutsutaan yläpääksi. Pinot sallivat vain kaksi perustoimintoa, joita kutsutaan push ja pop. Työntötoiminto lisää pinon yläosaan uuden elementin. Pop-toiminto poistaa elementin pinon yläosasta. Jos pino on jo täynnä, sitä pidetään pinon ylivuodona, kun push-toiminto suoritetaan. Jos pop-toiminto suoritetaan jo tyhjälle pinolle, sitä pidetään pinon alivuodona. Pinolle suoritettavien toimintojen pienen määrän vuoksi sitä pidetään rajoitettuna tietorakenteena. Lisäksi sen mukaan, miten push- ja pop-operaatiot määritellään, on selvää, että elementit, jotka on lisätty pinoon viimeisenä, poistuvat pinosta ensin. Siksi pinoa pidetään LIFO-tietorakenteena.
Mikä on Heap?
Kuten aiemmin mainittiin, kasa on täydellinen puu, joka täyttää kasan ominaisuuden. Keon ominaisuus ilmoittaa, että jos y on x:n lapsisolmu, solmuun x tallennetun arvon tulisi olla suurempi tai yhtä suuri kuin solmuun y tallennettu arvo (eli arvo(x) ≥ arvo(y)). Tämä ominaisuus tarkoittaa, että solmu, jolla on suurin arvo, sijoitetaan aina juureen. Tätä ominaisuutta käyttämällä muodostettua kasaa kutsutaan max-kekoksi. On olemassa toinenkin keon ominaisuuden muunnelma, joka ilmaisee tämän päinvastaisen. (eli arvo(x) ≤ arvo(y)). Tämä tarkoittaa, että pienimmän arvon omaava solmu sijoitettaisiin aina juureen, jota kutsutaan siis min-keoksi. Kasoille tehdään monenlaisia toimintoja, kuten minimin (min-kasoissa) tai maksimin (max-kasoissa), minimin (min-kasoissa) tai maksimin (max-kasoissa) poistaminen, lisääminen (max-kasoissa) -kasot) tai laskeva (min-kekoina) -näppäin jne.
Mitä eroa on pinolla ja kasalla?
Pinojen ja pinojen pääasiallinen ero on, että kun pino on lineaarinen tietorakenne, pino on epälineaarinen tietorakenne. Pino on järjestetty luettelo, joka seuraa LIFO-ominaisuutta, kun taas kasa on täydellinen puu, joka seuraa keon ominaisuutta. Lisäksi pino on rajoitettu tietorakenne, joka tukee vain rajoitettua määrää operaatioita, kuten push ja pop, kun taas pino tukee monenlaisia toimintoja, kuten minimi- tai maksimiarvon etsimistä ja poistamista, avaimen lisäämistä tai pienentämistä ja yhdistämistä.
