Clase 17 de 23 • Curso de Estructuras de Datos Lineales con Python
Contenido del curso
Christian Molina Vázquez
Miguel Angel Reyes Moreno
Armando José Arenas Sánchez
Héctor Daniel Vega Quiñones
Manuel G. Pineda
Luis Eduardo Lerena Pereira
Mauricio Gonzalez Falcon
Jose Noriega
Junior Peves
Ricardo Torres
Jonathan Osorio
David Rosas
Roger Christian Cansaya Olazabal
José Martínez Santana
Andres Cueto Estrada
Eduardo Kiriakos Piazza
Oscar Eduardo Barrios Blanco
Oscar Eduardo Barrios Blanco
Christian Molina Vázquez
Carlos Eduardo Gomez García
Christian Molina Vázquez
Oscar Rogelio Heredia Ruiz
Oscar Rogelio Heredia Ruiz
Jonnatan Pereira Betancur
Rigoberto Maldonado
Andres Montes
Reto 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
