Comprender la implementación de pila en Python

Las estructuras de datos juegan un papel clave en el mundo de la programación. Nos ayudan a organizar nuestros datos de manera que se puedan utilizar de manera eficiente. los montón es una de las estructuras de datos más simples.

Aprendamos sobre la pila y su implementación en Python.

What is a Stack?

Una pila es similar a la pila de libros, sillas, etc., en la vida real. Y sigue el Último en entrar / primero en salir (LIFO) principio. 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.

Pila de libros

Cuando queremos el tercer libro de la parte superior, tenemos que quitar los dos primeros libros de la parte superior para sacar el tercer libro. Aquí, el libro superior va último a la pila y es el primero de la pila. La estructura de datos montón sigue el mismo principio Último en entrar / primero en salir (LIFO) en programación.

Operations in Stack

Hay principalmente dos operaciones en una pila

1. empujar (datos)

Agrega o inserta los datos en la pila.

2. pop ()

Elimina o saca el elemento superior de la pila.

Vea las siguientes ilustraciones de empuje y Deliciosos operaciones.

Escribiremos algunas funciones auxiliares que nos ayudarán a obtener más información sobre la pila.

A verlos.

ojeada()

Devuelve el elemento superior de la pila.

esta vacio()

Devuelve si la pila está vacía o no.

Bastantes aspectos conceptuales del montón estructura de datos. Pasemos a la implementación sin más preámbulos.

Supongo que tienes Python instalado en su PC si no, también puede probar el compilador en línea.

Stack Implementation

La implementación de la pila es la más fácil en comparación con otras implementaciones de estructura de datos. Podemos implementar una pila de varias formas en Python.

Veámoslos todos uno por uno.

# 1. Lista

Vamos a implementar el montón usando el -- en una clase. Veamos la implementación paso a paso de la pila.

Step1: Escribe una clase llamada Pila.

class Stack:
	pass

Step2: Tenemos que mantener los datos en una lista. Agreguemos una lista vacía en la clase Stack con nombre elementos.

class Stack:
	def __init__(self):
		self.elements = []

Step3: A empuje los elementos en la pila, necesitamos un método. Escribamos un empuje método que toma datos como argumento y anexar a la elementos lista.

class Stack:
	def __init__(self):
		self.elements = []

	def push(self, data):
		self.elements.append(data)
		return data

Step4: Del mismo modo, escribamos el Deliciosos método que saca el elemento superior de la montón. Podemos usar el Deliciosos método de la -- tipo de datos

class Stack:
	## ...
	def pop(self):
		return self.elements.pop()

Hemos completado la implementación de la pila con las operaciones necesarias. Ahora, agreguemos las funciones auxiliares para obtener más información sobre la pila.

Step5: Podemos obtener el elemento superior de la pila usando el índice negativo. El código <span data-token-index="2" data-reactroot="">element[-1]</span> devuelve el último de la lista. Es el elemento más alto de la pila en nuestro caso.

class Stack:
	## ...

	def peek(self):
		return self.elements[-1]

Step6: Si la longitud del elements la lista 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 usando el -- tipo de datos

Oh! espera, acabamos de implementarlo. Pero, no vi cómo usarlo. ¿Cómo usarlo entonces?

Ven, veamos cómo implementarlo. Tenemos que crear un objeto para el Apilar clase para usarlo. 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 pila.

Compruebe si la pila está vacía o no utilizando el esta vacio método. Debería volver Edición colaborativa.
Empuje los números 1, 2, 3, 4, 5 en la pila usando el empuje método.
La esta vacio el método debería regresar Falso. Revisalo.
Imprima el elemento superior usando el ojeada método.
Saque el elemento de la pila usando el Deliciosos método.
Verifique el elemento de vista previa. Debería devolver el elemento 4.
Ahora, saque todos los elementos de la pila.
La esta vacio el método debería regresar Edición colaborativa. Revisalo.

Nuestra implementación de la 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 usando el -- tipo de datos. Verá la salida como se menciona a continuación si ejecuta el código anterior.

True
False
5
4
True

Podemos usar directamente el -- tipo de datos como montón. La implementación de pila anterior también le ayuda a comprender la implementación de pila en otros lenguajes de programación.

También puede consultar estos artículos relacionados con la lista.

Comprueba si la lista está vacía

Aplanar lista

Convertir lista en diccionario

Veamos el deque incorporado del colecciones módulo incorporado 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 tanto, podemos utilizarlo como montón. Podemos hacer que siga el LIFO principio de la pila.

Se implementa utilizando otras estructuras de datos llamadas doblemente ligado lista. Entonces, el desempeño de la inserción y eliminación de elementos es consistente. Acceder a elementos de la lista de enlaces intermedios tomó O (n) hora. Podemos usarlo como montón 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 el cola.

añadir (datos) - utilizado para enviar los datos a la pila
popular() - utilizado para eliminar el elemento superior de la pila

No existen métodos alternativos para ojeada y esta vacio. Podemos imprimir toda la pila en lugar de ojeada método. A continuación, podemos usar el len método para comprobar si el montón está vacío o no.

Implementemos la pila usando deque del desplegable colecciones módulo.

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. Hemos aprendido a implementar montón usando el deque del desplegable colecciones módulo incorporado. Obtendrá la salida 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? ¡Si! Veamos la forma final de implementar una pila en este tutorial.

# 3. LifoQueue

Su nombre LifoQueue sí mismo dice que sigue el LIFO principio. Por tanto, podemos utilizarlo como montón Sin ninguna duda. Es del módulo incorporado cola. LifoQueue proporciona algunos métodos útiles que son útiles en la implementación de la pila. Vamos a verlos

poner (datos) - agrega o empuja los datos a la cola
get () - elimina o hace estallar 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 del desplegable cola módulo.

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

Application of Stack

Ahora, tiene suficiente conocimiento sobre pilas para aplicarlo en problemas de programación. Veamos un problema y lo resolvemos usando una pila.

Dada una expresión, escriba un programa para comprobar si los paréntesis, llaves y llaves están equilibrados correctamente o no.

Veamos algunos ejemplos.

Entrada: "[{}] ([])"

Salida: Equilibrado

Entrada: "{[}] ([])"

Salida: No equilibrado

Podemos usar la pila para resolver el problema anterior. Veamos los pasos para solucionar el problema.

Crea una pila para almacenar los personajes.
Si la longitud de la expresión es impar, entonces la expresión es No equilibrado
Repite la expresión dada.
- Si el carácter actual es el corchete de apertura de ( o o [, luego empújelo para apilar.
- De lo contrario, si el carácter actual es un corchete de cierre ) o o ], luego salte de la pila.
- Si el carácter emergente coincide con el corchete inicial, continúe; de lo contrario, los corchetes no están equilibrados.
Después de la iteración, si la pila está vacía, la ecuación es Equilibrado si no, la ecuación es No Equilibrado.

Podemos hacer uso del tipo de datos establecido para la verificación de coincidencias entre corchetes.

## 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 el montón para resolver muchos más problemas. El problema anterior es uno de ellos. Intente aplicar el concepto de pila donde crea que le conviene más.

Conclusión

¡Yah! Ha completado el tutorial. Espero que hayas disfrutado del tutorial tanto como yo mientras lo hago. Eso es todo por el tutorial.

Codificación feliz 🙂 👨‍💻