• ¡Obtenga la seguridad de la aplicación de la manera correcta! Detectar, proteger, monitorear, acelerar y más ...
  • 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.

    ¿Qué es una pila?

    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.

    Operaciones en pila

    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.

    Implementación de pila

    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 lista 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 lista 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 element[-1] 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 lista 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 Verdadero.
    • 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 Verdadero. 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 lista 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 lista 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.

    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 from the 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 from the 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. El 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 from the 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

    Aplicación de 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 🙂 👨‍💻