Podatkovne strukture so zbirka podatkovnih vrednosti, odnosov med njimi in funkcij ali operacij, ki jih je mogoče uporabiti za podatke. Zdaj je na voljo veliko podatkovnih struktur. Toda danes se bomo osredotočili na strukture podatkovnih skladov. Razpravljal bom o naslednjih temah:
- Zakaj podatkovne strukture?
- Vrste podatkovnih struktur
- Kaj je struktura podatkov skladov?
- Ustvarjanje strukture podatkovnega sklada
- Potisnite elemente v sklad
- Pop elementi iz sklada
- Uporaba strukture podatkov skladov
Zakaj podatkovne strukture?
Če želite odgovoriti na to, boste morali razmišljati na večji ravni. Pomislite, kako vam Google Zemljevidi v najboljših delih sekund prikažejo najboljšo pot, kako v mikrosekundah vrne rezultate iskanja. Ne ukvarja se s samo 100 spletnimi mesti, ukvarja se z več kot milijardo spletnih mest in še vedno tako hitro prikazuje rezultate.
No, čeprav ima uporabljeni algoritem ključno vlogo, je osnova tega algoritma podatkovna struktura ali uporabljeni vsebnik. V vsaki aplikaciji je organiziranje in shranjevanje podatkov na način ali v strukturi, ki je najprimernejša za njihovo uporabo, ključnega pomena za učinkovit dostop in obdelavo podatkov.
Vrste podatkovnih struktur
Obstaja nekaj standardnih podatkovnih struktur, ki jih lahko uporabimo za učinkovito delo s podatki. Lahko jih celo prilagodimo ali izdelamo popolnoma nove, ki ustrezajo naši aplikaciji.
Kaj je struktura podatkov skladov?
Poglejmo nekaj primerov iz resničnega življenja:
- Pošiljka v tovoru
- Plošče na pladnju
- Sklop kovancev
- Sklop predalov
- Manevriranje vlakov na železniškem dvorišču
Vsi ti primeri sledijo a Last-in-first-out strategijo. Razmislite o krožnikih na pladnju. Ko želite izbrati krožnik, ste prisiljeni, da krožnik poberete z vrha, medtem ko morajo biti krožniki na pladnju v obratnem vrstnem redu. Zgornji primeri, ki sledijo Last-in-first-out (LIFO) načelo so znani kot Stack .
Poleg dopolnilnih operacij lahko rečem, da so glavne operacije, ki so možne na kupu:
- Potisnite ali vstavite element na vrh sklada
- Pop ali odstranite element z vrha sklada
Ustvarjanje strukture podatkovnega sklada
razred Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size je največje število pričakovanih elementov v kupčku.
- Elementi sklada so shranjeni na seznamu python.
- Vrh označuje najvišji indeks sklada, ki je bil prvotno vzet -1 za označevanje praznega sklada.
Začetno stanje sklada je razvidno iz slike, kjer je max_size = 5
Potisnite element v sklad
Če želite element vnesti ali potisniti v sklad, si ga morate zapomniti
- Zgoraj bo usmerjen indeks, kamor bo element vstavljen.
- In da noben element ne bo vstavljen, ko je sklad poln, torej ko je max_size = top.
Torej, kakšen naj bo algoritem ??
# vrne največjo velikost sklada def get_max_size (self): return self .__ max_size # vrne vrednost bool, ne glede na to, ali je sklad poln ali ne, True, če je poln in False, sicer def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes element na vrhu sklada def push (self, data): if (self.is_full ()): print ('stack je že poln') else: self .__ top = self .__ top + int (1 ) self .__ elementi [self .__ top] = podatki # Spodnji __str __ () lahko uporabite za tiskanje elementov predmeta DS med odpravljanjem napak def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg = 'Stack data (Top to Bottom):' + msg return msgZdaj, ko izvedete naslednje:
stack1 = sklad (4)
# Potisnite vse zahtevane elemente.
java na moč
stack1.push ('A')
stack1.push (“B”)
stack1.push (“C”)
stack1.push (“E”)
tiskanje (stack1.is_full ())
tisk (kup 1)
Izhod:
sklad je že poln
Prav
Podatki sklada (od zgoraj navzdol): D C B A
Pop elementi iz sklada
Zdaj, ko ste elemente vstavili v sklad, jih želite prikazati, zato morate poskrbeti za naslednje:
- Sklad ni prazen, tj. Top! = -1
- Ko izbrišete podatke, mora vrh kazati na prejšnji vrh sklada.
Torej, kakšen bo algoritem ??
#returns vrednost bool, ali je sklad prazen ali ne, True, če je prazen in False, sicer def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('nič za pop, že prazno') else: a = self .__ elementi [self .__ top] self .__ top = self .__ top-1 vrne a #display all the stack elements from top to bottom def display (self): za i v obsegu (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()Zdaj, če upoštevamo predhodno ustvarjeni sklad, poskusite pojaviti elemente
tiskanje (stack1.pop ())
tiskanje (stack1.pop ())
tisk (kup 1)
tiskanje (stack1.pop ())
tiskanje (stack1.pop ())
tiskanje (stack1.pop ())
Izhod:
D
C
Podatki sklada (od zgoraj navzdol): B A
B
TO
nič za pop, že prazno
Uporaba strukture podatkov skladov
- Primer 1:
Sklop se uporablja za izvajanje algoritma ujemanja oklepajev za vrednotenje aritmetičnega izraza in tudi pri izvajanju klicev metode.
Odgovor na to je 5.
- 2. primer:
Odložišče v sistemu Windows uporablja dva sklada za izvajanje operacij razveljavitve ponovitve (ctrl + z, ctrl + y). Delali bi z urejevalniki besed Windows, kot so MS-Word, Notepad itd. Tu je besedilo, napisano v MS-Word. Oglejte si, kako se je besedilo spremenilo s klikom na Ctrl-Z in Ctrl-Y.
Tu je koda, ki simulira operacijo razveljavitve ponovitve. Preglejte kodo in opazujte, kako se sklad uporablja pri tej izvedbi.
#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ 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 ()): print ('Sklad je poln !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Sklop je prazen! ! ') else: data = self .__ elementi [self .__ top] self .__ top- = 1 vrne podatke def display (self): if (self.is_empty ()): print (' Stack is empty ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Spodnji __str __ () lahko uporabite za tiskanje elementov DS objekt med razhroščevanjem def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Stack data (Top to Bottom): '+ msg return ms g #funkcija za izvajanje odstranitve ali povratne operacije def remove (): globalno odložišče, undo_stack data = odložišče [len (odložišče) -1] clipboard.remove (data) undo_stack.push (data) print ('Odstrani:', odložišče) #funkcija za izvajanje operacije razveljavitve def undo (): globalno odložišče, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Ni podatkov za razveljavitev') else: data = undo_stack.pop () clipboard.append ( podatki) redo_stack.push (data) print ('Razveljavi:', odložišče) #funkcija za izvajanje operacije ponovitve def redo (): globalno odložišče, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Ni podatkov za ponovitev ') else: data = redo_stack.pop () if (podatki niso v odložišču): print (' Ni podatkov za ponovitev ') redo_stack.push (podatki) else: clipboard.remove (data) undo_stack.push ( data) print ('Redo:', odložišče) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (odložišče)) redo_stack = Stack (len (odložišče)) remove () undo () redo ()Izhod:
Odstrani: [„A“, „B“, „C“, „D“, „E“]
Razveljavi: [„A“, „B“, „C“, „D“, „E“, „F“]
Uveljavi: [„A“, „B“, „C“, „D“, „E“]
S tem smo prišli do konca tega članka o strukturi podatkov skladov v Pythonu. Če ste kode uspešno razumeli in zagnali sami, niste več novinec v podatkovni strukturi skladov.
Imate vprašanje za nas? Prosimo, omenite ga v oddelku za komentarje tega članka in odgovorili vam bomo v najkrajšem možnem času.
Če želite pridobiti poglobljeno znanje o Pythonu skupaj z različnimi aplikacijami, se lahko prijavite v živo s 24-urno podporo in življenjskim dostopom.