Stacks en Python
Contenido del curso
Día 1
Día 2
Día 3
Día 4
Día 5
Día 6
Día 7
Día 8
Día 9
Día 10
Día 11
Día 12
Día 13
Día 14
Día 15
Día 16
Día 17
Día 18
Día 19
Día 20
Día 21
Stacks en Python
Contenido del curso
Stacks en Python
Un stack (o pila) es una estructura de datos lineal que sigue el principio "último en entrar, primero en salir" (Last In, First Out, LIFO). Esto significa que el último elemento agregado al stack será el primero en ser eliminado. En Python, podemos implementar un stack utilizando listas.
Complejidad Algorítmica
La complejidad de los métodos de un stack en Python depende de la implementación utilizada. Si se utiliza una lista, la complejidad es la siguiente:
| Algoritmo | Notación Big O |
|---|---|
| Agregar un elemento (push) | O(1) |
| Eliminar un elemento (pop) | O(1) |
| Acceder al último elemento | O(1) |
| Acceder a un elemento en una posición específica | O(1) |
En general, utilizar listas para implementar un stack en Python es una opción eficiente, ya que ofrece un buen rendimiento para todas las operaciones.
Construyamos un Stack en Python
A continuación, implementaremos un stack en Python utilizando una clase y aprovechando la estructura de lista nativa de Python.
class Node: def __init__(self, value): self.value = value self.next = None class Stack: def __init__(self): self.top = None self.bottom = None self.length = 0 def push(self, value): new_node = Node(value) if self.length == 0: self.top = new_node self.bottom = new_node else: new_node.next = self.top self.top = new_node self.length += 1 def pop(self): if not self.top: return None if self.top == self.bottom: self.bottom = None popped_node = self.top self.top = self.top.next self.length -= 1 return popped_node.value def peek(self): return self.top.value if self.top else None def is_empty(self): return self.length == 0
En esta implementación, hemos creado la clase Node que representa un nodo en el stack, y la clase Stack que implementa el stack en sí.
La clase Node tiene un constructor que inicializa el nodo con un valor y establece next como None.
La clase Stack tiene un constructor que inicializa el stack con top, bottom y length establecidos como None, None y 0, respectivamente.
Los métodos implementados en la clase Stack son los siguientes:
push: Agrega un nuevo nodo en la parte superior del stack. Si el stack está vacío, asigna el nuevo nodo tanto a top como a bottom. En caso contrario, hace que new_node.next apunte al nodo actual en la parte superior del stack, actualiza top para que apunte al nuevo nodo y aumenta length en 1.pop: Elimina y devuelve el valor del nodo en la parte superior del stack. Si el stack está vacío, devuelve None. Si top y bottom son iguales, se establece bottom en None. Guarda el nodo en la parte superior en la variable popped_node, actualiza top para que apunte al siguiente nodo en el stack, disminuye length en 1 y devuelve el valor de popped_node.peek: Devuelve el valor del nodo en la parte superior del stack sin eliminarlo. Si el stack está vacío, devuelve None.is_empty: Verifica si el stack está vacío comprobando si length es igual a 0.Oportunidades donde puedes usar un Stack
El stack es una estructura de datos muy versátil que puede utilizarse en diversas situaciones. Algunas oportunidades donde es conveniente utilizar un stack en Python incluyen:
Es importante tener en cuenta las características del stack y elegir la estructura de datos adecuada según los requisitos específicos del problema.
En resumen, hemos aprendido cómo implementar un stack en Python utilizando listas y una clase. También hemos explorado las oportunidades en las que un stack puede ser útil y la complejidad algorítmica de los métodos implementados.
Jhon Freddy Tavera Blandon
Estudiante
Waldir Zapata Garcia
Estudiante
Nicolas Alpargatero
EstudianteEjemplos reales de cómo utilizar este Stack:
# Crear un Stack vacío stack = Stack() # Agregar elementos al Stack stack.push(10) stack.push(20) stack.push(30) # Obtener el elemento del top del Stack print(stack.peek()) # Output: 30 # Eliminar elementos del Stack stack.pop() print(stack.peek()) # Output: 20 # Verificar si el Stack está vacío print(stack.is_empty()) # Output: False # Obtener el tamaño del Stack print(stack.size()) # Output: 2 # Vaciar el Stack stack.pop() stack.pop() print(stack.is_empty()) # Output: True # Intentar hacer pop en un Stack vacío (lanzará una excepción IndexError) # stack.pop()
it's ok stack
Para profundizar y hacer más retos implementando Staks https://platzi.com/clases/4593-algoritmos-avanzados-lineales/57034-estructura-de-datos-pilas-y-colas/