Las estructuras de datos juegan un papel clave en el mundo de la programación. Nos ayudan a organizar nuestros datos de una manera que se puede utilizar de manera eficiente. La pila es una de las estructuras de datos más simples.
Aprendamos sobre la pila y su implementación en Python.
Tabla de contenido
¿Qué es una pila?
Una pila es similar a la pila de libros, sillas, etc., en la vida real. Y sigue el principio Last-in/First-out (LIFO). Es la estructura de datos más simple. Veamos el escenario con un ejemplo del mundo real.
Digamos que tenemos una pila de libros de la siguiente manera.
Cuando queremos el tercer libro desde arriba, tenemos que quitar los dos primeros libros desde arriba para sacar el tercer libro. Aquí, el libro de arriba va último en la pila y es el primero de la pila. La pila de estructura de datos sigue el mismo principio Last-in/First-out (LIFO) en la programación.
Operaciones en la pila
Hay principalmente dos operaciones en una pila.
1. empujar (datos)
Agrega o inserta los datos en la pila.
2. estallar()
Elimina o extrae el elemento superior de la pila.
Consulte las siguientes ilustraciones de las operaciones de empujar y abrir.
Escribiremos algunas funciones auxiliares que nos ayuden a obtener más información sobre la pila.
Veámoslos.
ojeada()
Devuelve el elemento superior de la pila.
esta vacio()
Devuelve si la pila está vacía o no.
Suficientes aspectos conceptuales de la estructura de datos de la pila. Pasemos a la implementación sin más preámbulos.
Supongo que tiene Python instalado en su PC, si no, también puede probar el compilador en línea.
Implementación de pila
La implementación de la pila es la más fácil en comparación con otras implementaciones de estructuras de datos. Podemos implementar una pila de varias formas en Python.
Vamos a verlos todos uno por uno.
#1. Lista
Vamos a implementar la pila usando la lista en una clase. Veamos la implementación paso a paso de la pila.
Paso 1: escribe una clase llamada Stack.
class Stack: pass
Paso 2: Tenemos que mantener los datos en una lista. Agreguemos una lista vacía en la clase Stack con elementos de nombre.
class Stack: def __init__(self): self.elements = []
Paso 3: Para empujar los elementos a la pila, necesitamos un método. Escribamos un método push que tome datos como argumento y los agreguemos a la lista de elementos.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data
Paso 4: Del mismo modo, escribamos el método pop que extrae el elemento superior de la pila. Podemos usar el método pop del tipo de datos de lista.
class Stack: ## ... def pop(self): return self.elements.pop()
Hemos completado la implementación de la pila con las operaciones requeridas. Ahora, agreguemos las funciones auxiliares para obtener más información sobre la pila.
Paso 5: podemos obtener el elemento superior de la pila usando el índice negativo. El código elemento[-1] devuelve el último de la lista. Es el elemento superior de la pila en nuestro caso.
class Stack: ## ... def peek(self): return self.elements[-1]
Paso 6: si la longitud de la lista de elementos es 0, entonces la pila está vacía. Escribamos un método que devuelva si el elemento está vacío o no.
class Stack: ## ... def is_empty(self): return len(self.elements) == 0
Hemos completado la implementación de la pila utilizando el tipo de datos de lista.
¡Vaya! espera, acabamos de implementarlo. Pero, no vi cómo usarlo. ¿Cómo usarlo entonces?
Ven vamos a ver cómo implementarlo. Tenemos que crear un objeto para que la clase Stack lo use. No es gran cosa. Hagámoslo primero.
class Stack:
## ...
if __name__ == '__main__':
stack = Stack()
Hemos creado el objeto de pila y estamos listos para usarlo. Sigamos los pasos a continuación para probar las operaciones de la pila.
- Compruebe si la pila está vacía o no utilizando el método is_empty. Debería devolver True.
- Empuje los números 1, 2, 3, 4, 5 en la pila utilizando el método de inserción.
- El método is_empty debería devolver False. Revisalo.
- Imprime el elemento superior usando el método de vista.
- Saca el elemento de la pila usando el método pop.
- Compruebe el elemento de vista. Debería devolver el elemento 4.
- Ahora, saque todos los elementos de la pila.
- El método is_empty debería devolver True. Revisalo.
Nuestra implementación de pila se completa si pasa todos los pasos anteriores. Intente escribir el código para los pasos anteriores.
¿Escribiste el código? No, no te preocupes, revisa el código a continuación.
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
if __name__ == '__main__':
stack = Stack()
## checking is_empty method -> true
print(stack.is_empty())
## pushing the elements
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
## again checking is_empty method -> false
print(stack.is_empty())
## printing the topmost element of the stack -> 5
print(stack.peek())
## popping the topmost element -> 5
stack.pop()
## checking the topmost element using peek method -> 4
print(stack.peek())
## popping all the elements
stack.pop()
stack.pop()
stack.pop()
stack.pop()
## checking the is_empty method for the last time -> true
print(stack.is_empty())
¡Viva! Hemos completado la implementación de la pila desde cero utilizando el tipo de datos de lista. Verá el resultado como se menciona a continuación si ejecuta el código anterior.
True False 5 4 True
Podemos usar directamente el tipo de datos de lista como una pila. La implementación anterior de la pila también lo ayuda a comprender la implementación de la pila en otros lenguajes de programación.
También puede consultar esta lista de artículos relacionados.
Veamos el deque integrado del módulo integrado de colecciones que puede actuar como una pila.
#2. deque de colecciones
Se implementa como una cola de dos extremos. Ya que admite la adición y eliminación de elementos de ambos extremos. Por lo tanto, podemos usarlo como una pila. Podemos hacer que siga el principio LIFO de la pila.
Se implementa utilizando otras estructuras de datos denominadas listas doblemente enlazadas. Entonces, el rendimiento de la inserción y eliminación de elementos es consistente. Acceder a los elementos de la lista enlazada del medio tomó O(n) tiempo. Podemos usarlo como una pila, ya que no es necesario acceder a los elementos intermedios de la pila.
Antes de implementar la pila, veamos los métodos que se usan para implementar la pila usando la cola.
- agregar (datos): se usa para enviar los datos a la pila
- pop(): se usa para eliminar el elemento superior de la pila
No hay métodos alternativos para peek e is_empty. Podemos imprimir toda la pila en lugar del método de vistazo. A continuación, podemos usar el método len para verificar si la pila está vacía o no.
Implementemos la pila usando deque del módulo de colecciones.
from collections import deque ## creating deque object stack = deque() ## checking whether stack is empty or not -> true print(len(stack) == 0) ## pushing the elements stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## again checking whether stack is empty or not -> false print(len(stack) == 0) ## printing the stack print(stack) ## popping the topmost element -> 5 stack.pop() ## printing the stack print(stack) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the whether stack is empty or not for the last time -> true print(len(stack) == 0)
Eso es todo. Hemos aprendido cómo implementar la pila usando el deque del módulo integrado de colecciones. Obtendrá el resultado como se menciona a continuación si ejecuta el programa anterior.
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Hasta ahora, hemos visto dos formas de implementar la pila. ¿Hay otras formas de implementar una pila? ¡Sí! Veamos la forma final de implementar una pila en este tutorial.
#3. LifoQueue
El propio nombre LifoQueue dice que sigue el principio LIFO. Por lo tanto, podemos usarlo como una pila sin ninguna duda. Es de la cola del módulo incorporado. LifoQueue proporciona algunos métodos prácticos que son útiles en la implementación de la pila. vamos a verlos
- put (datos): agrega o empuja los datos a la cola
- get (): elimina o saca el elemento superior de la cola
- vacío () – devuelve si la pila está vacía o no
- qsize() – devuelve la longitud de la cola
Implementemos la pila usando LifoQueue desde el módulo de cola.
from queue import LifoQueue
## creating LifoQueue object
stack = LifoQueue()
## checking whether stack is empty or not -> true
print(stack.empty())
## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
## again checking whether stack is empty or not -> false
print(stack.empty())
## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())
## checking the stack size
print("Size", stack.qsize())
print(stack.get())
print(stack.get())
## checking the whether stack is empty or not for the last time -> true
print(stack.empty())
Obtendrá el resultado mencionado a continuación si ejecuta el programa anterior sin cambiarlo.
True False 5 4 3 Size 2 2 1 True
Aplicación de pila
Ahora, tiene suficiente conocimiento sobre pilas para aplicarlo en problemas de programación. Veamos un problema y resolvámoslo usando una pila.
Dada una expresión, escriba un programa para verificar si los paréntesis, las llaves, las llaves están balanceadas correctamente o no.
Veamos algunos ejemplos.
Aporte: «[{}]([])”
Salida: Equilibrada
Aporte: «{[}]([])”
Salida: no balanceada
Podemos usar la pila para resolver el problema anterior. Veamos los pasos para solucionar el problema.
- Crea una pila para almacenar los caracteres.
- Si la longitud de la expresión es impar, entonces la expresión no está balanceada
- Iterar a través de la expresión dada.
- Si el carácter actual es el corchete de apertura de ( o { o [, then push it to stack.
- Else if the current character is a closing bracket ) or } or ]luego pop de la pila.
- Si el carácter reventado coincide con el paréntesis inicial, continúe; de lo contrario, los paréntesis no están equilibrados.
- Después de la iteración, si la pila está vacía, la ecuación está balanceada; de lo contrario, la ecuación no está balanceada.
Podemos hacer uso del tipo de datos establecido para la verificación de coincidencia de paréntesis.
## stack
class Stack:
def __init__(self):
self.elements = []
def push(self, data):
self.elements.append(data)
return data
def pop(self):
return self.elements.pop()
def peek(self):
return self.elements[-1]
def is_empty(self):
return len(self.elements) == 0
def balance_check(expression):
## checking the length of the expression
if len(expression) % 2 != 0:
## not balanced if the length is odd
return False
## for checking
opening_brackets = set('([{')
pairs = set([ ('(',')'), ('[',']'), ('{','}') ])
## stack initialization
stack = Stack()
## iterating through the given expression
for bracket in expression:
## checking whether the current bracket is opened or not
if bracket in opening_brackets:
## adding to the stack
stack.push(bracket)
else:
## popping out the last bracket from the stack
popped_bracket = stack.pop()
## checking whether popped and current bracket pair
if (popped_bracket, bracket) not in pairs:
return False
return stack.is_empty()
if __name__ == '__main__':
if balance_check('[{}]([])'):
print("Balanced")
else:
print("Not Balanced")
if balance_check('{[}]([])'):
print("Balanced")
else:
print("Not Balanced")
Podemos usar la pila para resolver muchos más problemas. El problema anterior es uno de ellos. Intenta aplicar el concepto de pila donde creas que te conviene más.
Conclusión
¡Sí! Has completado el tutorial. Espero que hayas disfrutado el tutorial tanto como yo mientras lo hago. Eso es todo por el tutorial.
Codificación feliz 🙂 👨💻