Què són les estructures de dades de pila a Python?



Aquest article us proporcionarà un coneixement detallat i complet de les estructures de dades de pila a Python amb molts exemples.

Les Estructures de dades són una col·lecció de valors de dades, les relacions entre ells i les funcions o operacions que es poden aplicar a les dades. Ara hi ha moltes estructures de dades disponibles. Però avui ens centrarem en les estructures de dades de pila. Parlaré dels temes següents:

Per què les estructures de dades?

Per respondre a això, haurà de pensar a un gran nivell. Penseu com Google Maps us mostra la millor ruta en pocs segons, com us proporciona el resultat de la cerca en microsegons. No tracta només amb 100 llocs web, tracta amb més de mil milions de llocs i encara us mostra els resultats tan ràpidament.





Bé, tot i que l'algorisme utilitzat té un paper crucial, l'estructura de dades o el contenidor utilitzat són la base d'aquest algorisme. En qualsevol aplicació, l’organització i l’emmagatzematge de dades d’una manera o en una estructura que s’adapti millor al seu ús és clau per a un accés i processament eficaç de les dades.

Tipus d’estructures de dades

Hi ha algunes estructures de dades estàndard que es poden utilitzar per treballar de manera eficient amb les dades. Fins i tot podem personalitzar-los o crear-ne de nous completament adequats a la nostra aplicació.



Tipus d’estructures de dades

Què és l'estructura de dades de la pila?

Penseu en alguns exemples de la vida real:

  • Enviament en càrrega
  • Plats en una safata
  • Pila de monedes
  • Pila de calaixos
  • Maniobra de trens en un pati de ferrocarril

plates-stacks-data-structure



Tots aquests exemples segueixen a Últim-Primer-Sortit estratègia. Tingueu en compte els plats d’una safata. Quan vulgueu triar un plat, esteu obligats a triar un plat de la part superior, mentre que quan es conservaven a la safata, han d’estar en ordre invers. A sobre dels exemples que segueixen el Última entrada-primera sortida (LIFO) principi es coneixen com Pila .

A part de les operacions complementàries, puc dir que les principals operacions possibles a la pila són:

  1. Premeu o inseriu un element a la part superior de la pila
  2. Feu saltar o traieu un element de la part superior de la pila

Creació d’una estructura de dades de pila

class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [Cap] * self .__ max_size self .__ top = -1
  • mida_màxima és el nombre màxim d'elements que s'espera a la pila.
  • Els elements de la pila s’emmagatzemen a la llista python.
  • La part superior indica l'índex més alt de la pila que inicialment es pren -1 per marcar la pila buida.

L'estat inicial de la pila es pot veure a la figura on max_size = 5

Introduïu l'element a la pila

Ara, si voleu introduir o empènyer l'element a la pila, heu de recordar-ho

  • La part superior assenyalarà l'índex al qual s'inserirà l'element.
  • I que no s'inserirà cap element quan la pila estigui plena, és a dir, quan max_size = top.

Llavors, quin hauria de ser l'algorisme ??

controlador de vista de model a Java
# retorna la mida màxima de la pila def get_max_size (self): torna self .__ max_size # retorna el valor bool si la pila està plena o no, True si està plena i False def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes element a la part superior de la pila def push (self, dades): if (self.is_full ()): print ('la pila ja està plena') else: self .__ top = self .__ top + int (1 ) elements self .__ [self .__ top] = dades # Podeu utilitzar el següent __str __ () per imprimir els elements de l’objecte DS mentre es depura 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

Ara, quan executeu el següent:

stack1 = Pila (4)

#Premeu tots els elements necessaris.

stack1.push ('A')

stack1.push ('B')

stack1.push ('C')

stack1.push ('E')

print (stack1.is_full ())

imprimir (pila1)

Sortida:

la pila ja està plena
És cert
Dades de la pila (de dalt a baix): D C B A

Elements pop de Stack

