Tietorakenteet:

Miksi pinot ja jonot?

Pinoissa ja jonoissa ei ole satunnaista pääsyä (emme voi käyttää elementtiä suoraan ’indeksillä’). Meillä on yleensä vähemmän metodeja/toimintoja, joita voimme suorittaa, kuten push(), pop(), peek(), enqueue(), dequeue(), jotka kaikki käsittelevät yksinomaan tietorakenteen alussa tai lopussa olevaa elementtiä.

Mutta…

Kysymys: Tämä kuulostaa niin rajoittavalta, koska voimme käyttää vain tietorakenteen ensimmäistä tai viimeistä elementtiä. Miksi haluaisimme koskaan käyttää jotain tällaista? Miksemme käytä vain matriiseja joustavuuden lisäämiseksi?

Vastaus: Pinot ja jonot ovat yleensä ”korkeamman tason tietorakenteita”, jotka on rakennettu alemman tason tietorakenteiden (array tai linkitetty lista) päälle rajoittamaan operaatioita, joita voimme tehdä niillä. Se on etu, jos haluamme rajoitetun pääsyn.

Tämän rajoitetun kyvyn omaaminen tietorakenteelle on etu, koska voimme kontrolloida sitä, kuka käyttää tätä tietorakennetta, joka suorittaa vain oikeita operaatioita, jotka ovat tehokkaita. Meidän ei esimerkiksi tarvitse miettiä, jos joku satunnaisesti lisää elementin listamme keskelle sotkien joitakin invariantteja. Tämä pelasti meidät monilta ongelmilta. Katsotaanpa niitä tarkemmin.

Mikä on pino?

Pino on yksipäätteinen lineaarinen tietorakenne, joka mallintaa reaalimaailman pinoa siten, että siinä on kaksi ensisijaista operaatiota, nimittäin push- ja pop-operaatiot.

Alhaalla olevasta kuvasta näemme, että pinon yläreunasta nostetaan yksi tietojäsen pois ja siihen lisätään toinen. Yläosoitin osoittaa pinon yläosassa olevaan lohkoon. Tämä johtuu siitä, että pinon elementit poistetaan ja lisätään aina pinon yläosaan. Tämä käyttäytyminen tunnetaan yleisesti nimellä LIFO (Last In First Out).

Pinon operaatiot

Seuraavassa on 2 perusoperaatiota, jotka voidaan suorittaa pinolle.

• Push-funktio: Lisää elementti pinon yläosaan
• Pop-funktio: Poistaa ylimmän elementin (ja saattaa palauttaa sen)

Pinon perusoperaatioiden visualisointi

Pinolle on lisäksi seuraavat lisätoiminnot sen tilan tarkistamiseksi.

• Peek-funktio: Palauttaa pinon ylimmän elementin poistamatta tai poistamatta sitä
• isEmpty-funktio: Tarkistaa, onko pino tyhjä vai ei
• isFull-funktio: Tarkista, onko pino täynnä vai ei

Kaikki toiminnot toimivat pinon yläosasta. Meillä ei ole pääsyä mihinkään muuhun kuin ylimpään. Tämä on ratkaisevaa sen toiminnan ymmärtämisessä.

Kompleksisuusanalyysi

Seuraavassa monimutkaisuustaulukossa oletetaan, että olet toteuttanut pinon linkitetyllä listalla

Pinojen sovellukset

Missä ja milloin pinoa käytetään? käytämme pinoa paljon ohjelmoinnissa huomaamattamme, tässä muutamia esimerkkejä:

• Voidaan käyttää lausekkeiden evaluointiin (esim.: shunting-yard-algoritmi matemaattisten lausekkeiden jäsentämiseen ja evaluointiin).
• Voidaan käyttää funktiokutsujen toteuttamiseen rekursio-ohjelmoinnissa.

