Contenido del curso
Implementación de una Pila con Nodos en Python
Implementar una pila o stack en Python usando nodos es una de las formas más elegantes de comprender cómo funciona esta estructura de datos dinámica. A continuación se desglosa paso a paso cómo construirla, qué métodos esenciales necesita y cuándo conviene usar nodos en lugar de arrays.
¿Cómo se inicializa un stack con nodos en Python?
El primer paso es crear un archivo llamado stack.py e importar la clase Node [00:21]. La clase Stack se define con un método constructor que establece dos atributos fundamentales:
None porque el stack comienza vacío.Esto convierte al stack en una estructura de datos dinámica, capaz de crecer o decrecer conforme se agregan o retiran elementos [00:40].
python class Stack: def init(self): self.top = None self.size = 0
¿Qué hacen los métodos push, pop, peek y clear?
¿Cómo agregar elementos con push?
El método push recibe un dato, crea un nodo y lo coloca en la cima del stack [01:02]. Si ya existe un elemento en self.top, el nuevo nodo apunta hacia él mediante next. Después, self.top se actualiza al nodo recién creado y el tamaño incrementa en uno.
python def push(self, data): node = Node(data) if self.top: node.next = self.top self.top = node self.size += 1
¿Cómo remover elementos con pop?
El método pop retira el elemento que está hasta arriba del stack y retorna su valor [01:42]. Primero verifica que exista un elemento en self.top. Si lo hay, guarda el dato, decrementa el tamaño y reposiciona self.top hacia el siguiente nodo. Cuando no queda ningún nodo después, self.top se vuelve None.
python def pop(self): if self.top: data = self.top.data self.size -= 1 if self.top.next: self.top = self.top.next else: self.top = None return data else: print("El stack está vacío")
Aquí se aplica el principio LIFO (last in, first out): el último elemento en entrar es el primero en salir [03:38].
¿Cómo consultar la cima con peek?
El método peek simplemente retorna el dato del elemento que está en la cima sin removerlo [02:34]. Si el stack está vacío, muestra un mensaje indicándolo.
python def peek(self): if self.top: return self.top.data else: print("El stack está vacío")
¿Cómo vaciar el stack con clear?
El método clear utiliza un ciclo while que llama repetidamente a pop mientras exista un elemento en self.top [02:55]. De esta forma se eliminan todos los nodos de manera iterativa.
python def clear(self): while self.top: self.pop()
¿Cuándo usar nodos y cuándo usar arrays para un stack?
Durante la prueba en terminal se agregaron tres elementos: egg, ham y spam usando push [03:12]. Al llamar a pop, salió spam primero porque fue el último en entrar, confirmando el comportamiento LIFO.
La diferencia entre implementar un stack con nodos o con arrays tiene implicaciones prácticas [04:30]:
Sin embargo, al igual que con las linked lists, agregar muchos nodos incrementa la complejidad del código [04:40].
El reto propuesto consiste en añadir métodos para buscar un elemento en particular, crear un iterador que recorra el stack, implementar clear de una forma diferente, y finalmente construir una segunda clase stack basada en arrays con herencia, aplicando la misma lógica pero trabajando con índices [05:05]. ¿Se te ocurre otra forma de vaciar un stack sin usar pop repetidamente? Compártelo en los comentarios.
Christian Molina Vázquez
Estudiante
Miguel Angel Reyes Moreno
Estudiante
Armando José Arenas Sánchez
Estudiante
Héctor Daniel Vega Quiñones
Profesor
Manuel G. Pineda
Estudiante
Luis Eduardo Lerena Pereira
Estudiante
Mauricio Gonzalez Falcon
Estudiante
Jose Noriega
Estudiante
Junior Peves
Estudiante
Ricardo Torres
Estudiante
Jonathan Osorio
Estudiante
David Rosas
Estudiante
Roger Christian Cansaya Olazabal
Estudiante
José Martínez Santana
Estudiante
Andres Cueto Estrada
Estudiante
Eduardo Kiriakos Piazza
Estudiante
Oscar Eduardo Barrios Blanco
EstudianteOscar Eduardo Barrios Blanco
EstudianteChristian Molina Vázquez
Estudiante
Carlos Eduardo Gomez García
ProfesorChristian Molina Vázquez
Estudiante
Oscar Rogelio Heredia Ruiz
EstudianteOscar Rogelio Heredia Ruiz
Estudiante
Jonnatan Pereira Betancur
Estudiante
Rigoberto Maldonado
Estudiante
Andres Montes
EstudianteReto 2
class Array: def __init__(self, capacity, fill_value=None): self.items = list() for _ in range(capacity): self.items.append(fill_value) def __len__(self): return len(self.items) def __str__(self): return str(self.items) def __iter__(self): return iter(self.items) def __getitem__(self, index): return self.items[index] def __setitem__(self, index, new_item): self.items[index] = new_item class StackArray(Array): def __init__(self, capacity, fill_value=None): super().__init__(capacity, fill_value) self.capacity = capacity self.top = None self.size = 0 def __str__(self): result = '' if self.size <= 0: return 'Stack empty' for i in self.items: if i != None: result += f'{i} ' return result def push(self, data): if self.size == self.capacity: print('Stack full') return -1 for i, value in enumerate(self.items): if value == None: self.items[i] = data self.top = data self.size += 1 break def pop(self): for i in range(self.capacity-1, -1, -1): if self.items[i] != None: self.items[i] = None self.size -= 1 if i > 0: self.top = self.items[i-1] else: self.top = None break def peek(self): if self.top: return self.top else: return "The stack is empty" def clear(self): self.__init__(self.capacity) def search(self, target_item): if self.size <= 0: print("The stack is empty") else: if target_item in self.items: print(f'Target item {target_item} has been found') return self.items.index(target_item) else: print(f'Target item {target_item} is not in stack') return -1 def iter(self): for element in self.items: if element != None: yield element
from node import Node class Stack: def __init__(self): self.top = None self.size = 0 def push(self, data): node = Node(data, self.top) if self.top: node.next = self.top self.top = node else: self.top = node self.size += 1 def pop(self): if self.top: data = self.top.data self.size -= 1 if self.top.next: self.top = self.top.next else: self.top = None return data else: return ("The stack is empty") def peek(self): return self.top.data if self.top else ("The stack is empty") def clear(self): while self.top: self.pop() def search_element(self, data): if self.top: current = self.top while current: if current.data == data: return (f'Elemet {data} founded') current = current.next return (f'Elemet {data} not founded')
Para el método clear no quedaría más corto simplemente quitar el valor de self.top y poner el tamaño de la lista en cero o hay algo que me estoy saltando?
def clear(self): self.top=None self.size=0
Es una opción totalmente válida, lo importante es que hayas pensado en esa alternativa ;)
También pense en esta posibilidad. Borrando la referencia de self.top. Supongo que posteriormente el garbage collector elimina los nodos.
Reto 1: Clase:
import gc from node import Node class Stack: def __init__(self) -> None: self.top = None self.size = 0 self.__current__ = None def __iter__(self): self.__current__ = self.top return self def __next__(self): if not self.__current__: raise StopIteration else: next_node = self.__current__ self.__current__ = next_node.next return next_node def push(self, data): node = Node(data) if self.top: node.next = self.top self.top = node self.size += 1 def pop(self): return_data = 'Empty stack' if self.top: return_data = self.top.data self.top = self.top.next self.size -= 1 return return_data def add(self, stack2): if len(stack2) > 0: for node2 in stack2: self.push(node2.data) else: print(f'Parameter stack is empty') def __contains__(self, data): if self.size > 0: return_node = self.top while return_node and return_node.data != data: return_node = return_node.next return return_node def clear(self): self.size = 0 self.top = None gc.collect() def peek(self): return_data = 'Empty stack' if self.top: return_data = self.top.data return return_data def __len__(self): return self.size def __str__(self): node = self.top position = 1 return_str = '(\r\n' while(node): return_str += f'\tPosition {position} - dato {node.data}' position += 1 node = node.next return_str += '\r\n)' return return_str
Aplicación:
from mi_stack import Stack def run(): stack = Stack() stack.push('A') stack.push('B') stack.push('C') stack.push('D') show_stack(stack) print(stack.pop()) print(stack.pop()) show_stack(stack) stack2 = Stack() stack2.push('X') stack2.push('Y') stack2.push('Z') stack.add(stack2) show_stack(stack) stack.clear() show_stack(stack) def show_stack(stack): print('=======================') position = 1 for node in stack: print(f'Position {position} dato {node.data}') position += 1 if __name__ == '__main__': run()
También pensé en el Garbange collector, pero no sabía como llamarlo.
Muchas Gracias!
Reto
Código
Stack con nodos
from typing import Optional, Union from typing import Iterable from node import Node class Stack: """A simple stack implementation.""" _size: int _top: Optional[Node] def __init__(self, *items): """Initializes the stack.""" self._top = None self._size = 0 if len(items) > 0 and isinstance(items[0], Iterable): items = items[0] for item in items: self.push(item) def is_empty(self): """Checks if the stack is empty. Returns: bool: True if the stack is empty, False otherwise. """ return self._size <= 0 def clear(self): """Clears the stack.""" self._top = None self._size = 0 def copy(self): """Returns a copy of the stack. Caution: This method returns a shallow copy. Returns: Stack: A copy of the stack. """ new_stack = Stack() new_stack._top = self._top return new_stack def depthcopy(self): """Returns a deep copy of the stack. Returns: Stack: A deep copy of the stack. """ new_stack = Stack() new_stack._top = self._top.depthcopy() new_stack._size = self._size return new_stack def extend(self, other: 'Stack'): """Extends the current stack with the items of the other stack. Time complexity: O(n) where n is the length of the other stack. Args: other: The other stack to extend the current stack with. """ if other._top is None: return None bottom_node = other._top while bottom_node.next is not None: bottom_node = bottom_node.next bottom_node.next = self._top self._top = other._top self._size += other._size return None def peek(self, raw: bool = False) -> Union[None, Node, object]: """Returns the top item of the stack. Raises IndexError if the stack is empty. Args: raw: If True returns the Node, otherwise it will return the node value. Returns: object: The top item of the stack. """ if not self._top: raise IndexError('The stack is empty.') if raw: return self._top return self._top.value def push(self, value: object): """Pushes an item onto the stack. Time complexity: O(1) Args: item: The item to be pushed onto the stack. """ self._top = Node(value, self._top) self._size += 1 def pop(self, raw: bool = False): """Pops an item off the stack. Raises IndexError if the stack is empty. Time complexity: O(1) Args: raw: If True returns the Node, otherwise it will return the node value. Returns: object: The item that was popped off the stack. """ if self._top is None: raise IndexError('The stack is empty.') temp = self._top self._top = temp.next self._size -= 1 if raw: return temp return temp.value def __len__(self): """Returns the length of the stack. Time complexity: O(1) Returns: int: The length of the stack. """ return self._size def __str__(self) -> str: """Returns a string representation of the stack. Time complexity: O(n) Space complexity: O(n) Returns: str: A string representation of the stack. """ items = list(self) return str(items) def __contains__(self, item: object) -> bool: """Checks if the stack contains an item. Args: item: The item to check if the stack contains. Returns: bool: True if the stack contains the item, False otherwise. """ pointer = self._top while pointer is not None: if pointer.value == item: return True pointer = pointer.next return False def itervalues(self) -> Iterable: """Returns an iterator over the values of the stack. Returns: iterator: An iterator over the values of the stack. """ pointer = self._top while pointer is not None: yield pointer pointer = pointer.next def __iter__(self) -> Iterable: """Returns an iterator over the stack. Returns: iterator: An iterator over the stack. """ return self.itervalues() def __add__(self, other): """Returns a new stack containing the items of both stacks. Args: other: The other stack to add to the current stack. Returns: Stack: A new stack containing the items of both stacks. """ new_stack = self.depthcopy() new_stack.extend(other.depthcopy()) return new_stack
Stack con listas
from typing import Optional, Union from typing import Iterable class Stack: """A simple stack implementation with list.""" _items: list def __init__(self, *items): self._items = list(*items) def is_empty(self) -> bool: return len(self._items) == 0 def clear(self) -> None: self._items.clear() def copy(self) -> 'Stack': stack = Stack() for item in self._items: stack.push(item) return stack def extend(self, other: Iterable) -> None: for item in reversed(other): self.push(item) def peek(self) -> Optional[object]: if self.is_empty(): raise ValueError('Stack is empty.') return self._items[-1] def pop(self) -> Optional[object]: return self._items.pop() def push(self, item: object) -> None: self._items.append(item) def itervalues(self) -> Iterable: return reversed(self._items) def __len__(self) -> int: return len(self._items) def __str__(self) -> str: return str(self._items) def __contains__(self, item: object) -> bool: return item in self._items def __iter__(self) -> Iterable: return self.itervalues() def __repr__(self) -> str: return f'Stack({self._items})' def __reversed__(self) -> Iterable: return self._items def __add__(self, other: Union['Stack', Iterable]) -> 'Stack': stack = self.copy() if isinstance(other, Stack): stack.extend(other) else: stack.extend(other) return stack
Pruebas unitarias
Stack con nodos
# Unitest import unittest # Utils from stack_with_node import Stack class StackWithNodeTestCase(unittest.TestCase): """Stack test cases.""" def test_empty_instantiation(self): """Test instantiation of an empty stack.""" stack = Stack() self.assertEqual(len(stack), 0) def test_instantiation_with_items(self): """Test instantiation of a stack with items.""" stack = Stack(['a', 'b', 'c']) self.assertEqual(len(stack), 3) def test_is_empty(self): """Test is_empty method.""" stack = Stack() self.assertTrue(stack.is_empty()) def test_is_not_empty(self): """Test is_empty method.""" stack = Stack(['a', 'b', 'c']) self.assertFalse(stack.is_empty()) def test_push(self): """Test push method.""" stack = Stack() stack.push('a') self.assertEqual(len(stack), 1) def test_peek(self): """Test peek method.""" stack = Stack(['a', 'b', 'c']) self.assertEqual(stack.peek(), 'c') def test_pop(self): """Test pop method.""" stack = Stack(['a', 'b', 'c']) self.assertEqual(stack.pop(), 'c') self.assertEqual(len(stack), 2) for a, b in zip(stack, ['b', 'a']): self.assertEqual(a, b) def test_pop_empty(self): """Test pop method.""" stack = Stack() self.assertRaises(IndexError, stack.pop) def test_copy(self): """Test copy method.""" stack = Stack(['a', 'b', 'c']) stack_copy = stack.copy() self.assertIsNot(stack_copy, stack) def test_depthcopy(self): """test depthcopy method.""" stack_1 = Stack([1, 2, 3]) stack_2 = stack_1.depthcopy() self.assertEqual(len(stack_2), len(stack_1)) for a, b in zip(stack_1, stack_2): self.assertIsNot(a, b) def test_iter(self): """Test iter method.""" stack = Stack(['a', 'b', 'c']) self.assertEqual(list(stack), ['c', 'b', 'a']) def test_extend(self): """Test extends method.""" stack_1 = Stack([1, 2, 3]) stack_2 = Stack([4, 5, 6]) stack_1.extend(stack_2) self.assertEqual(len(stack_1), 6) for a, b in zip(stack_1, [6, 5, 4, 3, 2, 1]): self.assertEqual(a, b) def test_add_operator(self): """Test add operator.""" stack_1 = Stack([1, 2, 3]) stack_2 = Stack([4, 5, 6]) stack_3 = stack_1 + stack_2 self.assertEqual(len(stack_3), 6) for a, b in zip(stack_3, [6, 5, 4, 3, 2, 1]): self.assertEqual(a, b)
Stack con listas
# Unitest import unittest # Utils from stack_with_array import Stack class StackWithNodeTestCase(unittest.TestCase): """Stack test cases.""" def test_empty_instantiation(self): """Test instantiation of an empty stack.""" stack = Stack() self.assertEqual(len(stack), 0) def test_instantiation_with_items(self): """Test instantiation of a stack with items.""" stack = Stack(['a', 'b', 'c']) self.assertEqual(len(stack), 3) def test_is_empty(self): """Test is_empty method.""" stack = Stack() self.assertTrue(stack.is_empty()) def test_is_not_empty(self): """Test is_empty method.""" stack = Stack(['a', 'b', 'c']) self.assertFalse(stack.is_empty()) def test_push(self): """Test push method.""" stack = Stack() stack.push('a') self.assertEqual(len(stack), 1) def test_push_multiple(self): """Test push method.""" stack = Stack() stack.push('a') stack.push('b') stack.push('c') self.assertEqual(len(stack), 3) for a, b in zip(stack, ['c', 'b', 'a']): self.assertEqual(a, b) def test_peek(self): """Test peek method.""" stack = Stack(['a', 'b', 'c']) self.assertEqual(stack.peek(), 'c') def test_pop(self): """Test pop method.""" stack = Stack(['a', 'b', 'c']) self.assertEqual(stack.pop(), 'c') self.assertEqual(len(stack), 2) for a, b in zip(stack, ['b', 'a']): self.assertEqual(a, b) def test_pop_empty(self): """Test pop method.""" stack = Stack() self.assertRaises(IndexError, stack.pop) def test_copy(self): """Test copy method.""" stack = Stack(['a', 'b', 'c']) stack_copy = stack.copy() self.assertIsNot(stack_copy, stack) def test_iter(self): """Test iter method.""" stack = Stack(['a', 'b', 'c']) self.assertEqual(list(stack), ['c', 'b', 'a']) def test_extend(self): """Test extends method.""" stack_1 = Stack([1, 2, 3]) stack_2 = Stack([4, 5, 6]) stack_1.extend(stack_2) self.assertEqual(len(stack_1), 6) for a, b in zip(stack_1, [6, 5, 4, 3, 2, 1]): self.assertEqual(a, b) def test_add_operator(self): """Test add operator.""" stack_1 = Stack([1, 2, 3]) stack_2 = Stack([4, 5, 6]) stack_3 = stack_1 + stack_2 self.assertEqual(len(stack_3), 6) for a, b in zip(stack_3, [6, 5, 4, 3, 2, 1]): self.assertEqual(a, b)
Reto 2:
Tengo una duda que no me termina de quedar clara. En que ocasiones o que casos de uso tienen este tipo de estructuras de datos. Hasta el momento hemos visto nodos y stacks pero no me termina de quedar claro cunado seria util implentar cada uno o ambos
Reto 1
from nodes import Node class Stack(): def __init__(self): self.top = None #Top or Head self.size = 0 def push(self, data): ##other way to push """Add an element in top""" node = Node(data) if self.top: node.next = self.top self.top = node else: self.top = node self.size += 1 def pop(self, data): """Remove element on top and returns data""" if self.top: data = self.top.data self.size -= 1 if self.top.next: self.top = self.top.next else: self.top = None return data else: return 'The stack is empty' def peek(self): """Returns top element in stack""" if self.top: return self.top.data else: return 'The stack is empty' def clear(self): """Erase all data from stack""" while self.top: self.pop() return 'The stack now is empty' def iter(self): """Create a stack iterator""" while self.top: value = self.top.data self.top = self.top.next yield value def search(self, data): count = 0 for node in self.iter(): count += 1 if data == node: print (f'Data {data} found!') break elif count == self.size: print ('Data not found!') def printList(self): current = self.top print('Data in Single Linked List:', end='\n') while current is not None: print(current.data, end=" ") current = current.next print('') if __name__ == '__main__': stack = Stack() for i in range(6,0,-1): stack.push(i) stack.search(6) stack.pop() stack.peek() stack.printList()
Reto 2, utilice herencia y agregación
from class_array import Array from stack import Stack class stackFromArray(Stack): def __init__(self, data=Array(1)): super().__init__() for i in data: self.push(i) if __name__ == '__main__': s = stackFromArray(Array(3)) s.printList()
Gracias!
Paso a pasito:
El reto #1
El reto #2
Para simplificar la clase realizé el Stack usando nuestro anterior Double Linked List como padre.
Les dejo el código en github.
Considero que nos permite concentrarnos un poco más en entender el tipo de dato que en reinventar los métodos usados anteriormente.
Segundo reto completado!
class ArrayStack(Array): def __init__(self, capacity, fill_value=None): Array.__init__(self, capacity, fill_value) self.top_index = self.__len__() - 1 self.size = 0 def iter(self): for elm in filter(lambda x: x != None, self.items): yield elm def push(self, data): if self.top_index == 0: print("The stack is full") else: if not self.items[self.top_index]: self.items[self.top_index] = data else: self.top_index -= 1 self.items[self.top_index] = data self.size += 1 def pop(self): if self.size > 0: val = self.items[self.top_index] self.items[self.top_index] = None self.top_index += 1 self.size -= 1 return val else: return "The stack is empty"
Stacks basados en Arrays usando la Clase anterior Array
from array_1 import Array class Stack(Array): def __init__(self, capacity = 10): super().__init__(capacity, fill_value=None) self.size = 0 #El array empieza vacío self.capacity = capacity def push(self, data): #Define la capacidad del array if self.size < self.capacity: #Reemplazamos el None con el dato a ingresar self.items[self.size] = data #Movemos el tope lógico para que la siguiente vez, reemplazamos la siguiente posición self.size += 1 else: return 'El Stack está lleno' def pop(self): if self.size == 0: return 'El stack está vacío' else: self.size -= 1 data = self.items[self.size] self.items[self.size] = None return data def peek(self): if self.size == 0: return 'El stack está vacío' else: last = self.size - 1 return self.items[last] def clear (self): for i in range (self.capacity): self.items[i] = None self.size = 0 self.items[self.size] = data #Movemos el tope lógico para que la siguiente vez, reemplazamos la siguiente posición self.size += 1 else: return 'El Stack está lleno' def pop(self): #al ser un stack e ir llenando desde index 0, si ese indice está vacío, todo el stack debería estar vacío if self.size == 0: return 'El stack está vacío' else: self.size -= 1 data = self.items[self.size] self.items[self.size] = None return data def peek(self): if self.size == 0: return 'El stack está vacío' else: last = self.size - 1 return self.items[last] def clear (self): for i in range (self.capacity): self.items[i] = None self.size = 0
Reto 1
from node import Node class Stack: def __init__(self): self.top = None self.size = 0 def search(self, data): prop = self.top while prop: if prop.data == data: return prop.data else: prop = prop.next return 'The stack is empty' def Walker(self): prop = self.top while prop: yield prop #Si pongo un return aca la funcion para? print (prop.data) prop = prop.next def clear (self): self.top = None
Envie dos comentarios para compartir mi solución a los retos y me apareció que estaban en revisión, porque sucede eso??
¡Hola! Es porque tal vez tu comentario tiene enlaces a sitios no seguros o contiene alguna palabra no admitida 🤔 ¿Puedes subir una captura de lo que intentabas enviar?
Creo que era por qué era muy largo, no le veo otra razón solo eran los dos comentarios que ya subi de la solución de los retos
Reto 1.- Buscar un elemento
def search_element(self, data): current = self.top while current: if current.data == data: return "Element found" else: current = current.next return "Element not found
Reto 1.- Retornar elementos
def list_elements(self): while self.top: print(self.top.data) self.top = self.top.next return "The stack is empty"
def clear(self): self.__init__()
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements can be added (pushed) and remove (popped) only from the top of the stack.
...
Good reselts.
reto de los metodos del stack
