Clase 19 de 23 • Curso de Estructuras de Datos Lineales con Python
Contenido del curso
Christian Molina Vázquez
Alexis Dorado Muñoz
Christian Molina Vázquez
Michelle Duque De La Rosa
Fabián Aravena Silva
José Isidro Torres Caldea
Mauricio Gonzalez Falcon
Romel Manrique
Valentin Francisco Blanco
Héctor Daniel Vega Quiñones
Juan Antonio Aramburo Pasapera
Pablo Joaquín Cruz
Jhon Freddy Tavera Blandon
Alexis Dorado Muñoz
Juan Antonio Aramburo Pasapera
Lucas Yañez
Jose Noriega
Jose Noriega
Elvis Ronald Cruz Chullo
José Joaquín Tripp Gudiño
Oscar Rogelio Heredia Ruiz
Rigoberto Maldonado
Andrés Cardona
iecgerman .
iecgerman .
Nicolas Alpargatero
Dante Rodrigo Méndez Pérez
Lucas Yañez
Luis Santiago jaramillo espinosa
Para obtener el tamaño, simplemente aplicaría la función len() a la lista self.items.
self.size = len(self.items)
Muchas gracias por tu aporte.
El código de la clase
class ListQueue: def __init__(self): self.items = [] self.size = 0 def enqueue(self,data): self.items.insert(0,data) self.size += 1 def dequeue(self): data = self.items.pop() self.size -= 1 return data def traverse(self): total_items = self.size for item in range(total_items): print(self.items[item])
from list_based_queue import ListQueue food = ListQueue() food.enqueue('eggs') food.enqueue('ham') food.enqueue('spam') print(food.dequeue()) food.traverse()
eggs spam ham
Gracias
Opinion: Me confunde un poco el que inserte un nuevo valor en el índice 0, ya que contradice un poco el funcionamiento de las listas. Considerando que en el índice 0 está el primer elemento de la lista, creo que quedaría mejor utilizar append() y pop(0).
¡Hola compañero!
.
En las colas el primero en entrar es el primero en salir, ahora, trata de imaginar una cola donde quien esté al final de la lista será el primero en salir. El profesor lo hace así para aprovechar los métodos que ya traen las listas en Python, como pop().
.
Así cuando ingresa un nuevo elemento en la posición 0, se asegura de que el elemento que ingresó no va a salir con el método pop (a menos que no hayan más elementos) y los que ya estaban se reorganicen, lo que quiere decir que si ya habían elementos el que entró al principio seguirá estando listo para salir de primero con el método pop porque habrá quedado de último en la lista, recordemos que el método pop se encarga de sacar el último elemento de una lista.
.
Espero haberte aclarado un poco. ✌🏻
A mi me dejo pensando, pero tiene sentido como lo hace el profesor, si haces lo que planteas tendría que desplazar todo el código desde la derecha al principio.
En cambio así el primero en entrar para a quedar último, y ser el primer en salir con método pop.
En lugar de usar un atributo auxiliar .size o redefinir el valor del mismo con self.size = len(self.items) cada vez que hagamos una operación que lo modifique. Recomiendo hacer lo siguiente:
@property def size(self): return len(self.items)
De esta forma, cada vez que llamemos a self.size nos devolvera el resultado de la función size().
También se puede lograr de la siguiente forma:
def _size() return len(self.items) size = property( f_get = _size )
De esta forma, el valor de .size solo es accesible para ser visto o copiado, mas no modificado o setteado, ya que este, en teoría, no debería ser modificado a menos de que las lista items lo haga y también evitamos actualizar el valor de self.size en cada cambio que hagamos.
Los métodos "enqueue" y "dequeue" no deberían llamarase add y pop respectivamente?
Para colas (queues) es convención utilizar los nombres enqueue y dequeue, mientras que para stacks usamos push y pop, en tanto listas podemos usar add, pop, remove, delete, etc.
No son reglas estrictas sino convenciones, por lo tanto puedes darle el nombre que más sentido te haga :D
Python ya tiene actualmente un modulo para queues en la liberría estándar. https://docs.python.org/3/library/queue.html#queue.Queue Se usa principalmente para tareas que son consumidas por diferntes hilos. Seguro es un overkill para los ejemplos del curso pero se puede usar y ya está hecha. Sólo cambia los nombre de los métodos a put y get
La idea es entender cómo funciona una cola. Sino sería como la paradoja en la que el creador de la máquina del tiempo viaja al pasado y se entrega a sí mismo la máquina para que la cree.
class Queue: def __init__(self): self.items = [] def is_empty(self): return len(self.items) == 0 def enqueue(self, item): self.items.append(item) def dequeue(self): if not self.is_empty(): return self.items.pop(0) else: raise IndexError("Queue is empty") def front(self): if not self.is_empty(): return self.items[0] else: raise IndexError("Queue is empty") def rear(self): if not self.is_empty(): return self.items[-1] else: raise IndexError("Queue is empty") def size(self): return len(self.items) # Crear una instancia de la cola: my_queue = Queue() #Verificar si la cola está vacía: print(my_queue.is_empty()) # Resultado: True #Agregar elementos a la cola: my_queue.enqueue(1) my_queue.enqueue(2) my_queue.enqueue(3) #Obtener el elemento del frente de la cola: print(my_queue.front()) # Resultado: 1 #Eliminar y obtener el elemento del frente de la cola: print(my_queue.dequeue()) # Resultado: 1 #Obtener el tamaño actual de la cola: print(my_queue.size()) # Resultado: 2 #Verificar si la cola está vacía nuevamente: print(my_queue.is_empty()) # Resultado: False '''Creamor una instancia de la clase Queue llamada my_queue. Luego, verificamos si está vacía, agregamos elementos a la cola (1, 2 y 3), obtenemos el elemento del frente de la cola, eliminamos y obtenemos el elemento del frente, obtenemos el tamaño actual y verificamos si la cola está vacía nuevamente. Recuerda que la cola basada en listas utiliza el método append() para agregar elementos al final de la lista y el método pop(0) para eliminar y devolver el elemento del frente de la lista. Espero que esto te ayude a comprender cómo utilizar una cola basada en listas en Python. '''
Muchas gracias por tu aporte.
En el ciclo for del método traverse podrías usar enumerate y reversed para que te ponga el número de la posición de cada elemento y te imprima primero el item que va a salir después en el dequeue. Algo como
def traverse(self): for i, item in enumerate(reversed(self.items)): print(f"{i}.- {item}")
Así creo que es más facil ver cuál es el siguiente item que saldrá cuando usemos dequeue.
Otra forma sería
def traverse(self): for i in range(2,-1,-1): print(self.items[i])
Queue con list implementando métodos básicos
from typing import List from typing import Any from typing import Iterable from typing import Optional from node import Node class Queue: """Represents a simple queue.""" _items: List def __init__(self, *items) -> None: """Initializes the Queue""" self._items = [] if len(items) > 0 and isinstance(items[0], Iterable): items = items[0] for item in items: self.enqueue(item) def clear(self): """Clears the queue. Time complexity: O(1) """ self._items = [] def peek(self): """Returns the first element of the queue. Raises IndexError if the queue is empty. Time complexity: O(1) Returns: Any: First element of the queue. """ if len(self._items) == 0: raise IndexError('The queue is empty.') return self._items[0] def is_empty(self) -> bool: """Check if the queue is empty. Returns: bool: True if the queue is empty. False otherwise. """ return len(self._items) == 0 def enqueue(self, value: Any) -> None: """Adds a new value to the queue. Time Complexity: O(n) Args: value (Any): Value to be added. Returns: None """ self._items.append(value) return None def dequeue(self): """Removes a value from the queue. Raises IndexError if the queue is empty. Time complexity: O(n) Returns: Any: Removed value. """ if len(self._items) == 0: raise IndexError('The queue is empty.') value = self._items.pop(0) return value def copy(self): """Returns a copy of the current queue. Time complexity: O(1) Returns: Queue: Copy of the current queue. """ new_queue = Queue() new_queue._items = self._items return new_queue def depthcopy(self): """Returns a copy of the current queue. This function will create a copy of value in the queue. Time Complexity: O(n) Returns: Queue: Copy of the queue. """ new_queue = Queue() new_queue._items = [item for item in self] return new_queue def itervalues(self) -> Iterable[Any]: """Generates an iterable of the values in the queue. Time complexity: O(n) Returns: Iterable: Iterable of the values in the queue. """ return iter(self._items) def __len__(self) -> int: """Returns the length of the queue when using the `len` built-in function. Time complexity: O(1) Returns: int: Number of nodes into the queue. """ return len(self._items) def __str__(self): """Returns a string representation of the queue. Time complexity: O(n) Args: str: Representation of the queue """ return '->'.join(self._items) def __iter__(self) -> Iterable[Any]: """Generates an iterable of the values in the queue. Time complexity: O(n) Returns: Iterable: Iterable of the values in the queue. """ return self.itervalues() def __contains__(self, value: Any) -> bool: """Checks if a value is in the queue. Time complexity: O(n) Args: value: Value to be searched in the queue. Returns: bool: True if the value is in the queue. False otherwise. """ for item in self: if item == value: return True return False def __add__(self, other: Iterable) -> 'Queue': """Returns a new queue with the items of both queues. Time complexity: O(n) Args: other (Iterable): Items to be added to the current queue. Returns: Queue: New queue with the items of both queues. """ new_queue = self.depthcopy() new_queue._items += [item for item in other] return new_queue
Unit tests
# Unittest import unittest # Utilities from queue_with_list import Queue class QueueTestCase(unittest.TestCase): """Queue test cases.""" def test_initialize_empty(self): """Test initialize empty queue.""" _queue = Queue() self.assertEqual(len(_queue), 0) def test_intialize_with_list(self): """Test initialize with list.""" _queue = Queue([1, 2, 3]) self.assertEqual(len(_queue), 3) for a, b in zip(_queue, [1, 2, 3]): self.assertEqual(a, b) def test_initialize_with_tuple(self): """Test initialize with tuple.""" _queue = Queue((1, 2, 3)) self.assertEqual(len(_queue), 3) for a, b in zip(_queue, [1, 2, 3]): self.assertEqual(a, b) def test_initialize_with_set(self): """Test initialize with set.""" _queue = Queue({1, 2, 3}) self.assertEqual(len(_queue), 3) for a, b in zip(_queue, [1, 2, 3]): self.assertEqual(a, b) def test_initialize_with_iterable(self): """Test initialize with iterable.""" _queue = Queue(range(1, 4)) self.assertEqual(len(_queue), 3) for a, b in zip(_queue, [1, 2, 3]): self.assertEqual(a, b) def test_is_empty(self): """Test is empty.""" _queue = Queue() self.assertTrue(_queue.is_empty()) _queue = Queue([1, 2, 3]) self.assertFalse(_queue.is_empty()) def test_enqueue(self): """Test add.""" _queue = Queue() _queue.enqueue(1) self.assertEqual(len(_queue), 1) _queue.enqueue(2) self.assertEqual(len(_queue), 2) def test_peek(self): """Test peek.""" _queue = Queue() self.assertRaises(IndexError, _queue.peek) _queue = Queue([1, 2, 3]) self.assertEqual(_queue.peek(), 1) def test_dequeue(self): """Test dequeue.""" _queue = Queue([1, 2, 3]) self.assertEqual(_queue.dequeue(), 1) self.assertEqual(_queue.dequeue(), 2) self.assertEqual(_queue.dequeue(), 3) self.assertRaises(IndexError, _queue.dequeue) def test_copy(self): """Test copy.""" _queue = Queue([1, 2, 3]) queue_copy = _queue.copy() self.assertIsNot(_queue, queue_copy) self.assertEqual(len(_queue), len(queue_copy)) for a, b in zip(_queue, queue_copy): self.assertEqual(a, b) def test_depthcopy(self): """Test depthcopy.""" _queue = Queue([1, 2, 3]) queue_copy: Queue = _queue.depthcopy() self.assertIsNot(_queue, queue_copy) self.assertEqual(len(_queue), len(queue_copy)) for a, b in zip(_queue, queue_copy): self.assertEqual(a, b) def test_clear(self): """Test clear.""" _queue = Queue([1, 2, 3]) _queue.clear() self.assertEqual(len(_queue), 0) def test_contains(self): """Test contains.""" _queue = Queue([1, 2, 3]) self.assertTrue(1 in _queue) self.assertFalse(4 in _queue) def test_add_operator(self): """Test add operator.""" _queue = Queue([1, 2, 3]) _queue += [4, 5, 6] self.assertEqual(len(_queue), 6) for a, b in zip(_queue, [1, 2, 3, 4, 5, 6]): self.assertEqual(a, b)
Excelente clase profesor. Tengo una consulta cuando uso el método "insert(indice,item)" Yo intuía que el menor indice debería ubicarse mas a la izquierda, pero el resultado de este código no es el que me esperaría. A qué se debe esto?
lista=[] lista.insert(30,"silla") lista.insert(20,"cama") lista.insert(3,"muebles") lista.insert(2,"escaleras") lista.insert(13,"puertas") print(lista)
OUTPUT: ['silla', 'cama', 'escaleras', 'muebles', 'puertas']
Para el caso del método de traverse, para imprimir la lista en el sentido FIFO pueden hacer una ligera modificación:
def traverse(self): total_items = self.size for item in range(total_items): print(self.items[(item+1)*-1])
Pero me quedó la intriga si hay alguna forma alternativa para conseguir la impresión FIFO de forma más optima.
Para recorrer los elementos de la cola puedes usar un for in def traverse(self): for item in self.items: print(item)
def traverse(self): for item in self.items: print(item)
Por medio de opciones. Increibe
..
Excelente.
Dejo código comentado para mejor entendimiento:
class ListQueue: def __init__(self): self.items = [] # Inicializa una lista vacía para almacenar los elementos de la cola self.size = 0 # Inicializa el tamaño de la cola como 0 def enqueue(self, data): self.items.insert(0, data) # Agrega el elemento al principio de la lista (FIFO) self.size += 1 # Incrementa el tamaño de la cola def dequeue(self): data = self.items.pop() # Elimina y devuelve el último elemento de la lista (FIFO) self.size -= 1 # Decrementa el tamaño de la cola return data # Retorna el elemento eliminado def traverse(self): total_items = self.size # Obtiene el tamaño total de la cola for item in range(total_items): # Itera sobre cada elemento de la cola print(self.items[item]) # Imprime el elemento en la posición actual ```class ListQueue:   def \_\_init\_\_(self):   self.items = \[] # Inicializa una lista vacía para almacenar los elementos de la cola   self.size = 0 # Inicializa el tamaño de la cola como 0   def enqueue(self, data):   self.items.insert(0, data) # Agrega el elemento al principio de la lista (FIFO)   self.size += 1 # Incrementa el tamaño de la cola   def dequeue(self):   data = self.items.pop() # Elimina y devuelve el último elemento de la lista (FIFO)   self.size -= 1 # Decrementa el tamaño de la cola   return data # Retorna el elemento eliminado   def traverse(self):   total\_items = self.size # Obtiene el tamaño total de la cola   for item in range(total\_items): # Itera sobre cada elemento de la cola   print(self.items\[item]) # Imprime el elemento en la posición actual
o la clase estaba muy fácil o ya voy mejorando, creo que es lo primero jejeje
en el min 3:28 en la linea 9 pone inser y luego lo cambia sin avisar, digo yo me dei cuenta en su momento pero si editan el video deben de explicar el error, a veces eso nos retrasa cuando son cosas mas complejas.
En la clase pasada lo explica como add y pop y en este si como enqueue y dequeue. Pero bueno tal vez sea porque va hacerlo con stacks
Los métodos enqueue y dequeue están implementados al revés y eso puede confundir. El primer elemento de una lista siempre está en el índice cero lista[0]. Por lo tanto, al agregar un elemento este tiene que ir después del primero, eso se hace con la función lista.append(). Al quitar un elemento este tiene que ser el que se encuentre en la primera posición, esto lo podemos hacer con lista.pop(0). Por los tanto las funciones quedarían así:
def enqueue(self, data): self.items.append(data) self.size += 1 def dequeue(self): data = self.items.pop(0) self.size -= 1 return data
Por eso es que en el minuto 5:45 al usar food.traverse() la cola se le imprime en orden inverso.
class Queues_List: def __init__(self): self.items = [] self.size = len(self.items) def seelist(self): # ver lista completa print(self.items) def enqueue(self, data): # agregar elemento self.items.insert(0,data) def dequeue(self): # despachar el primer elemento en entrar frontdel = self.items[2] self.items.pop() print(f"elemento borrado: {frontdel}") return frontdel Q = Queues_List() Q.enqueue("Norte") Q.seelist() Q.enqueue("Este") Q.seelist() Q.enqueue("Sur") Q.seelist() Q.dequeue() Q.seelist()
Asi se verá el proceso del codigo:
self.size=len(self.items)