• Käytetään tekstieditorien peruuttamismekanismeja kirjoittamamme tekstin peruuttamiseen (Cmd + Z Mac OS:ssä ja Ctrl + Z Windowsissa)
• Käytetään selaimessa taaksepäin navigointiin ja eteenpäin
• Voidaan käyttää DFS:n (Depth First Search) tekemiseen graafissa
• Käytetään kulissien takana tukemaan rekursiota pitämällä kirjaa edellisistä funktiokutsuista

Mikä on jono?

Jono on myös lineaarinen tietorakenne, joka mallintaa reaalimaailman jonoja siten, että siinä on kaksi pääasiallista operaatiota, nimittäin enqueue (voimme ajatella sen tarkoittavan ”astu jonoon”) ja dequeue (voimme ajatella sen myös tarkoittavan ”poista jonosta”). Tämä rakenne on nimetty ”jonoksi” sen vuoksi, että se muistuttaa todellista jonoa – (jossa ihmiset odottavat jonossa).

Jokaiseen jonoon kuuluu etu- ja takapää (jota joskus kutsutaan ”takapääksi”). Lisäämme elementtejä takapään kautta ja poistamme niitä etupään kautta.

Osoitusjono on FIFO-rakenne (First In First Out – ensin sijoitettu elementti voidaan käyttää ensimmäisenä), joka esiintyy yleisesti monissa ohjelmointikielissä.

Jonojonon operaatiot

Seuraavassa on 3 perusoperaatiota, jotka voidaan suorittaa jonolle.

• Enqueue-funktio: Lisää elementti jonon loppuun
• Dequeue-funktio: Elementin poistaminen jonon alusta
• Peeking-funktio: Jonon alussa olevan arvon katsominen poistamatta sitä

Kompleksisuusanalyysi

Kuten kuvasta nähdään, jonoon asettaminen ja jonon poistaminen vievät vakioaikaa O(1). Sen sijaan sen tarkistaminen, sisältyykö jokin elementti jonoon, on lineaarisessa ajassa O(n), koska meidän pitäisi mahdollisesti skannata kaikki elementit läpi.

Sisäisesti on myös elementtien poisto (ei jonosta poisto). Se vaatii lineaarista aikaa, koska joudumme pahimmassa tapauksessa skannaamaan kaikki elementit läpi.

Jonojonojen sovellukset

• Käytetään säikeiden hallintaan monisäikeistyksessä.
• Voidaan käyttää tehokkaaseen seurantaan x viimeksi lisätystä elementistä
• Web-palvelinpyyntöjen hallintaan, jossa halutaan, että palvellaan ensin tullutta ensin. Esim: Verkkopalvelimemme voi palvella tiettynä hetkenä vain enintään 50 ihmistä samanaikaisesti.

Jos lyhyessä ajassa tulee 70 pyyntöä, emme pysty käsittelemään niitä kaikkia. Niinpä verkkopalvelin nostaa jonosta vain 50 pyyntöä ja laittaa loput 20 odottamaan. Kun web-palvelin lopettaa pyynnön käsittelyn, se poistaa seuraavan pyynnön jonosta ja tekee näin niin kauan, kunnes jono on tyhjä.

• Breadth-first search (BFS) graafin läpikäynti
• Käytetään jonotusjärjestelmien toteuttamiseen (esim.: prioriteettijonot)
• Käytetään verkkotulostimessa: Tulostin voi palvella vain yhtä pyyntöä kerrallaan. Joten jos muita pyyntöjä tulee, kun tulostin on varattu, tulostinta hallinnoiva ohjelma ei hylkää näitä pyyntöjä, vaan laittaa ne jonoon odottamaan suoritusta. Ensimmäinen pyyntö palvellaan ensin (FIFO).

Toivomme, että tämä artikkeli on antanut sinulle kuvan pinoista ja jonoista mielessäsi. Älä unohda tilata blogiamme ja seurata Designveloperin Facebookia, Twitteriä ja LinkedIniä.

Ja nämä ovat muita artikkeleita, joista saattaisit pitää:

• Mitä on web-sovellusarkkitehtuuri?
• Tietorakenteet ja niiden sovellukset
• Mitä on Big O-merkintä?