Comprender la implementación de la pila en Python

Las estructuras de datos desempeñan un papel fundamental en el mundo de la programación. Nos ayudan a organizar nuestros datos de forma que puedan utilizarse de manera eficiente. La pila es una de las estructuras de datos más sencillas.

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 principio de último en entrar/primero en salir (LIFO). Es la estructura de datos más sencilla. Veámoslo con un ejemplo del mundo real.

Supongamos que tenemos una pila de libros como la siguiente.

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

Operaciones en la pila

Existen principalmente dos operaciones en una pila

1. push(datos)

Añade o empuja los datos a la pila.

2. pop()

Elimina o hace saltar el elemento situado más arriba de la pila.

Vea a continuación las ilustraciones de las operaciones push y pop.

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

Veámoslas.

mirar()

Devuelve el elemento situado más arriba de la pila.

is_empty()

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.

Asumo que tiene python instalado en su PC si no también puede probar el compilador en línea.

Implementación de la pila

La implementación de la pila es la más sencilla comparada con otras implementaciones de estructuras de datos. Podemos implementar una pila de múltiples maneras en Python.

Veámoslas una a una.

#1. Lista

Vamos a implementar la pila utilizando la lista en una clase. Veamos la implementación paso a paso de la pila.

Paso1: Escribir una clase llamada Pila.

clase Pila:
	pass

Paso2: Tenemos que mantener los datos en una lista. Añadamos una lista vacía en la clase Pila con elementos de nombre.

clase Pila
	def __init__(self):
		self.elementos = []

Paso3: Para empujar los elementos a la pila, necesitamos un método. Escribamos un método push que tome datos como argumento y los añada a la lista de elementos.

clase Pila:
	def __init__(self):
		self.elementos = []

	def push(self, datos):
		self.elements.append(datos)
		devolver datos

Paso4: Del mismo modo, escribamos el método pop que saque el elemento superior de la pila. Podemos utilizar el método pop del tipo de datos lista.

class Pila:
	## ...
	def pop(self):
		return self.elementos.pop()

Hemos completado la implementación de la pila con las operaciones necesarias. Ahora, vamos a añadir las funciones de ayuda para obtener más información sobre la pila.

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

clase Pila:
	## ...

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

Paso6: 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.

clase Pila
	## ...
	def is_empty(self):
		return len(self.elementos) == 0

Hemos terminado de implementar la pila utilizando el tipo de datos lista.

¡Oh! espere acabamos de implementarla. Pero, no hemos visto cómo utilizarla. ¿Cómo utilizarla entonces?

Vamos a ver como implementarlo. Tenemos que crear un objeto para la clase Pila para usarlo. No es gran cosa. Hagámoslo primero.

clase Pila: 
    ## ...

if __name__ == '__main__':
    stack = Stack()

Hemos creado el objeto pila y estamos listos para usarlo. Sigamos los siguientes pasos 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.
Introduzca los números 1, 2, 3, 4, 5 en la pila utilizando el método push .
El método is_empty debería devolver False. Compruébelo.
Imprima el elemento superior utilizando el método peek .
Saque el elemento de la pila utilizando el método pop .
Compruebe el elemento peek. Debería devolver el elemento 4.
Ahora, saque todos los elementos de la pila.
El método is_empty debería devolver True. Compruébelo.

Nuestra implementación de la pila está completa si supera todos los pasos anteriores. Intente escribir el código de los pasos anteriores.

¿Ha escrito el código? No, no se preocupe compruebe el código de abajo.

clase Pila 
    def __init__(self): 
        self.elementos = [] 
    
    def push(self, datos): 
        self.elements.append(datos) 
        devolver datos 
    
    def pop(self): 
        return self.elementos.pop() 
        
    def peek(self): 
        return auto.elementos[-1] 
        
    def is_empty(self): 
        return len(auto.elementos) == 0

