Ce sunt structurile de date Stack în Python?

Structurile de date sunt o colecție de valori ale datelor, relațiile dintre ele și funcțiile sau operațiile care pot fi aplicate datelor. Acum sunt disponibile o mulțime de structuri de date. Dar astăzi accentul nostru va fi pe structurile de date Stack. Voi discuta următoarele subiecte:

• De ce structuri de date?
• Tipuri de structuri de date
• Ce este structura de date Stack?
• Crearea structurii de date a stivei
• Împingeți elementele în stivă
• Pop Elements from Stack
• Aplicații ale structurii de date Stack

De ce structuri de date?

Pentru a răspunde la acest lucru, va trebui să vă gândiți la un nivel mare. Gândiți-vă cum vă arată Google Maps cel mai bun traseu în doar o fracțiune de secunde, cum vă returnează rezultatul căutării în microsecunde. Nu se ocupă doar de 100 de site-uri web, se ocupă cu mai mult de un miliard de site-uri și încă arată rezultatele atât de repede.

Ei bine, deși algoritmul folosit joacă un rol crucial, structura datelor sau containerul folosit este fundamentul acelui algoritm. În orice aplicație, organizarea și stocarea datelor într-un mod sau într-o structură care este cea mai potrivită pentru utilizarea sa este esențială pentru accesul și prelucrarea eficientă a datelor.

Tipuri de structuri de date

Există câteva structuri de date standard care pot fi utilizate pentru a lucra eficient cu datele. Putem chiar să le personalizăm sau să construim altele complet noi pentru a se potrivi aplicației noastre.

Ce este structura de date Stack?

Luați în considerare câteva exemple din viața reală:

• Expediere în marfă
• Farfurii pe o tavă
• Teanc de monede
• Stiva de sertare
• Manevrarea trenurilor într-o curte de cale ferată

Toate aceste exemple urmează un Last-In-First-Out strategie. Luați în considerare plăcile de pe o tavă, când doriți să alegeți o placă, sunteți forțați să alegeți o placă de sus, în timp ce atunci când plăcile au fost ținute pe tavă, acestea trebuie să fie în ordine inversă. Deasupra exemplelor care urmează Last-In-First-Out (LIFO) principiul sunt cunoscute sub numele de Grămadă .

În afară de operațiile complementare, pot spune că principalele operațiuni posibile pe stivă sunt:

1. Împingeți sau introduceți un element în partea de sus a stivei
2. Apăsați sau eliminați un element din partea de sus a stivei

Crearea structurii de date a stivei

class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1

• max_size este numărul maxim de elemente așteptat în stivă.
• Elementele stivei sunt stocate în lista python.
• Sus indică indexul cel mai de sus al stivei, care este inițial luat -1 pentru a marca stiva goală.

Starea inițială a Stivei poate fi văzută în Figura unde max_size = 5

Împingeți elementul în stivă

Acum, dacă doriți să introduceți sau să împingeți elementul în stivă, trebuie să vă amintiți acest lucru

• Partea de sus va indica indexul la care va fi inserat elementul.
• Și că niciun element nu va fi inserat când stiva este plină, adică când max_size = top.

Deci, care ar trebui să fie algoritmul ??

controler de vizualizare model în java

# returnează dimensiunea maximă a stivei def get_max_size (self): returnează self .__ max_size # returnează valoarea bool indiferent dacă stiva este plină sau nu, True dacă este plin și False altfel def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes element in the top of stack def push (self, data): if (self.is_full ()): print ('stiva este deja plină') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data # Puteți utiliza __str __ () de mai jos pentru a imprima elementele obiectului DS în timp ce depanați 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

Acum, când executați următoarele:

stack1 = Stack (4)

# Apăsați toate elementele necesare.

stack1.push („A”)

stack1.push („B”)

stack1.push („C”)

stack1.push („E”)

print (stack1.is_full ())

print (stack1)

Ieșire:

stiva este deja plină
Adevărat
Stive date (de sus în jos): D C B A

Pop Elements from Stack

Acum, pe măsură ce ați inserat elementele în stivă, doriți să le deschideți, deci trebuie să aveți grijă de următoarele:

• Stiva nu este goală, adică sus! = -1
• Când ștergeți datele, partea de sus trebuie să indice partea de sus a stivei.

Deci, care va fi algoritmul ??

# returnează valoarea bool dacă stiva este goală sau nu, True dacă este goală și False altfel def is_empty (self): return self .__ top == - 1 # returnează popped value def pop (self): if (self.is_empty ()): print ('nimic de pop, deja gol') altceva: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 return a #display toate elementele stivei de sus în jos def display (auto): pentru i în interval (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()

Acum, având în vedere stiva creată anterior, încercați să deschideți elemente

print (stack1.pop ())

print (stack1.pop ())

print (stack1)

print (stack1.pop ())

print (stack1.pop ())

print (stack1.pop ())

Ieșire:

D

C

Stiva date (de sus în jos): B A

B

LA

nimic de scos, deja gol

Aplicații ale structurii de date Stack

• Exemplul 1:

O stivă este utilizată pentru implementarea algoritmului de potrivire a parantezelor pentru evaluarea expresiei aritmetice și, de asemenea, în implementarea apelurilor de metodă.

Răspunsul la care este 5.

• Exemplul 2:

Clipboard în Windows folosește două stive pentru a implementa operații de anulare-refacere (ctrl + z, ctrl + y). Ați fi lucrat la editori de cuvinte Windows, cum ar fi MS-Word, Notepad, etc. Aici este un text scris în MS-Word. Observați cum s-a schimbat textul făcând clic pe Ctrl-Z și Ctrl-Y.

java sort arraylist de numere întregi

Iată un cod care simulează operația de anulare-refacere. Parcurgeți codul și observați cum este folosit stiva în această implementare.

#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 ('Stiva este plină !!') else: self .__ top + = 1 self .__ elements [self .__ top] = date def pop (self): if (self.is_empty ()): print ('Stiva este goală! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 returnare afișare def date (self): if (self.is_empty ()): print („Stiva este goală”) else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Puteți utiliza __str __ () de mai jos pentru a imprima elementele din Obiect DS în timp ce depanarea 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 #function to implement remove or backspace operation def remove (): clipboard global, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) #funcție de implementare a operației de anulare def undo (): clipboard global, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Nu există date de anulat') else: data = undo_stack.pop () clipboard.append ( date) redo_stack.push (data) print ('Undo:', clipboard) #funcție pentru implementarea operației reface def refo (): clipboard global, undo_stack, reface_stack if (redo_stack.is_empty ()): print ('Nu există date a reface ') else: data = redo_stack.pop () if (datele nu sunt în clipboard): print (' Nu există date de refăcut ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( date) print ('Reface:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (clipboard)) remove () undo () reface ()

Ieșire:

Eliminați: [„A”, „B”, „C”, „D”, „E”]

Anulați: [„A”, „B”, „C”, „D”, „E”, „F”]

Reface: [„A”, „B”, „C”, „D”, „E”]

Cu aceasta, ajungem la sfârșitul acestui articol Stack Data Structure in Python. Dacă ați înțeles și ați rulat codurile singuri, nu mai sunteți un începător în Stacks Data Structure.

Ai o întrebare pentru noi? Vă rugăm să o menționați în secțiunea de comentarii a acestui articol și vă vom răspunde cât mai curând posibil.

Pentru a obține cunoștințe aprofundate despre Python împreună cu diferitele sale aplicații, vă puteți înscrie pentru live cu suport 24/7 și acces pe viață.