Esittely

Tietorakenteet järjestävät tallennustilaa tietokoneissa niin, että voimme käyttää ja muuttaa tietoja tehokkaasti. Pinot ja jonot ovat eräitä varhaisimpia tietotekniikassa määriteltyjä tietorakenteita.

Helppoja oppia ja helppoja toteuttaa, ja niiden käyttö on yleistä, ja todennäköisesti huomaat sisällyttäväsi niitä ohjelmistoihisi erilaisiin tehtäviin.

Pinot ja jonot on tavallista toteuttaa Array:llä tai Linked Listillä. Luotamme List-tietorakenteeseen, jolla voidaan toteuttaa sekä pinot että jonot.

Miten ne toimivat?

Pino

Pinot noudattavat nimensä mukaisesti LIFO-periaatetta (Last-in-First-Out). Aivan kuin pinoaisimme kolikoita päällekkäin, viimeinen kolikko, jonka laitamme päällimmäiseksi, on se, joka myöhemmin poistetaan pinosta ensimmäisenä.

Pinon toteuttamiseksi tarvitsemme siis kaksi yksinkertaista operaatiota:

• push – lisää elementin pinon yläosaan:

• pop – poistaa pinon huipulla olevan elementin:

Queue

Queueet noudattavat nimensä mukaisesti FIFO-periaatetta (First-in-First-Out). Aivan kuin elokuvalippuja jonottaessa, ensimmäisenä jonossa seisova ostaa ensimmäisenä lipun ja pääsee nauttimaan elokuvasta.

Toteuttaaksemme jonon tarvitsemme siis kaksi yksinkertaista operaatiota:

• enqueue – lisää elementin jonon loppuun:

• dequeue – poistaa jonon alussa olevan elementin:

Pinot ja jonot listojen avulla

Pythonin sisäänrakennetun List tietorakenteen mukana tulee metodeja, joilla voidaan simuloida sekä pino- että jonotoimintoja.

Katsotaanpa kirjepinoa:

Voidaan käyttää samoja funktioita jonon toteuttamiseen. Funktio pop ottaa argumenttina valinnaisesti sen elementin indeksin, jonka haluamme hakea.

Siten voimme käyttää pop:aa listan ensimmäisen indeksin eli 0 kanssa saadaksemme jonon kaltaisen käyttäytymisen.

Tarkastellaan hedelmien ”jonoa”:

Tässä taas käytämme listan append– ja pop-operaatioita simuloidaksemme jonon keskeisiä operaatioita.

Pinot ja jonot Deque-kirjastolla

Pythonissa on deque-kirjasto deque (lausutaan ’deck’ eli ’kansi’), joka tarjoaa sekvenssin, jossa on tehokkaita metodeja, joiden avulla voidaan työskennellä pinoina tai jonoina.

deque on lyhenne sanoista Double Ended Queue (kaksoispäätteinen jono) – yleistetty jono, joka voi saada ensimmäisen tai viimeisen tallennetun elementin:

Jos haluat oppia lisää deque-kirjastosta ja muista Pythonin tarjoamista kokoelmatyypeistä, voit lukea artikkelimme Johdatus Pythonin kokoelmamoduuliin.

Stricter-toteutukset Pythonissa

Jos koodisi tarvitsee pinon ja tarjoat List:n, mikään ei estä ohjelmoijaa kutsumasta insert, remove tai muita listafunktioita, jotka vaikuttavat pinon järjestykseen! Tämä pilaa pohjimmiltaan pinon määrittelyn tarkoituksen, koska se ei enää toimi niin kuin sen pitäisi.

On tilanteita, joissa haluamme varmistaa, että vain kelvollisia operaatioita voidaan suorittaa tiedoillamme.

Voimme luoda luokkia, jotka paljastavat vain tarvittavat metodit kullekin tietorakenteelle.

Tehdäksemme näin luodaan uusi tiedosto nimeltä stack_queue.py ja määritellään kaksi luokkaa:

Ohjelmoijia, jotka käyttävät Stack– ja Queue-luokkaamme, kannustetaan nyt käyttämään sen sijaan tarjottuja metodeja datan manipuloimiseksi.

Esimerkkejä

Kuvittele, että olet kehittäjä, joka työskentelee upouuden tekstinkäsittelyohjelman parissa. Tehtävänäsi on luoda peruutusominaisuus, jonka avulla käyttäjät voivat perua tekemänsä toimenpiteet istunnon alkuun asti.

Pino sopii tähän skenaarioon erinomaisesti. Voimme tallentaa jokaisen käyttäjän tekemän toimenpiteen työntämällä sen pinoon. Kun käyttäjä haluaa peruuttaa toimenpiteen, hän nostaa sen pinosta. Voimme nopeasti simuloida ominaisuutta näin:

Pinoilla on laajalti käyttöä myös ohjelmoinnissa. Ajattele pelejä kuten Street Fighter tai Super Smash Brothers. Näissä peleissä pelaajat voivat suorittaa erikoisliikkeitä painamalla painikeyhdistelmää. Nämä painikeyhdistelmät voidaan tallentaa jonoon.

Kuvittele nyt, että olet kehittäjä, joka työstää uutta tappelupeliä. Pelissäsi joka kerta, kun painiketta painetaan, laukaistaan syöttötapahtuma. Eräs testaaja huomasi, että jos nappeja painetaan liian nopeasti, peli käsittelee vain ensimmäisen ja erikoisliikkeet eivät toimi!

Voit korjata tämän jonon avulla. Voimme asettaa kaikki syötetapahtumat jonoon sitä mukaa kun niitä tulee. Tällä tavalla ei ole väliä, jos syöttötapahtumia tulee vähän aikaa niiden välillä, ne kaikki tallennetaan ja ovat käytettävissä käsittelyä varten. Kun olemme käsitelleet siirtoja, voimme poistaa ne jonosta. Erikoissiirto voidaan työstää näin:

Johtopäätös

Pinot ja jonot ovat yksinkertaisia tietorakenteita, joiden avulla voimme tallentaa ja hakea tietoja peräkkäin. Pinossa viimeksi syötetty kohde tulee ensimmäisenä ulos. Jonossa ensimmäinen syöttämämme kohde tulee ensimmäisenä ulos.

Voidaan lisätä kohteita pinoon operaatiolla push ja hakea kohteita operaatiolla pop. Jonoissa lisäämme kohteita operaatiolla enqueue ja haemme kohteita operaatiolla dequeue.

Pythonissa voimme toteuttaa pinot ja jonot vain käyttämällä sisäänrakennettua List-tietorakennetta. Pythonissa on myös deque-kirjasto, joka voi tarjota tehokkaasti pino- ja jono-operaatiot yhdessä objektissa. Lopuksi olemme tehneet pino- ja jonoluokkia tiukempaa datan hallintaa varten.

Pinoille ja jonoille on monia reaalimaailman käyttötapauksia, ja niiden ymmärtämisen avulla voimme ratkaista monia tiedon tallennusongelmia helposti ja tehokkaasti.