if __name__ == '__main__':
    stack = Stack()
    
    ## comprobación del método is_empty -> true
    print(pila.está_vacía())

    ## empujando los elementos
    stack.push(1)
    stack.push(2)
    pila.push(3)
    pila.push(4)
    pila.push(5)

    ## comprobando de nuevo el método is_empty -> false
    print(pila.está_vacía())

    ## imprimiendo el elemento más alto de la pila -> 5
    print(stack.peek())

    ## haciendo saltar el elemento situado más arriba -> 5
    stack.pop()

    ## comprobando el elemento superior mediante el método peek -> 4
    print(stack.peek())

    ## hacer saltar todos los elementos
    stack.pop()
    stack.pop() 
    stack.pop() 
    stack.pop() 

    ## comprobando el método is_empty por última vez -> true
    print(pila.es_vacía())

Hurra! hemos completado la implementación de la pila desde cero utilizando el tipo de datos lista . Si ejecuta el código anterior verá la salida como se indica a continuación.

Verdadero
Falso
5
4
Verdadero

Podemos utilizar directamente el tipo de datos lista como pila. La implementación anterior de la pila le ayudará a comprender también la implementación de la pila en otros lenguajes de programación.

También puede consultar estos artículos relacionados con las listas.

Comprobar si la lista está Vacía

Aplanar lista

Convertir lista en diccionario

Veamos el deque del módulo incorporado collections que puede actuar como una pila.

#2. deque de collections

Se implementa como una cola de doble extremo. Ya que admite la adición y eliminación de elementos desde ambos extremos. Por lo tanto, podemos utilizarlo como una pila. Podemos hacer que siga el principio LIFO de la pila.

Se implementa utilizando otras estructuras de datos denominadas lista doblemente enlazada. Así, el rendimiento de la inserción y eliminación de elementos es coherente. Acceder a los elementos de la lista doblemente enlazada requiere un tiempo O(n) . Podemos utilizarla como pila , ya que no es necesario acceder a los elementos intermedios desde la pila.

Antes de implementar la pila, veamos los métodos que se utilizan para implementar la pila utilizando la cola.

append(datos) – se utiliza para empujar los datos a la pila
pop() – se utiliza 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 peek . A continuación, podemos utilizar el método len para comprobar si la pila está vacía o no.

Implementemos la pila utilizando deque del módulo collections .

from colecciones import deque

## crear objeto deque
pila = deque()

## comprobar si la pila está vacía o no -> true
print(len(pila) == 0)

## empujar los elementos
stack.append(1)
stack.append(2)
pila.append(3)
pila.append(4)
stack.append(5)

## de nuevo comprobando si la pila está vacía o no -> false
print(len(stack) == 0)

## imprimiendo la pila
print(pila)

## saltando el elemento superior -> 5
stack.pop()

## imprimiendo la pila
print(pila)

## vaciar todos los elementos
pila.pop()
pila.pop() 
stack.pop() 
stack.pop() 

## comprobación de si la pila está vacía o no por última vez -> true
print(len(stack) == 0)

Eso es todo. Hemos aprendido a implementar stack utilizando el deque del módulo incorporado collections . Obtendrá la salida que se menciona a continuación si ejecuta el programa anterior.

Verdadero
Falso
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
Verdadero

Hasta ahora, hemos visto dos formas de implementar la pila. ¿Existen otras formas de implementar una pila? Sí Veamos la última forma de implementar una pila en este tutorial.

#3. LifoQueue

El propio nombre LifoQueue dice que sigue el principio LIFO . De ahí que podamos utilizarla como una pila sin ninguna duda. Procede del módulo incorporado queue. LifoQueue proporciona algunos métodos útiles para la implementación de la pila. Veámoslos

put(data ) – añade o empuja los datos a la cola
get () – elimina o saca el elemento superior de la cola
empty () – devuelve si la pila está vacía o no
qsize () – devuelve la longitud de la cola

