Ohjelmoijana työskentelet erilaisten tietorakenteiden kanssa projektiesi laajuudesta riippuen. Yksi tällainen käsite on jonotietorakenne; jonot ovat välttämättömiä opiskelijoille ja niitä käytetään monissa tärkeissä algoritmeissa. Jonoiden tavoin prioriteettijonoilla on samanlainen käsite, mutta niillä on muutamia perustavanlaatuisia eroja.
Lue lisää ymmärtääksesi jonoja ja prioriteettijonoja.
Mikä on jono?
Jono on yksinkertainen tietorakenne, jolla on erilaisia sovelluksia tosielämän koodausprojekteissa. Tietorakenteet ovat luonnostaan abstrakteja, mutta yksinkertaisuuden vuoksi kuvittelemme, että jonotietorakenteella on lineaarinen muoto, jolla on kaksi eri päätä.
Ajan monimutkaisuuden kannalta jono sallii lisäämisen (jonotus) ja poistamisen (dequeue) O (1) -aikaan. Asymptoottisen tehokkuutensa ansiosta jonot ovat tehokkaita suurille tietojoukoille. Jonot ovat luonteeltaan FIFO (first-in-first-out), mikä tarkoittaa, että ensin lisätylle tietokohteelle päästään käsiksi. Pinoilla on sitä vastoin LIFO-luonne ja niissä on vain yksi avoin pää.
Kuvittele lippujono elokuvateatterissa; jokainen uusi asiakas saapuu jonoon yhdestä päästä. Jokainen asiakas ostaa yksitellen lipun ja poistuu jonosta etupuolelta. Jonon tietorakenne toimii täsmälleen kuten mikä tahansa reaalimaailman jono, ja data lisätään (jonoon) toisesta päästä ja poistetaan (dequeue) toisesta päästä. Nyt toivottavasti ymmärrät, miksi jonot noudattavat FIFO -menetelmää.
Jonossa on paljon tosielämän koodaussovelluksia. Sitä käytetään yleisemmin sovelluksissa, joissa tietoja ei tarvitse käsitellä välittömästi, vaan FIFO -järjestyksessä. Levyn ajoitus, asynkroninen tiedonsiirto, semaforit ovat tyypillisiä sovelluksia. Aikataulutehtävät, jotka tulevat ensin tullutta palvellaan, kuten tulostuskelaus tai syöttölaitepuskurit, käyttävät myös jonoa.
Mikä on ensisijainen jono?
Prioriteettijono on samanlainen kuin jono, mutta sillä on lisäominaisuuksia. Kun tietoelementti asetetaan prioriteettijonoon, sille annetaan prioriteettinumero. Toisin kuin normaalin jonon poistaminen käytöstä, korkean prioriteetin tietoelementit poistetaan ennen matalan prioriteetin tietoelementtejä. Prioriteetti korvaa prioriteettijonoon saapumisjärjestyksen, minkä vuoksi prioriteettijonoilla ei ole johdonmukaista FIFO -luonnetta.
Aiheeseen liittyviä: Algoritmit, jotka jokaisen ohjelmoijan tulisi tietää
Ohjelmoijat voivat toteuttaa prioriteettijonon useilla tavoilla. Yksinkertainen toteutus on käyttää taulukkoa, jossa on struktuuri-/luokka -tietoalkio, ja tietokohde sisältää kunkin tietoelementin prioriteetin ja itse datan. Toinen primitiivinen prioriteettijonon toteutus on linkitetyn luettelon käyttäminen. Linkitetyillä luetteloilla toteutetut ensisijaiset jonot ovat toimivia, mutta eivät suorituskykynsä vuoksi ihanteellisia.
Voit toteuttaa paremman prioriteettijonon kasan avulla. Jos muistat, binaarikasot antavat enimmäis- tai minimielementin 0 (1) ajan kuluessa ja lisäys kestää vain 0 (logN) ajan. Kasojen avulla prioriteettijonot antavat paremman suorituskyvyn asymptoottisesti verrattuna jonoihin tai matriiseihin.
Ensisijaisessa jonossa on myös erilaisia olennaisia sovelluksia. Prioriteettijonot ovat ratkaisevia graafisissa algoritmeissa, kuten Primin vähimmäispituuspuu ja Dijkstran lyhin polku -algoritmi. Ne ovat myös ihanteellisia tietokoneen prosessointiyksikön (CPU) prosessien ajoitusalgoritmeissa.
Opi tietorakenteita
Jonot ja prioriteettijonot ovat tärkeitä tietorakenteita kaikille aloittelijoille. On ratkaisevan tärkeää, että opiskelijat haluavat käyttää näitä tietorakenteita ja käyttää niitä eri projekteissa.
Muut tietorakenteet, kuten kasat, pinot ja puut, ovat yhtä tärkeitä opiskelijoille ja ammattilaisille. On myös hyvin yleistä, että haastattelijat kyseenalaistavat hakijoita tietorakenteista.
Kun olet lukenut tämän artikkelin, sinulla pitäisi nyt olla hyvä käsitys siitä, miten jonot ja ensisijaiset jonot toimivat. Jos kaikki näyttää edelleen hieman epäselvältä, pääset käsiksi näihin, kun saat enemmän kokemusta niiden käytöstä.
Olet kuullut Heaps and Stacksista, mutta milloin sinun pitäisi käyttää niitä toisen päälle?
Lue seuraava
- Ohjelmointi
- Ohjelmointi
- Ohjelmointityökalut
- Tekniikka
Fahad on MakeUseOfin kirjailija ja hän on tällä hetkellä pääaineena tietotekniikka. Innokkaana teknikkona hän varmistaa, että hän pysyy ajan tasalla uusimmasta tekniikasta. Hän on erityisen kiinnostunut jalkapallosta ja tekniikasta.
tilaa uutiskirjeemme
Liity uutiskirjeeseemme saadaksesi teknisiä vinkkejä, arvosteluja, ilmaisia e -kirjoja ja ainutlaatuisia tarjouksia!
Klikkaa tästä tilataksesi