Ara, a mesura que heu inserit els elements a la pila, voleu fer-los aparèixer, de manera que heu de tenir cura del següent:

  • La pila no està buida, és a dir, superior! = -1
  • Quan suprimiu les dades, la part superior ha d’assenyalar la part superior anterior de la pila.

Llavors, quin serà l'algorisme ??

# retorna el valor bool si la pila està buida o no, és cert si està buida i falsa en cas contrari def is_empty (self): torna self .__ top == - 1 # torna el valor aparegut def pop (self): if (self.is_empty ()): print ('res a aparèixer, ja buit') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 retorna a #display tots els elements de la pila de dalt a baix def display (auto): per a l’interval (auto .__ superior, -1, -1): print (elements .__ auto [i], end = '') print ()

Ara, tenint en compte la pila creada anteriorment, intenteu fer pop elements

print (stack1.pop ())

print (stack1.pop ())

imprimir (pila1)

print (stack1.pop ())

print (stack1.pop ())

print (stack1.pop ())

Sortida:

D

C

Dades de la pila (de dalt a baix): B A

B

A

res de pop, ja buit

Aplicacions de l'estructura de dades de la pila

  • Exemple 1:

S'utilitza una pila per implementar l'algoritme de coincidència de claudàtors per a l'avaluació d'expressions aritmètiques i també en la implementació de trucades de mètodes.

La resposta a la qual és 5.

  • Exemple 2:

Portapapers al Windows utilitza dues piles per implementar operacions de desfer-refés (ctrl + z, ctrl + y). Hauríeu treballat en editors de paraules de Windows com MS-Word, Bloc de notes, etc. Aquí teniu un text escrit en MS-Word. Observeu com ha canviat el text en fer clic a Ctrl-Z i Ctrl-Y.

què és hashset a Java

Aquí teniu un codi que simula l’operació de desfer i refer. Consulteu el codi i observeu com s’utilitza la pila en aquesta implementació.

#creating class stack class Pila: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [Cap] * 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 ('La pila està plena !!') else: self .__ top + = 1 self .__ elements [self .__ top] = def de dades pop (self): if (self.is_empty ()): print ('La pila està buida! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 mostrar dades per defecte (self): if (self.is_empty ()): print (' La pila està buida ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # Podeu utilitzar el següent __str __ () per imprimir els elements del Objecte DS mentre es depura def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg ​​=' Dades de pila (de dalt a baix): '+ msg return ms g #function to implement remove or backspace operation def remove (): portapapers global, undo_stack data = portapapers [len (portapapers) -1] portapapers.remove (dades) undo_stack.push (data) print ('Elimina:', portapapers) #function to implement undo operation def undo (): porta-retalls global, undo_stack, refo_stack if (undo_stack.is_empty ()): print ('No hi ha dades per desfer') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Desfés:', porta-retalls) #function to implement refe operation def refo (): portapapers global, undo_stack, refo_stack if (redo_stack.is_empty ()): print ('No hi ha dades tornar a fer ') else: data = redo_stack.pop () if (dades no al porta-retalls): print (' No hi ha dades per refer ') redo_stack.push (dades) else: clipboard.remove (data) undo_stack.push ( data) print ('Refés:', porta-retalls) porta-retalls = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Pila (len (porta-retalls)) redo_stack = Pila (len (porta-retalls)) remove () undo () refet ()

Sortida:

Elimina: ['A', 'B', 'C', 'D', 'E']

Desfés: ['A', 'B', 'C', 'D', 'E', 'F']

Refés: ['A', 'B', 'C', 'D', 'E']

Amb això, arribem al final d’aquest article de Stack Data Structure in Python. Si heu entès i executat els codis per vosaltres mateixos, ja no sou principiants de Stacks Data Structure.

Tens alguna pregunta? Si us plau, mencioneu-lo a la secció de comentaris d’aquest article i us respondrem el més aviat possible.

Per obtenir coneixements en profunditat sobre Python juntament amb les seves diverses aplicacions, podeu inscriure-us a la publicació amb assistència les 24 hores del dia, els 7 dies de la setmana i accés permanent.