Implementemos la pila utilizando LifoQueue del módulo de colas.

from cola import LifoQueue

## crear objeto LifoQueue
pila = LifoQueue()

## comprobar si la pila está vacía o no -> true
print(stack.empty())

## empujar los elementos
stack.put(1)
stack.put(2)
pila.put(3)
pila.put(4)
pila.put(5)

## de nuevo comprobando si la pila está vacía o no -> false
print(pila.vacía())

## sacar todos los elementos
print(pila.obtener())
print(stack.get())
print(pila.obtener())

## comprobar el tamaño de la pila
print("Tamaño", stack.qsize())

print(pila.obtener())
print(pila.obtener())

## comprobar si la pila está vacía o no por última vez -> true
print(stack.empty())

Obtendrá la salida mencionada a continuación si ejecuta el programa anterior sin modificarlo.

Verdadero
Falso
5
4
3
Talla 2
2
1
Verdadero

Aplicación de la pila

Ahora ya tiene suficientes conocimientos sobre las pilas para aplicarlos en problemas de programación. Veamos un problema y resolvámoslo utilizando una pila.

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

Veamos algunos ejemplos.

Entrada: «[{}]([])»

Salida: Equilibrado

Entrada «{[}]([])»

Salida: No equilibrada

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

Cree una pila para almacenar los caracteres.
Si la longitud de la expresión es impar, entonces la expresión no está equilibrada
Itere a través de la expresión dada.
- Si el carácter actual es el corchete de apertura de ( o{ o [, entonces empújelo a la pila.
- Si el carácter actual es un corchete de cierre ) o } o ], entonces sáquelo de la pila.
- Si el carácter saltado coincide con el corchete de inicio, entonces continúe, de lo contrario los corchetes no se equilibran.
Después de la iteración, si la pila está vacía entonces la ecuación está Equilibrada de lo contrario la ecuación no está Equilibrada.

Podemos hacer uso del tipo de datos conjunto para la comprobación de coincidencia de corchetes.

## pila
clase Pila 
    def __init__(self): 
        self.elementos = [] 
    
    def push(self, datos): 
        self.elements.append(datos) 
        devolver datos 
        
    def pop(self): 
        return self.elementos.pop() 
    
    def peek(self): 
        return auto.elementos[-1] 
        
    def is_empty(self): 
        return len(auto.elementos) == 0

def balance_check(expression):
    ## comprobar la longitud de la expresión
    if len(expresión) % 2 != 0:
        ## no se equilibra si la longitud es impar
        return False
    
    ## para comprobar
    paréntesis_de_apertura = set('([{') 
    pares = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## inicialización de la pila
    pila = Pila()
    
    ## iterar a través de la expresión dada
    para corchete en expresión

        ## comprobar si el corchete actual está abierto o no  
        if corchete en abriendo_corchetes
            ## añadir a la pila 
            stack.push(corchete)
        else:
            ## sacar el último corchete de la pila
            corchete_de_apertura = pila.pop()
        
            ## comprobar si el corchete saltado y el actual están emparejados
            if (popped_bracket, bracket) not in pairs:
                return False
    
    return pila.está_vacía()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("Equilibrado")
    si no
        print("No equilibrado")
    
    si balance_check('{[}]([])'):
        print("Equilibrada")
    si no
        print("No equilibrado")

Podemos utilizar la pila para resolver muchos más problemas. El problema anterior es uno de ellos. Intente aplicar el concepto de pila donde mejor le parezca.

Conclusión

Ya está Ha completado el tutorial. Espero que haya disfrutado del tutorial tanto como yo mientras lo hacía. Eso es todo para el tutorial.

Feliz Codificación 🙂 👨‍💻

Hafeezul Kareem Shaik
Colaborador
- LinkedIn
Hafeez es desarrollador y disfruta compartiendo sus conocimientos sobre Python y los lenguajes de desarrollo emergentes.