Az adatstruktúrák az adatértékek, az azok közötti kapcsolatok és az adatokra alkalmazható funkciók vagy műveletek gyűjteménye. Most rengeteg adatstruktúra áll rendelkezésre. De ma a Stack Data Structures-re fogunk összpontosítani. A következő témákat fogom megvitatni:
- Miért pont az adatstruktúrák?
- Az adatszerkezetek típusai
- Mi a verem adatszerkezete?
- Verem adatstruktúra létrehozása
- Tolja az elemeket a verembe
- Pop elemek a veremből
- A verem adatszerkezetének alkalmazásai
Miért pont az adatstruktúrák?
Ennek megválaszolásához nagy szinten kell gondolkodnia. Gondoljon arra, hogy a Google maps miként mutatja meg a legjobb útvonalat másodpercek töredéke alatt, miként adja vissza a keresési eredményt mikroszekundumokban. Nem csak 100, hanem több mint egymilliárd weboldallal foglalkozik, és még mindig ilyen gyorsan mutatja az eredményt.
Nos, bár a használt algoritmus döntő szerepet játszik, az alkalmazott adatstruktúra vagy tároló az alapja ennek az algoritmusnak. Bármely alkalmazásban az adatok hatékony elérésének és feldolgozásának kulcsa az adatok olyan módon vagy struktúrában történő rendezése és tárolása, amely a legjobban megfelel a felhasználásának.
Az adatszerkezetek típusai
Van néhány szabványos adatstruktúra, amelyek felhasználhatók az adatok hatékony kezelésére. Akár testre is szabhatjuk őket, vagy teljesen újakat készíthetünk az alkalmazásunknak megfelelően.
Mi a verem adatszerkezete?
Vegyünk néhány valós példát:
- Szállítás rakományban
- Lemezek egy tálcán
- Verem az érmék
- Fiókos köteg
- A vonatok tolatása a vasúti udvaron
Mindezek a példák a Utoljára be, elsőként ki stratégia. Vegyük fontolóra a tálcán lévő lemezeket. Ha tányért szeretne választani, akkor kénytelen felülről felvenni egy lemezt, míg amikor a lemezeket a tálcán tartották, akkor fordított sorrendben kell lenniük. A fenti példákat követve Last-in-first-out (LIFO) elv ismert Kazal .
A kiegészítő műveleteken kívül mondhatom, hogy a veremben lehetséges fő műveletek:
- Tegyen vagy helyezzen be egy elemet a verem tetejére
- Pop vagy távolítson el egy elemet a verem tetején
Verem adatstruktúra létrehozása
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size a veremben várható elemek maximális száma.
- A verem elemei a python listában vannak tárolva.
- A Felső a verem legfelső indexét jelöli, amelyet kezdetben -1 vesz az üres verem megjelölésére.
A Verem kezdeti állapota az ábrán látható, ahol max_méret = 5
Tolja az elemet a verembe
Most, ha elemet akar beírni vagy a verembe tolni, akkor emlékeznie kell erre
- A teteje az indexet fogja mutatni, amelybe az elem beillesztésre kerül.
- És hogy egyetlen elem sem kerül beillesztésre, ha a verem megtelt, vagyis amikor max_size = top.
Akkor mi legyen az algoritmus ??
A # visszatér a verem maximális méretéhez def self .__ top #pushes elem a verem tetején def push (én, adatok): if (self.is_full ()): print ('a verem már megtelt') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data #Az alábbi __str __ () segítségével kinyomtathatja a DS objektum elemeit, miközben a def __str __ (self) hibakeresését végzi: msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elemek [index])) index- = 1 msg = '' .join (msg) msg = 'Adatok halmozása (fentről lefelé): + + msgMost, amikor a következőket hajtja végre:
névtér használatával c ++
stack1 = Verem (4)
#Tolja az összes szükséges elemet.
stack1.push („A”)
stack1.push („B”)
stack1.push („C”)
stack1.push („E”)
nyomtatás (stack1.is_full ())
nyomtatás (verem1)
Kimenet:
a verem már megtelt
Igaz
Veremadatok (fentről lefelé): D C B A
hogyan lehet dupla int-re dobni java-ban
Pop elemek a veremből
Most, amikor beillesztette az elemeket a verembe, fel akarja dobni őket, ezért ügyelnie kell a következőkre:
- A verem nem üres, azaz a felső! = -1
- Az adatok törlésekor a tetejének a verem előző tetejére kell mutatnia.
Szóval, mi lesz az algoritmus ??
#returns bool érték, függetlenül attól, hogy a verem üres-e vagy sem, igaz, ha üres és hamis, egyébként def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('semmi nem pop, már üres') más: a = self .__ elemek [self .__ top] self .__ top = self .__ top-1 visszaadja a #display összes veremelemet felülről lefelé def kijelző (self): i tartományban (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()Most, figyelembe véve a korábban létrehozott veremeket, próbáljon meg elemeket feltölteni
nyomtatás (stack1.pop ())
nyomtatás (stack1.pop ())
nyomtatás (verem1)
nyomtatás (stack1.pop ())
nyomtatás (stack1.pop ())
nyomtatás (stack1.pop ())
Kimenet:
D
C
Veremadatok (fentről lefelé): B A
B
NAK NEK
semmi pop, már üres
A verem adatszerkezetének alkalmazásai
- 1. példa:
A verem a zárójel-illesztési algoritmus megvalósítására szolgál az aritmetikai kifejezés kiértékeléséhez és a metódushívások megvalósításához is.
A válasz erre 5.
- 2. példa:
Vágólap a Windows rendszerben két halmot használ az undo-redo (ctrl + z, ctrl + y) műveletek végrehajtására. Dolgoztál volna olyan Windows szószerkesztőkön, mint az MS-Word, a Jegyzettömb stb. Itt van egy szöveg, amelyet MS-Word-be írtak. Figyelje meg, hogyan változott a szöveg a Ctrl-Z és a Ctrl-Y kattintására.
Itt van egy kód, amely a visszavonás-visszavonás műveletet szimulálja. Menjen végig a kódon, és figyelje meg, hogyan használják a verem ebben a megvalósításban.
#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 ('A verem megtelt !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('A verem üres! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' A verem üres ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #Az alábbi __str __ () segítségével kinyomtathatja a DS objektum def __str __ (self) hibakeresése közben: msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elemek [index])) index- = 1 msg = ' '.join (msg) msg =' Adatok halmozása (fentről lefelé): '+ msg visszatér ms g # function eltávolítás vagy visszalépés művelet végrehajtása def remove (): globális vágólap, undo_stack adatok = vágólap [len (vágólap) -1] vágólap.remove (adatok) undo_stack.push (adatok) nyomtatás ('Eltávolítás:', vágólap) # function a visszavonási művelet végrehajtásához def undo (): globális vágólap, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Nincs visszavonható adat') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Visszavonás:', vágólap) # function az átdolgozás végrehajtásához def redo (): globális vágólap, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Nincs adat átdolgozni ') else: data = redo_stack.pop () if (az adatok nincsenek a vágólapon): print (' Nincsenek átadandó adatok ') redo_stack.push (adatok) else: clipboard.remove (data) undo_stack.push ( adatok) print ('Újra:', vágólap) vágólap = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Verem (len (vágólap)) redo_stack = Verem [len (vágólap)] remove () undo () redo ()Kimenet:
Távolítsa el: [„A”, „B”, „C”, „D”, „E”]
fibonacci sorozat program java nyelven
Visszavonás: [„A”, „B”, „C”, „D”, „E”, „F”]
Újra: [„A”, „B”, „C”, „D”, „E”]
Ezzel a Python cikkben szereplő Stack Data Structure végéhez értünk. Ha sikeresen megértette és saját maga futtatta a kódokat, akkor már nem vagy újonc a Stacks Data Structure-ben.
Van egy kérdésünk? Kérjük, említse meg a cikk megjegyzés rovatában, és a lehető leghamarabb kapcsolatba lépünk Önnel.
Ha részletes ismereteket szeretne szerezni a Pythonról és annak különböző alkalmazásokról, regisztrálhat élőben 24/7 támogatással és élethosszig tartó hozzáféréssel.