Python

Johdanto

Tietorakenteet järjestävät tallennuksen tietokoneissa niin, että voimme tehokkaasti käyttää ja muuttaa dataa. Pinot ja jonot ovat varhaisimpia tietojenkäsittelytieteessä määriteltyjä tietorakenteita.

helppo oppia ja helppo toteuttaa, niiden käyttötavat ovat yleisiä ja huomaat todennäköisesti sisällyttäväsi ne ohjelmistoosi erilaisiin tehtäviin.

on tavallista, että pinot ja jonot toteutetaan Array-tai linkitetyllä listalla. Luotamme List tietorakenteeseen, johon mahtuu sekä pinoja että jonoja.

miten ne vaikuttavat?

Pino

Pinot noudattavat nimensä mukaisesti Last-in-First-Out (LIFO) – periaatetta. Ikään pinoaminen kolikoita yksi päällekkäin, viimeinen kolikon laitamme päälle on yksi, joka on ensimmäinen poistetaan pinosta myöhemmin.

pinon toteuttamiseksi tarvitaan siis kaksi yksinkertaista operaatiota:

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

pop – poistaa alkuaineen pinon yläreunasta:

jono

p> jonot noudattavat nimensä mukaisesti first-in-first-out (FIFO) – periaatetta. Aivan kuin jonossa odottaisi elokuvalippuja, jonottaja on ensimmäinen, joka ostaa lipun ja nauttii elokuvasta.

jonon toteuttamiseksi tarvitaan siis kaksi yksinkertaista operaatiota:

• enqueue – lisää alkuaineen jonon loppuun:

dequeue – poistaa alkuaineen jonon alussa:

pinot ja jonot käyttäen luetteloita

Pythonin sisäänrakennettu Listtietorakenne tulee nipussa sekä pino-että jono-operaatioiden simulointimenetelmien kanssa.

tarkastellaan kirjainpinoa:

Voimme käyttää samoja funktioita jonon toteuttamiseen. pop funktio ottaa valinnaisesti parametriksi haettavan kohteen indeksin.

voidaan siis käyttää pop listan ensimmäisen indeksin eli 0 jonomaista käyttäytymistä.

tarkastellaan hedelmien ”jonoa”:

taas, tässä käytetään append ja pop luettelon operaatioita simuloimaan jonon ydinoperaatioita.

Stacks and Queues with the Deque Library

Pythonilla on deque (lausutaan ’deck’) – kirjasto, joka tarjoaa sekvenssin tehokkailla menetelmillä toimimaan pinona tai jonona.

deque on lyhenne Kaksipäätteisestä jonosta – yleistetystä jonosta, joka voi saada tallennetun ensimmäisen tai viimeisen elementin:

Jos haluat lisätietoja deque kirjastosta ja muista Pythonin tarjoamista kokoelmista, voit lukea johdannon Pythonin Kokoelmamoduulin artikkelista.

tiukemmat toteutukset Pythonissa

Jos koodisi tarvitsi pinon ja annat List, mikään ei estä ohjelmoijaa kutsumasta insertremove tai muita pinosi järjestykseen vaikuttavia luettelofunktioita! Tämä pilaa olennaisesti pinon määrittelykohdan, koska se ei enää toimi niin kuin sen pitäisi.

on aikoja, jolloin haluamme varmistaa, että tiedoillamme voidaan suorittaa vain kelvollisia operaatioita.

voimme luoda luokkia, jotka paljastavat vain kullekin tietorakenteelle tarvittavat menetelmät.

luodaanpa uusi tiedosto stack_queue.py ja määritellään kaksi luokkaa:

ohjelmoijia, jotka käyttävät meidän Stack ja Queue, kannustetaan nyt käyttämään annettuja menetelmiä datan manipulointiin.

esimerkkejä

kuvittele olevasi kehittäjä, joka työskentelee upouuden tekstinkäsittelyohjelman parissa. Sinun tehtävänäsi on luoda kumoa – ominaisuus, jonka avulla käyttäjät voivat seurata toimintaansa istunnon alkuun asti.

pino sopii ihanteellisesti tähän skenaarioon. Voimme tallentaa kaikki käyttäjän toimet työntämällä ne pinoon. Kun käyttäjä haluaa kumota toiminnon, hän avaa sen pinosta. Ominaisuutta voidaan simuloida nopeasti näin:

jonoilla on laajaa käyttöä myös ohjelmoinnissa. Ajattele pelejä, kuten Street Fighter tai Super Smash Brothers. Pelaajat näissä peleissä voi suorittaa erityisiä liikkeitä painamalla yhdistelmä painikkeita. Nämä näppäinyhdistelmät voidaan tallentaa jonoon.

kuvittele nyt, että olet kehittäjä, joka työstää uutta taistelupeliä. Pelissä joka kerta, kun nappia painetaan, syöttötapahtuma ammutaan. Testaaja huomasi, että jos nappeja painetaan liian nopeasti, peli käsittelee vain ensimmäisen ja erikoisliikkeet eivät toimi!

sen voi korjata jonolla. Voimme tiedustella kaikki tapahtumat, kun ne tulevat. Näin sillä ei ole väliä, jos syöttötapahtumat tulevat vähän aikaa niiden välillä, ne kaikki tallennetaan ja voidaan käsitellä. Kun käsittelemme liikkeitä, voimme poistaa ne. Erityinen siirto voidaan toteuttaa näin:

johtopäätös

pinot ja jonot ovat yksinkertaisia tietorakenteita, joiden avulla voimme tallentaa ja hakea tietoja peräkkäin. Pinossa viimeinen syötettävä esine tulee ensimmäisenä ulos. Jonossa ensimmäinen sisään menevä kohde on ensimmäinen ulos tulija.

voimme lisätä kohteita pinoon käyttämällä push operaatiota ja hakea kohteita pop operaatiota. Jonoihin lisätään kohteita enqueue – operaatiolla ja noudetaan kohteita dequeue – operaatiolla.

Pythonissa voidaan toteuttaa pinot ja jonot pelkästään sisäänrakennetun List tietorakenne. Pythonilla on myös deque – kirjasto, joka voi tehokkaasti tarjota pino-ja jono-operaatioita yhdessä objektissa. Lopuksi, olemme tehneet meidän pino ja jono luokat tiukempi valvonta tietojamme.

pinoille ja jonoille on monia reaalimaailman käyttötapauksia, joiden ymmärtäminen mahdollistaa monien tietojen tallennusongelmien ratkaisemisen helposti ja tehokkaasti.