Ang Mga Structure ng Data ay isang koleksyon ng mga halaga ng data, ang mga ugnayan sa kanila, at ang mga pagpapaandar o pagpapatakbo na maaaring mailapat sa data. Ngayon maraming mga magagamit na Mga Structure ng Data. Ngunit ngayon ang aming pokus ay sa Stack Data Structures. Tatalakayin ko ang mga sumusunod na paksa:
- Bakit Mga Istraktura ng Data?
- Mga uri ng istraktura ng data
- Ano ang Istraktura ng Stack Data?
- Paglikha ng Istraktura ng Data ng Stack
- Itulak ang Mga Elemento sa Stack
- Mga Elementong Pop mula sa Stack
- Mga Aplikasyon ng Istraktura ng Data ng Stack
Bakit Mga Istraktura ng Data?
Upang sagutin ito kakailanganin mong mag-isip sa isang malaking antas. Isipin kung paano ipinapakita sa iyo ng mga mapa ng Google ang pinakamahusay na ruta sa maliit na bahagi lamang ng segundo, kung paano ka babalik sa iyo ng resulta ng paghahanap sa mga microsecond. Hindi ito nakikipag-usap sa 100 mga website lamang, nakikipag-usap ito sa higit sa isang bilyong mga site at ipinapakita pa rin sa iyo ang napakabilis na resulta.
Kaya, kahit na ang ginamit na algorithm ay may mahalagang papel, ang istraktura ng data o ang lalagyan na ginamit ay ang pundasyon ng algorithm na iyon. Sa anumang aplikasyon, ang pag-aayos at pag-iimbak ng data sa isang paraan o sa isang istrakturang pinakaangkop sa paggamit nito ay susi sa mahusay na pag-access at pagproseso ng data.
Mga uri ng istraktura ng data
Mayroong ilang mga pamantayang istraktura ng data na maaaring magamit upang mahusay na gumana sa data. Maaari rin naming ipasadya ang mga ito o bumuo ng mga ganap na bago upang umangkop sa aming aplikasyon.
Ano ang Istraktura ng Stack Data?
Isaalang-alang ang ilang mga halimbawa ng totoong buhay:
- Kargamento sa kargamento
- Mga plate sa isang tray
- Stack ng mga barya
- Stack ng drawer
- Shunting ng mga tren sa isang bakuran ng riles
Ang lahat ng mga halimbawang ito ay sumusunod a Huling pumasok Unang lumabas diskarte Isaalang-alang ang mga plato sa isang tray, Kung nais mong pumili ng isang plato ay pinipilit kang pumili ng isang plato mula sa itaas samantalang kapag ang mga plato ay itinatago sa tray dapat silang nasa reverse order. Sa itaas ng mga halimbawa na sumusunod sa Last-In-First-Out (LIFO) prinsipyo ay kilala bilang Stack .
Bukod sa mga pantulong na pagpapatakbo, maaari kong sabihin na ang pangunahing mga Operasyong posible sa stack ay:
- Itulak o ipasok ang isang elemento sa tuktok ng stack
- I-pop o alisin ang isang elemento mula sa tuktok ng stack
Paglikha ng Istraktura ng Data ng Stack
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [Wala] * sarili .__ max_size self .__ top = -1
- max_size ay ang maximum na bilang ng mga elemento na inaasahan sa stack.
- Ang mga elemento ng stack ay nakaimbak sa listahan ng sawa.
- Ipinapahiwatig ng tuktok ang pinakamataas na index ng stack na kung saan Ay unang kinuha -1 upang markahan ang walang laman na stack.
Ang paunang katayuan ng Stack ay makikita sa Larawan kung saan max_size = 5
Itulak ang Element sa Stack
Ngayon, kung nais mong ipasok o itulak ang elemento sa stack, dapat mong tandaan iyon
- Ituturo ng tuktok ang index kung saan ipapasok ang elemento.
- At walang sangkap na ipapasok kapag ang stack ay puno ibig sabihin kapag max_size = itaas.
Kaya ano ang dapat na algorithm ??
# nagbabalik ng maximum na laki ng stack def get_max_size (sarili): bumalik sa sarili .__ max_size # nagbabalik ng halaga ng bool maging puno ang stack o hindi, Totoo kung puno at Maling kung hindi man def is_full (sarili): ibalik ang self.get_max_size () - 1 == sarili .__ nangungunang #pushes na elemento sa tuktok ng stack def push (sarili, data): kung (self.is_full ()): print ('puno na ang stack') iba pa: sarili .__ tuktok = sarili .__ tuktok + int (1 ) self .__ element [self .__ top] = data #Maaari mong gamitin ang nasa ibaba __str __ () upang mai-print ang mga elemento ng DS object habang idi-debug ang def __str __ (self): msg = [] index = self .__ itaas habang (index> = 0): msg.append ((str) (self .__ elemento [index])) index- = 1 msg = '.join (msg) msg = 'Data ng stack (Itaas sa Ibaba):' + msg ibalik ang msgNgayon, Kapag naisagawa mo ang sumusunod:
stack1 = Stack (4)
#Push ang lahat ng kinakailangang elemento (s).
stack1.push (“A”)
stack1.push (“B”)
stack1.push (“C”)
stack1.push (“E”)
i-print (stack1.is_full ())
i-print (stack1)
Output:
puno na ang stack
Totoo
Data ng stack (Itaas hanggang Ibaba): D C B A
Mga Elementong Pop mula sa Stack
Ngayon, habang naipasok mo ang mga elemento sa stack, nais mong i-pop ang mga ito, kaya kailangan mong alagaan ang mga sumusunod:
- Ang stack ay hindi walang laman hal. Tuktok! = -1
- Kapag tinanggal mo ang data, ang tuktok ay dapat na magturo sa nakaraang tuktok ng stack.
Kaya, ano ang magiging algorithm ??
#returns bool halaga kung ang stack ay walang laman o hindi, Totoo kung walang laman at Maling kung hindi man def is_empty (sarili): bumalik sa sarili .__ tuktok == - 1 # bumalik ang pop na halaga def pop (sarili): kung (self.is_empty ()): i-print ('walang i-pop, walang laman') iba pa: a = sarili .__ na mga elemento [sarili .__ tuktok] sarili .__ tuktok = sarili .__ tuktok-1 ibalik ang isang # ipakita ang lahat ng mga elemento ng stack mula sa itaas hanggang sa ilalim ng pagpapakita ng def (sarili): para sa i sa saklaw (sarili .__ tuktok, -1, -1): i-print (sarili .__ elemento [i], end = ') print ()Ngayon, isinasaalang-alang ang dating nilikha na stack, subukang mag-pop ng mga elemento
i-print (stack1.pop ())
i-print (stack1.pop ())
i-print (stack1)
i-print (stack1.pop ())
i-print (stack1.pop ())
i-print (stack1.pop ())
Output:
D
C
Data ng stack (Itaas hanggang Ibaba): B A
B
SA
walang pop, wala nang laman
Mga Aplikasyon ng Istraktura ng Data ng Stack
- Halimbawa 1:
Ang isang stack ay ginagamit upang magpatupad ng algorithm ng pagtutugma ng bracket para sa pagsusuri ng ekspresyon ng arithmetic at pati na rin sa pagpapatupad ng mga tawag sa pamamaraan.
Sagot na alin ang 5.
java cast doble sa int
- Halimbawa 2:
Clipboard sa Windows gumagamit ng dalawang stack upang ipatupad ang undo-redo (ctrl + z, ctrl + y) na mga operasyon. Magagawa mo sana ang mga editor ng salita sa Windows tulad ng MS-Word, Notepad, atbp. Narito ang isang teksto na nakasulat sa MS-Word. Pagmasdan kung paano nagbago ang teksto sa pag-click sa Ctrl-Z at Ctrl-Y.
Narito ang isang code na simulate ang undo-redo operasyon. Dumaan sa code at obserbahan kung paano ginagamit ang stack sa pagpapatupad na ito.
#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [Wala] * 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 ('Ang stack ay puno !!') iba pa: sarili .__ tuktok + = 1 sarili .__ elemento [sarili .__ tuktok] = data def pop (sarili): kung (self.is_empty ()): i-print ('Walang laman ang stack! ! ') else: data = self .__ elemento [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' The stack is kosong ') else: index = self .__ itaas habang (index> = 0): print (self .__ elemento [index]) index- = 1 def get_max_size (self): return self .__ max_size #Maaari mong gamitin ang nasa ibaba __str __ () upang mai-print ang mga elemento ng DS object habang ina-debug ang def __str __ (sarili): msg = [] index = self .__ itaas habang (index> = 0): msg.append ((str) (self .__ elemento [index])) index- = 1 msg = ' '.sali (msg) msg =' Stack data (Itaas sa Ibaba): '+ msg ibalik ang ms g #function upang ipatupad ang alisin o backspace operasyon def alisin (): pandaigdigang clipboard, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Alisin:', clipboard) #function upang ipatupad ang undo operation def undo (): global clipboard, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Walang data upang i-undo') iba pa: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('I-undo:', clipboard) #function upang ipatupad ang gawing muli ang operasyon def redo (): pandaigdigang clipboard, undo_stack, redo_stack kung (redo_stack.is_empty ()): i-print ('Walang data upang gawing muli ') iba pa: data = redo_stack.pop () kung (data wala sa clipboard): i-print (' Walang data upang mag-redo ') data) print ('Redo:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (clipboard)) alisin () i-undo () gawing muli ()Output:
Alisin: ['A', 'B', 'C', 'D', 'E']
I-undo: ['A', 'B', 'C', 'D', 'E', 'F']
Gawing muli: ['A', 'B', 'C', 'D', 'E']
Sa pamamagitan nito, natapos namin ang istraktura ng Stack Data Structure na ito sa artikulong Python. Kung matagumpay mong naintindihan at pinatakbo ang mga code sa pamamagitan ng iyong sarili hindi ka na isang baguhan sa Structure Data Structure.
May tanong ba sa amin? Mangyaring banggitin ito sa seksyon ng mga komento ng artikulong ito at babalikan ka namin sa lalong madaling panahon.
Upang makakuha ng malalim na kaalaman sa Python kasama ang iba't ibang mga application nito, maaari kang magpatala nang live na may 24/7 na suporta at buhay na pag-access.