Cursos Empresas Blog Live Conf Eventos Precios

0:007:20

Recursos

Resumen

¿Cómo crear una cola basada en listas?

El concepto de colas es esencial en programación, especialmente en estructuras de datos. Una cola opera bajo el principio "primero en entrar, primero en salir" (FIFO: First In, First Out), lo que significa que el primer elemento en ser introducido en la cola será el primero en salir. En este segmento, abordaremos cómo crear una cola sencilla utilizando listas en Python, uno de los lenguajes de programación más populares hoy en día.

¿Cómo se inicia la construcción de una clase de cola?

Para comenzar, creamos un archivo llamado list_based_queue.py. En este archivo, desarrollamos una clase denominada ListQueue en Python. Esta clase será la base de nuestra estructura de cola. Los pasos iniciales incluyen definir el constructor de la clase, donde se establecerán los atributos:

class ListQueue:
    def __init__(self):
        self.items = []  # Lista vacía para almacenar elementos
        self.size = 0    # Tamaño de la cola

En este constructor, self.items es una lista vacía donde almacenaremos los elementos de la cola, y self.size nos permitirá rastrear el tamaño actual de la cola.

¿Cuáles son los métodos esenciales de una cola?

Los métodos cruciales de una cola son enqueue y dequeue, los cuales se usarán para añadir y eliminar elementos, respectivamente.

Enqueue (Añadir elementos): Este método permite agregar elementos al inicio de la cola, incrementando su tamaño.

def enqueue(self, data):
    self.items.insert(0, data)  # Inserta el elemento en la posición cero
    self.size += 1              # Incrementa el tamaño de la cola

Dequeue (Remover elementos): Este método elimina elementos desde el frente de la cola, disminuyendo su tamaño.

def dequeue(self):
    if self.size > 0:
        data = self.items.pop()  # Remueve el elemento del final
        self.size -= 1           # Decrementa el tamaño de la cola
        return data
    else:
        return "La cola está vacía"

¿Cómo podemos visualizar los elementos de la cola?

Ver y entender lo que hay en nuestra cola es crucial para cualquier desarrollador. El método traverse nos facilita esto:

def traverse(self):
    total_items = self.size  # Total de elementos
    for i in range(total_items):
        print(self.items[i])  # Imprime cada elemento de la cola

Durante el desarrollo, es común enfrentar errores. Uno podría encontrar que el número de total_items no es iterable debido a una mala especificación. Esto se soluciona, asegurando el uso de un tipo range.

¿Qué sucede durante la ejecución?

Finalmente, en un entorno interactivo de Python, importamos y probamos la clase ListQueue:

from list_based_queue import ListQueue

q = ListQueue()
q.enqueue('eggs')
q.enqueue('ham')
q.enqueue('spam')

print(q.dequeue())    # Salida: 'eggs'
q.traverse()          # Salida: 'spam', 'ham'

Veremos cómo se comportan los elementos de la cola, alineándose al principio FIFO. Así, al usar dequeue en nuestra cola, el primer elemento añadido es el primero en ser removido, lo cual verifica el correcto funcionamiento de nuestro código.

¿Qué sigue después de implementar la cola basada en listas?

Tras la elaboración de una cola con listas, el siguiente paso puede ser desarrollar una estructura de cola basada en dos pilas (stacks). Esto puede sonar intrigante, pero es una técnica popular en entrevistas técnicas de programación. Esta práctica no solo amplía el conocimiento de los desarrolladores sino que también afina sus habilidades para resolver problemas avanzados.

¡Sigue avanzando en esta visión fascinante de las estructuras de datos y continúa reforzando tus habilidades como desarrollador!

Creación de una Cola Basada en Listas en Python

Curso de Estructuras de Datos Lineales con Python

Clase 19 de 23

Clase 19 / 23

Jose Noriega

Hace 5 años

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

Jose Noriega

Hace 5 años

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)

Comentarios (21)21 comentarios

Christian Molina Vázquez

Para obtener el tamaño, simplemente aplicaría la función len() a la lista self.items.

self.size = len(self.items)

Alexis Dorado Muñoz

Hace 2 años

Muchas gracias por tu aporte.

Michelle Duque De La Rosa

Gracias

Fabián Aravena Silva

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).

José Isidro Torres Caldea

¡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. ✌🏻

Mauricio Gonzalez Falcon

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.

Romel Manrique

Hace 4 años

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.

Valentin Francisco Blanco

Los métodos "enqueue" y "dequeue" no deberían llamarase add y pop respectivamente?

Héctor Daniel Vega Quiñones

Profesor

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

Juan Antonio Aramburo Pasapera

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

Pablo Joaquín Cruz

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.

Jhon Freddy Tavera Blandon

Hace 3 años

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.

Lucas Yañez

Otra forma sería

    def traverse(self):
        for i in range(2,-1,-1):
            print(self.items[i])

Elvis Ronald Cruz Chullo

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']

José Joaquín Tripp Gudiño

Hace un año

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.

Oscar Rogelio Heredia Ruiz

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)

Rigoberto Maldonado

Por medio de opciones. Increibe

Excelente.

Andrés Cardona

Germán García

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.

Nicolas Alpargatero

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

Dante Rodrigo Méndez Pérez

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:

Luis Santiago jaramillo espinosa

Recursos

Resumen

Creación de una Cola Basada en Listas en Python

Progreso del curso

Introducción a las estructuras de datos

Arrays

Linked lists

Stacks

Queues

Próximos pasos