Tietorakenteet ovat kokoelma data-arvoja, niiden välisiä suhteita ja toimintoja tai toimintoja, joita voidaan käyttää tietoihin. Nyt käytettävissä on paljon tietorakenteita. Mutta tänään keskitymme pinon tietorakenteisiin. Keskustelen seuraavista aiheista:
- Miksi tietorakenteet?
- Tietorakenteiden tyypit
- Mikä on pinon tietorakenne?
- Pinotietorakenteen luominen
- Työnnä elementit pinoon
- Stackin popelementit
- Pino-tietorakenteen sovellukset
Miksi tietorakenteet?
Tähän vastaamiseksi joudut ajattelemaan suurella tasolla. Ajattele, kuinka Google Maps näyttää sinulle parhaan reitin muutamassa sekunnissa, kuinka se palauttaa hakutuloksesi mikrosekunnissa. Se ei käsittele vain 100 verkkosivustoa, se käsittelee yli miljardia sivustoa ja näyttää silti tuloksia niin nopeasti.
No, vaikka käytetyllä algoritmilla on ratkaiseva rooli, käytettävä tietorakenne tai säilö on kyseisen algoritmin perusta. Kaikissa sovelluksissa tietojen järjestäminen ja tallentaminen tavalla, joka soveltuu parhaiten sen käyttöön, on avain tietojen tehokkaaseen saatavuuteen ja käsittelyyn.
Tietorakenteiden tyypit
On joitain vakiomaisia tietorakenteita, joita voidaan käyttää tietojen tehokkaaseen käsittelyyn. Voimme jopa muokata niitä tai rakentaa täysin uusia sovelluksemme mukaan.
Mikä on pinon tietorakenne?
Harkitse joitain tosielämän esimerkkejä:
- Lähetys rahtina
- Levyt tarjottimelle
- Pino kolikoita
- Pino laatikoita
- Junien vaihtaminen rautatiepihalla
Kaikki nämä esimerkit seuraavat a Viimeisenä sisään ensimmäisenä ulos strategia. Harkitse tarjottimella olevia levyjä. Kun haluat valita levyn, sinun on pakko valita levy ylhäältä, kun levyjä pidettiin alustalla, niiden on oltava päinvastaisessa järjestyksessä. Yllä olevien esimerkkien yläpuolella Viimeinen ensimmäisessä lähtö (LIFO) periaatteessa tunnetaan nimellä Pino .
Täydentävien toimintojen lisäksi voin sanoa, että päätoiminnot pinossa ovat:
yhdistä lajittelukoodi c ++
- Työnnä tai työnnä elementti pinon yläosaan
- Pistä tai poista elementti pinon yläosasta
Pinotietorakenteen luominen
luokan pino: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size on pinossa odotettavissa olevien elementtien enimmäismäärä.
- Pinoelementit tallennetaan python-luetteloon.
- Ylä osoittaa pinon ylimmän indeksin, joka otetaan aluksi -1 merkitsemään tyhjää pinoa.
Pinon alkutila näkyy kuvassa, jossa max_size = 5
Työnnä elementti pinoon
Nyt, jos haluat syöttää tai siirtää elementin pinoon, sinun on muistettava se
- Yläosa osoittaa hakemiston, johon elementti lisätään.
- Ja että mitään elementtiä ei lisätä, kun pino on täynnä, ts. Kun max_size = top.
Joten mikä pitäisi olla algoritmi?
# palauttaa pinon maksimikoon def get_max_size (itse): return self .__ max_size # palauttaa Bool-arvon riippumatta siitä, onko pino täynnä vai ei, True jos täysi ja False muuten def on_full (itse): return self.get_max_size () - 1 == self .__ top #pushes -elementti pinon yläosassa def push (itse, data): if (self.is_full ()): print ('pino on jo täynnä') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data #Voit käyttää alla olevaa __str __ () tulostaa DS-objektin elementit virheenkorjauksen yhteydessä def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (itse .__ elementit [hakemisto])) index- = 1 msg = '' .join (msg) msg = 'Pino tiedot (ylhäältä alas):' + msg palauta viestiNyt kun suoritat seuraavat:
pino1 = pino (4)
#Push kaikki vaaditut elementit.
pino1.push (“A”)
pino1.push (“B”)
pino1.push (“C”)
theano vs tensorflow vs keras
pino1.push (“E”)
tulosta (pino1.is_full ())
tulosta (pino1)
Tuotos:
pino on jo täynnä
Totta
Pinon tiedot (ylhäältä alas): D C B A
Stackin popelementit
Kun olet lisännyt elementit pinoon, haluat lisätä ne, joten sinun on huolehdittava seuraavista:
- Pino ei ole tyhjä eli alkuun! = -1
- Kun poistat tiedot, yläosan on osoitettava pinon edellistä yläosaa.
Joten mikä on algoritmi?
# palauttaa Bool-arvon riippumatta siitä, onko pino tyhjä vai ei, Tosi, jos tyhjä ja Epätosi muutoin def on_tyhjä (itse): return self .__ top == - 1 #palauttaa popped-arvon def pop (itse): if (itse.is_empty ()): tulosta ('ei mitään avattavaa, jo tyhjä') muuten: a = itse .__ elementit [itse .__ ylh.] itse .__ ylh. = itse .__ top-1 palauttaa #näytä kaikki pinon elementit ylhäältä alas def-näyttö (itse): alueelle i (itse .__ ylh., -1, -1): tulosta (itse .__ elementit [i], loppu = '') tulosta ()Ottaen huomioon aiemmin luotu pino, yritä pop-elementtejä
tulosta (pino1.pop ())
tulosta (pino1.pop ())
tulosta (pino1)
tulosta (pino1.pop ())
tulosta (pino1.pop ())
tulosta (pino1.pop ())
Tuotos:
D
C
Pinon tiedot (ylhäältä alas): B A
B
TO
ei mitään popia, jo tyhjä
Pino-tietorakenteen sovellukset
- Esimerkki 1:
Pinoa käytetään sulkujen sovitusalgoritmin toteuttamiseen aritmeettisen lausekkeen arviointiin ja myös menetelmäkutsujen toteuttamiseen.
muuntaa binaari int jaavaksi
Vastaus on 5.
- Esimerkki 2:
Leikepöytä Windowsissa käyttää kahta pinoa kumoustoimintojen (ctrl + z, ctrl + y) toteuttamiseen. Olisit työskennellyt Windows-sananmuokkausohjelmilla, kuten MS-Word, Muistio jne. Tässä on teksti kirjoitettu MS-Wordiin. Tarkkaile, kuinka teksti muuttui Ctrl-Z: n ja Ctrl-Y: n napsautuksella.
Tässä on koodi, joka simuloi kumoa-uudelleen-toimintaa. Käy läpi koodi ja tarkkaile, kuinka pinoa käytetään tässä toteutuksessa.
#creating luokan pino luokan pino: def __init __ (itse, max_size): itse .__ max_size = max_size self .__ elementit = [Ei mitään] * itse .__ max_size self .__ alkuun = -1 def is_full (itse): if (itse .__ alkuun == itse .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): tulosta ('Pino on täynnä !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Pino on tyhjä! ! ') else: data = self .__ elementit [self .__ top] self .__ top- = 1 return data def -näyttö (itse): if (self.is_empty ()): print (' Pino on tyhjä ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #Voit käyttää alla olevaa __str __ () tulostaaksesi DS-objekti virheenkorjauksen aikana def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Pino tiedot (ylhäältä alas): '+ msg palauttaa ms g # toiminto poisto- tai askelpalautustoiminnon toteuttamiseksi def poista (): yleinen leikepöytä, undo_stack data = leikepöytä [len (leikepöytä) -1] leikepöytä. poista (data) undo_stack.push (data) -tulostus ('Poista:', leikepöytä) # function toteuttaa kumoustoiminta def undo (): globaali leikepöytä, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Kumottavia tietoja ei ole') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Kumoa:', leikepöytä) # toiminto toisto-operaation toteuttamiseksi def redo (): globaali leikepöytä, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Tietoja ei ole tehdä uudelleen ') else: data = redo_stack.pop () if (tietoja ei ole leikepöydällä): print (' Ei ole tietoja, jotka pitäisi tehdä uudelleen ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( data) print ('Tee uudelleen:', leikepöytä) leikepöytä = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Pino (len (leikepöytä)) redo_stack = Pino (len (leikepöytä)) poista () kumoa () tee uudelleen ()Tuotos:
Poista: [”A”, “B”, “C”, “D”, “E”]
Kumoa: [”A”, “B”, “C”, “D”, “E”, “F”]
Tee uudelleen: [”A”, “B”, “C”, “D”, “E”]
Tämän avulla olemme päässeet tämän pinon tietorakenteen python-artikkeliin. Jos ymmärrät koodit ja suoritit ne itse, et ole enää aloittelija Stacks-tietorakenteessa.
Onko sinulla kysymys meille? Mainitse se tämän artikkelin kommenttiosassa ja otamme sinuun yhteyttä mahdollisimman pian.
Saadaksesi syvällistä tietoa Pythonista sen eri sovellusten kanssa, voit ilmoittautua livenä 24/7 -tuella ja käyttöikällä.