Datu struktūras ir datu vērtību kopums, attiecības starp tām un funkcijas vai darbības, kuras var izmantot datiem. Tagad ir pieejamas daudzas datu struktūras. Bet šodien mūsu uzmanība tiks koncentrēta uz kaudzes datu struktūrām. Es apspriedīšu šādas tēmas:
- Kāpēc datu struktūras?
- Datu struktūru veidi
- Kas ir kaudzes datu struktūra?
- Steka datu struktūras izveide
- Ievietojiet elementus kaudzē
- Popelementi no kaudzes
- Steka datu struktūras pielietojumi
Kāpēc datu struktūras?
Lai atbildētu uz to, jums būs jādomā lielā līmenī. Padomājiet, kā Google Maps parāda labāko maršrutu tikai dažu sekunžu laikā, kā tas mikrosekundēs atgriež jūsu meklēšanas rezultātu. Tas nenodarbojas tikai ar 100 vietnēm, tas attiecas uz vairāk nekā miljardu vietņu un joprojām parāda rezultātu tik ātri.
Lai gan izmantotajam algoritmam ir izšķiroša loma, datu struktūra vai izmantotais konteiners ir šī algoritma pamats. Jebkurā lietojumprogrammā datu efektīvai piekļuvei un apstrādei galvenā nozīme ir datu organizēšana un glabāšana tādā veidā vai struktūrā, kas ir vispiemērotākā to lietošanai.
Datu struktūru veidi
Ir dažas standarta datu struktūras, kuras var izmantot, lai efektīvi strādātu ar datiem. Mēs pat varam tos pielāgot vai izveidot pilnīgi jaunus, lai tie atbilstu mūsu lietojumprogrammai.
Kas ir kaudzes datu struktūra?
Apsveriet dažus reālās dzīves piemērus:
- Sūtījums kravā
- Plātnes uz paplātes
- Monētu kaudze
- Atvilktņu kaudze
- Vilcienu manevrēšana dzelzceļa pagalmā
Visi šie piemēri seko a Last-In-First-Out stratēģiju. Apsveriet plāksnes uz paplātes. Ja vēlaties izvēlēties plāksni, jums ir jāpiespiež plāksne no augšas, turpretim, kad plāksnes turēja uz paplātes, tām jābūt apgrieztā secībā. Iepriekš minētie piemēri, kas seko Last-in-first-out (LIFO) princips ir pazīstams kā Kaudze .
Papildus papildu operācijām es varu teikt, ka galvenās iespējamās operācijas kaudzē ir:
- Pabīdiet vai ievietojiet elementu kaudzes augšdaļā
- Pop vai noņemiet elementu no kaudzes augšdaļas
Steka datu struktūras izveide
klases kaudze: def __init __ (self, max_size): self .__ max_size = max_size self .__ elementi = [Neviens] * self .__ max_size self .__ top = -1
- max_size ir maksimālais kaudzē gaidāmo elementu skaits.
- Steka elementi tiek glabāti pitonu sarakstā.
- Augšdaļa norāda augšējo kaudzes indeksu, kas sākotnēji tiek ņemts -1, lai atzīmētu tukšu kaudzi.
Sākotnējais kaudzes statuss ir redzams attēlā, kur max_size = 5
Iebīdiet elementu kaudzē
Tagad, ja vēlaties ievadīt vai nospiest elementu kaudzē, tas ir jāatceras
- Augšdaļa norādīs indeksu, kurā elements tiks ievietots.
- Un ka neviens elements netiks ievietots, kad kaudze ir pilna, t.i., kad max_size = top.
Kādam tad jābūt algoritmam ??
# atgriež maksimālo kaudzes def lielumu get_max_size (self): return self .__ max_size # atgriež bool vērtību neatkarīgi no tā, vai kaudze ir pilna vai nav, True, ja pilna un False, citādi def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes elements kaudzes augšdaļā def push (self, data): if (self.is_full ()): print ('kaudze jau ir pilna') cits: self .__ top = self .__ top + int (1 ) self .__ elementi [self .__ top] = dati # Varat izmantot zemāk esošo __str __ (), lai izdrukātu DS objekta elementus, atkļūdojot def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elementi [rādītājs])) index- = 1 msg = '' .join (msg) msg = 'Steka dati (no augšas uz leju):' + msg atbildes ziņojumsTagad, kad izpildāt sekojošo:
kaudze1 = kaudze (4)
#Piespiediet visus nepieciešamos elementus.
stack1.push (“A”)
stack1.push (“B”)
stack1.push (“C”)
stack1.push (“E”)
drukāt (stack1.is_full ())
drukāt (kaudze1)
java kā iziet no programmas
Izeja:
kaudze jau ir pilna
Patiesi
Steka dati (no augšas uz leju): D C B A
Popelementi no kaudzes
Kad elementi ir ievietoti kaudzē, vēlaties tos izlaist, tāpēc jums jārūpējas par šādām darbībām:
- Steks nav tukšs, t.i., augšējais! = -1
- Dzēšot datus, augšdaļai jānorāda uz iepriekšējo kaudzes augšdaļu.
Tātad, kāds būs algoritms ??
#returns bool vērtība neatkarīgi no tā, vai kaudze ir tukša vai nē, True, ja tukša un False, citādi def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): drukāt ('nekas nav pop, jau tukšs') cits: a = self .__ elementi [self .__ top] self .__ top = self .__ top-1 atgriež # displejā visus steka elementus no augšas uz leju def displejs (pats): i diapazonā (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()Tagad, ņemot vērā iepriekš izveidoto kaudzīti, mēģiniet pop elementus
drukāt (stack1.pop ())
drukāt (stack1.pop ())
drukāt (kaudze1)
drukāt (stack1.pop ())
drukāt (stack1.pop ())
drukāt (stack1.pop ())
Izeja:
D
C
Steka dati (no augšas uz leju): B A
B
TO
nekas pops, jau tukšs
Steka datu struktūras pielietojumi
- 1. piemērs:
Steks tiek izmantots, lai ieviestu iekavu atbilstības algoritmu aritmētiskās izteiksmes novērtēšanai un arī metožu izsaukumu ieviešanai.
Atbilde uz kuru ir 5.
- 2. piemērs:
Starpliktuve operētājsistēmā Windows izmanto divas kaudzes, lai īstenotu atsaukšanas-atsaukšanas (ctrl + z, ctrl + y) darbības. Jūs būtu strādājis ar Windows vārdu redaktoriem, piemēram, MS-Word, Notepad utt. Šeit teksts ir rakstīts MS-Word. Novērojiet, kā mainījās teksts, noklikšķinot uz Ctrl-Z un Ctrl-Y.
Šeit ir kods, kas simulē atsaukšanas un atsaukšanas darbību. Izskatiet kodu un novērojiet, kā kaudze tiek izmantota šajā ieviešanā.
#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 ('Steks ir pilns !!') cits: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('Steks ir tukšs! ! ') else: data = self .__ elementi [self .__ top] self .__ top- = 1 atgriež datu def displeju (self): if (self.is_empty ()): print (' Steks ir tukšs ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Varat izmantot šo __str __ (), lai izdrukātu elementus DS objekts, atkļūdojot def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Steka dati (no augšas uz leju): '+ msg atgriež ms g # function to remove or backspace operation def remove (): global starpliktuve, undo_stack data = starpliktuve [len (starpliktuve) -1] clipboard.remove (dati) undo_stack.push (dati) print ('Noņemt:', starpliktuve) #function, lai ieviestu atsaukšanas darbību def undo (): globālā starpliktuve, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Nav atsaucamu datu') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', starpliktuve) # function to perform redo operation def redo (): globālā starpliktuve, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Nav datu pārtaisīt ') else: data = redo_stack.pop () if (dati nav starpliktuvē): print (' Nav datu, ko pārtaisīt ') redo_stack.push (dati) else: clipboard.remove (data) undo_stack.push ( dati) print ('Redo:', starpliktuve) starpliktuve = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (starpliktuve)) redo_stack = Stack [len (starpliktuve)] noņemt () atsaukt () pārtaisīt ()Izeja:
Noņemt: [’A’, ’B’, ‘C’, ‘D’, ‘E’]
Atsaukt: [’A’, ’B’, ‘C’, ‘D’, ‘E’, ‘F’]
Pārtaisīt: [’A’, ’B’, ‘C’, ‘D’, ‘E’]
Ar to mēs esam nonākuši šīs kaudzes datu struktūras Python rakstā. Ja jūs veiksmīgi sapratāt un paši izpildījāt kodus, jūs vairs neesat Stacks Data Structure iesācējs.
Vai mums ir jautājums? Lūdzu, pieminējiet to šī raksta komentāru sadaļā, un mēs sazināsimies ar jums pēc iespējas ātrāk.
Lai iegūtu padziļinātas zināšanas par Python kopā ar dažādām lietojumprogrammām, varat reģistrēties tiešraidē ar diennakts atbalstu un piekļuvi mūža garumā.