Strukture podataka su zbirka vrijednosti podataka, odnosi među njima i funkcije ili operacije koje se mogu primijeniti na podatke. Sada je dostupno puno struktura podataka. Ali danas ćemo se fokusirati na strukture podataka steka. Razgovarat ću o sljedećim temama:
- Zašto strukture podataka?
- Vrste struktura podataka
- Što je struktura podataka steka?
- Stvaranje strukture podataka steka
- Gurnite elemente u hrpu
- Pop elementi iz stoga
- Primjene strukture podataka steka
Zašto strukture podataka?
Da biste odgovorili na ovo, morat ćete razmišljati na velikoj razini. Razmislite kako vam Google mape pokazuju najbolju rutu u samo djeliću sekundi, kako vam vraća rezultat pretraživanja u mikrosekundama. Ne bavi se samo sa 100 web lokacija, bavi se s više od milijardu web stranica i još uvijek vam tako brzo pokazuje rezultat.
Pa, iako korišteni algoritam igra presudnu ulogu, struktura podataka ili upotrijebljeni spremnik temelj su tog algoritma. U bilo kojoj aplikaciji, organiziranje i pohranjivanje podataka na način ili u strukturi koja je najprikladnija za njegovu upotrebu ključno je za učinkovit pristup i obradu podataka.
Vrste struktura podataka
Postoje neke standardne strukture podataka koje se mogu koristiti za učinkovit rad s podacima. Možemo ih čak prilagoditi ili izraditi potpuno nove kako bi odgovarali našoj aplikaciji.
Što je struktura podataka steka?
Razmotrite neke primjere iz stvarnog života:
- Pošiljka u teretu
- Ploče na pladnju
- Stog novčića
- Stog ladica
- Manevriranje vlakovima u željezničkom dvorištu
Svi ovi primjeri slijede a Posljednji-prvi-izašao strategija. Razmislite o tanjurima na pladnju. Kad želite odabrati tanjur, prisiljeni ste odabrati tanjur s vrha, dok kada su ploče držane na pladnju, moraju biti obrnutim redoslijedom. Iznad primjera koji slijede Posljednje-prvo-izašlo (LIFO) Načela su poznata kao Stog .
Osim komplementarnih operacija, mogu reći da su glavne operacije koje su moguće na hrpi:
- Gurnite ili umetnite element na vrh snopa
- Otvorite ili uklonite element s vrha hrpe
Stvaranje strukture podataka steka
klasa Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size je maksimalan broj elemenata koji se očekuju u stogu.
- Elementi stoga pohranjeni su na popisu python.
- Vrh označava najviši indeks stoga koji se u početku uzima -1 za označavanje praznog stoga.
Početni status stoga može se vidjeti na slici gdje je max_size = 5
Gurnite element u hrpu
Sada, ako želite unijeti ili gurnuti element u stog, to morate zapamtiti
- Vrh će usmjeriti indeks na koji će se element umetnuti.
- I da nijedan element neće biti umetnut kad je stog pun, tj. Kada je max_size = top.
Pa koji bi trebao biti algoritam ??
pretvoriti niz u datum u Java
# vraća maksimalnu veličinu stoga def get_max_size (self): return self .__ max_size # vraća vrijednost bool-a bez obzira je li stog pun ili nije, True ako je pun i False inače def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes element na vrhu steka def push (self, data): if (self.is_full ()): print ('stog je već pun') else: self .__ top = self .__ top + int (1 ) self .__ elementi [self .__ top] = podaci # Možete koristiti donji __str __ () za ispis elemenata DS objekta tijekom uklanjanja pogrešaka 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 msg
Sada, kada izvršite sljedeće:
stack1 = stog (4)
# Pritisnite sve potrebne elemente.
stack1.push ('A')
stack1.push ('B')
stack1.push ('C')
stack1.push ('E')
ispis (stack1.is_full ())
ispis (hrpa1)
Izlaz:
hrpa je već puna
Pravi
Podaci o hrpi (od vrha do dna): D C B A
Pop elementi iz stoga
Sada, kako ste umetnuli elemente u stog, želite ih iskočiti, pa morate voditi računa o sljedećem:
- Stog nije prazan, tj. Vrh! = -1
- Kada izbrišete podatke, vrh mora usmjeravati na prethodni vrh stoga.
Pa, koji će biti algoritam ??
#returns vrijednost bool-a da li je stek prazan ili ne, True ako je prazan i False inače def is_empty (self): return self .__ top == - 1 #returns iskačena vrijednost def pop (self): if (self.is_empty ()): print ('ništa za iskakanje, već prazno') else: a = self .__ elementi [self .__ top] self .__ top = self .__ top-1 return a #display all the stack elements from top to bottom def display (self): za i u rasponu (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()
Sada, s obzirom na prethodno stvoreni stog, pokušajte iskočiti elemente
ispis (stack1.pop ())
ispis (stack1.pop ())
ispis (hrpa1)
ispis (stack1.pop ())
ispis (stack1.pop ())
ispis (stack1.pop ())
Izlaz:
D
C
Podaci o hrpi (od vrha do dna): B A
B
DO
ništa za iskočiti, već prazno
Primjene strukture podataka steka
- Primjer 1:
Stog se koristi za implementaciju algoritma za podudaranje zagrada za procjenu aritmetičkog izraza, a također i u provedbi poziva metode.
Odgovor na koji je 5.
- Primjer 2:
Međuspremnik u sustavu Windows koristi dva snopa za provedbu operacija poništavanja ponavljanja (ctrl + z, ctrl + y). Radili biste na Windows uređivačima riječi kao što su MS-Word, Notepad itd. Ovdje je tekst napisan u MS-Wordu. Promatrajte kako se tekst mijenjao klikom na Ctrl-Z i Ctrl-Y.
java dvostruka prema int okrugla
Ovdje je kod koji simulira operaciju poništavanja ponavljanja. Prođite kroz kod i promatrajte kako se stog koristi u ovoj implementaciji.
#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 ('Stog je pun !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Stog je prazan! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' Stog je prazan ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Možete koristiti __str __ () za ispis elemenata DS objekt tijekom uklanjanja pogrešaka def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Podaci steka (od vrha do dna): '+ msg return ms g #funkcija za implementaciju uklanjanja ili vraćanja prostora def remove (): globalna međuspremnik, undo_stack data = međuspremnik [len (međuspremnik) -1] međuspremnik.remove (podaci) undo_stack.push (podaci) ispis ('Ukloni:', međuspremnik) #funkcija za provedbu operacije poništavanja def undo (): globalni međuspremnik, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Nema podataka za poništavanje') else: data = undo_stack.pop () clipboard.append ( podaci) redo_stack.push (podaci) print ('Poništi:', međuspremnik) #funkcija za provedbu redoslijed operacije def redo (): globalni međuspremnik, poništi_staknuti, redo_stack if (redo_stack.is_empty ()): print ('Nema podataka ponoviti ') else: data = redo_stack.pop () if (podaci nisu u međuspremniku): print (' Nema podataka za ponovnu obradu ') redo_stack.push (podaci) else: clipboard.remove (data) undo_stack.push ( podaci) print ('Ponovi:', međuspremnik) međuspremnik = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stog (len (međuspremnik)) redo_stack = Stog (len (međuspremnik)) remove () poništi () redo ()
Izlaz:
Ukloni: [„A“, „B“, „C“, „D“, „E“]
Poništi: [„A“, „B“, „C“, „D“, „E“, „F“]
Ponovi: [„A“, „B“, „C“, „D“, „E“]
Ovim smo došli do kraja ovog članka o strukturi podataka steka u Pythonu. Ako ste sami uspješno razumjeli i pokrenuli kodove, više niste novak u strukturi podataka stekova.
Imate pitanje za nas? Molimo navedite ga u odjeljku za komentare ovog članka i javit ćemo vam se što je prije moguće.
Da biste stekli detaljno znanje o Pythonu, zajedno s raznim aplikacijama, možete se prijaviti uživo s 24/7 podrškom i doživotnim pristupom.