Saltar al contenido
KodigoSwift

Estructuras de Datos – Colas

Estructuras de Datos - Colas
  • 1
  • 1
  • 0
  • 1

    Hoy abordaremos una nueva estructura de datos, aprenderemos a implementar una Cola (Queue en Inglés). Las colas son estructuras de datos bien populares y relativamente fáciles de implementar. Pudiéramos definirla como una fila cualquiera en la cual sus elementos una vez se insertan se van procesando en orden de entrada y solamente podemos consultar el elemento más antiguo dentro de esta.

    Esto garantiza que el primer elemento añadido a la cola (enqueue) sea el primero en extraerse (dequeue). Es como una fila / cola de la vida real donde habemos algunos esperando a llegar a la caja y pagar lo que vamos a llevar. El primer cliente que llegó es al que están atendiendo actualmente y el último tendrá que esperar a que el resto de personas sean atendidas. Básicamente el primer elemento en entrar es el primero en atenderse, servirse o procesarse.

    ¿Por qué necesitaríamos implementar algo así?

    Bueno, en muchos algoritmos se nos presenta la necesidad de crear una lista de elementos temporales donde el orden también puede ser relevante y que luego usaremos nuevamente. Sí en este punto te parece que las Colas son muy similares a las Pilas pues tienes razón, la diferencia reside en que una Cola por concepto configura el orden de sus elementos en modo FIFO (First-In First-Out), el primero en entrar es el primero en salir a diferencia de la estructura de datos Pila que es LIFO (Last-In First-Out) donde el último en entrar es el primero en salir.

    Implementación de una Cola

    La mejor manera de volvernos mejores programadores es haciendo, así que pasemos a desarrollar nuestro ejemplo:

    En este primer fragmento de código hemos declarado una estructura de nombre Queue (Cola), dentro de esta tenemos una variable de nombre list (Lista) cuyo nivel de acceso la limita al ámbito del archivo donde está declarada la estructura de la cual es miembro. Otro aspecto a destacar es el tipo LinkedList ya que no es parte de ninguna librería o framework, ha sido implementado en un anterior artículo donde aprendimos sobre otra importante estructura de datos: las listas enlazadas.

    En la medida que vayamos desarrollando nuestra Cola iremos tomando conciencia sobre la utilidad de esta lista. Continuemos con esos aspectos que definen esta estructura de datos:

    Agregar a la Cola

    Como ya hemos comentado al inicio, nuestra cola necesita de un método enqueue que se encargue de agregar un elemento. Bajo dicha premisa añadiremos esta funcionalidad a nuestra estructura, quedando así:

    Aquí tenemos una función marcada como mutating debido a que modifica (mutate) el estado de una variable miembro, de nombre enqueue y recibe un solo elemento de tipo entero (Int).

    Si no has escuchado hablar de mutating o no sabes bien de que va, pues te recomiendo nuestro tutorial dedicado a las estructuras y clases en el lenguaje Swift.

    Por último en la línea 7 hacemos uso de nuestra variable list y ejecutamos el método append al cual pasamos como parámetro la constante element que ha sido enviada por el cliente de nuestra Cola.

    Remover de la Cola

    La funcionalidad que nos permite eliminar un elemento de la Cola tiene un enfoque bien sencillo:

    Nuestra función dequeue no necesita parámetros, recordemos que en una Cola siempre se elimina o procesa el primer elemento que fue agregado a esta y gracias a que estamos almacenando estos elementos en nuestra lista enlazada pues hacemos uso de la propiedad computada first y nos evitamos así la implementación de un mecanismo con el fin de encontrar este primer elemento de la lista. Esta es la razón por la que no necesitamos parámetros en nuestra función y también el motivo por el que nos estamos apoyando en la lista enlazada que ya hemos desarrollado, y es que como ya comentamos ambas estructuras de datos son bien similares.

    En la línea 5 verificamos mediante guard que la lista no esté vacía ya que no tendría sentido eliminar algo que no existe al mismo tiempo que obtenemos el primer elemento de la misma. Si esto falla interrumpimos la ejecución o de lo contrario pasamos a la línea 11 donde eliminamos el elemento ejecutando la función remove. Finalizamos en la línea 13 retornando el valor asociado al elemento que acaba de ser eliminado.

    Obtener el primer elemento

    Otra características de las Colas es el método peek, mediante el cual podremos echar una ojeada al primer elemento de la Cola pero sin eliminarlo. Exacto, sería una implementación bien similar a la anterior:

    En esta función volvemos a usar guard para verificar que la lista no está vacía y también obtenemos el primer elemento de la lista, prácticamente es idéntica a la función dequeue, con diferencia del nombre y que solamente retornamos el valor del elemento sin eliminarlo de la lista.

    En este sito hemos escrito un tutorial sobre la instrucción guard, la pirámide de la perdición y la salida temprana. Quedas invitado a su lectura si deseas conocer más sobre esta sentencia y por que abogamos por su uso en lugar del clásico if.

    De ahí el nombre de peek (ojeada), la intención detrás de esta función es tan básica como la obtención de una referencia, visualizar el valor del actual primer elemento.

    ¿Está la Cola vacía?

    Al igual que con nuestra lista enlazada en el caso de la Cola también necesitamos conocer si está vacía o no:

    Nuevamente nos apoyamos en nuestra lista enlazada y creo que es evidente que sería así. En este punto es claro el hecho de que estamos implementando una estructura de datos haciendo uso de las funcionalidades de otra, nuestra estructura Queue viene a ser como un wrapper (envoltura) de la clase LinkedList.

    Reiniciando la Cola

    Se impone una vía para reiniciar nuestro sistema y es que en ocasiones, muchas de hecho, necesitamos eliminar todos los elementos y disponernos a comenzar desde cero:

    Lo primero que hacemos en este método es comprobar si la Cola contiene elementos ya que si esta se encuentra en su estado inicial no tiene sentido eliminar algo que no existe, si este es el caso devolvemos false, indicando que la estructura de datos no cuenta con elementos a remover. Solamente si la Cola cuenta con elementos saltamos a la línea 9 en la cual eliminamos todos los elementos disponibles y retornamos true para informar que ha terminado con éxito la ejecución.

    Imprimiendo la Cola

    Si has leído varios de nuestro tutoriales ya sabrás que nos gusta implementar la propiedad computada description en nuestros tipos personalizados:

    Esta característica no es como tal parte de nuestra estructura de datos así que hacemos uso de una extension para incorporar el protocolo CustomStringConvertible y con esto adoptar la propiedad antes comentada.

    Si tienes alguna duda con el código anterior te recomendamos la lectura de nuestros artículos dedicados a las extensiones y los protocolos.

    Como podemos constatar en el anterior ejemplo solamente devolvemos la descripción de la lista, luego de esto ya podemos utilizarla por ejemplo dentro de una función print y obtener una salida formateada.

    Probando nuestra implementación

    En este punto se impone que probemos todo cuanto hemos desarrollado hasta ahora. Necesitamos comprobar que las funcionalidades tras enqueue, dequeue, peek, isEmpty y description se comportan de la manera deseada.

    Enqueue y description

    Para esto hagamos lo siguiente:

    …la salida en pantalla del anterior código es:

    En este punto podemos constatar que el método enqueue funciona correctamente al igual que la extension que hemos aplicado sobre la clase Queue y mediante la cual obtenemos una salida en pantalla mucho más legible. Pueden comentar el segmento de código asociado a la extensión y comparar, verán a lo que me refiero.

    Dequeue

    Ahora probemos con la función dequeue recordando que de ejecutarla sobre el código anterior, el número 2 (el primero que hemos añadido) deberá ser el elemento removido:

    …en este ejemplo la primera línea corresponde a la línea 7 del código anterior, ejecutamos el método dequeue y luego volvemos a imprimir el contenido de la Cola. La salida en pantalla:

    …como podemos ver ha funcionado de la manera esperada y si lo volviéramos a ejecutar …Exacto, el número 15 sería el próximo a eliminar.

    Peek

    La función peek es igual de sencilla de probar, añadimos el siguiente código al anterior:

    En la línea 3 tenemos la llamada a nuestro método peek. Lo hemos envuelto dentro de un print ya que este nos devuelve el valor del elemento que se encuentra listo para ser procesado y de esta manera, obviamente, lo capturamos hacia la salida estándar:

    Nos percatamos que está funcionando bien pero nos imprime el valor (15) aún en su estado optional. Así que modificaremos la anterior a la siguiente versión:

    Ahora la salida en pantalla se muestra así:

    El cambio que hemos aplicado también pudiéramos haberlo realizado sobre el resto de llamadas que devuelven nil en caso de la lista estar vacía, pero esto tornaría más grande el ejemplo cuando la razón de ser de los mismos es solamente probar que nuestra Cola funciona correctamente, no obstante creo válida la advertencia.

    isEmpty y removeAll

    Por último hagamos un test sobre isEmpty, esta propiedad computada nos debe devolver false si la ejecutamos ahora sobre los dos elementos que tenemos en nuestra Cola:

    …la salida en pantalla como era de esperar es:

    Ahora, si queremos probar que sucede cuando la Cola está vacía tendríamos o bien implementar un loop donde ejecutemos dequeue hasta que no quede elementos o bien ejecutar el método removeAll que ya nos ayuda con esta funcionalidad:

    …la salida sería:

    Creo que la lógica tras lo que acabamos de hacer es bastante evidente si leemos la salida en pantalla. Imprimimos los elementos disponibles, verificamos si está vacía, la reiniciamos con éxito, volvemos a imprimir la Cola y verificamos que está vacía y por último verificamos que de hecho lo está.

    Implementación genérica

    En este punto, ya hemos implementado una cola de uso general que almacena valores Int y proporciona varias funcionalidades. En esta sección, modificaremos un poco el código que hemos desarrollado hasta el momento en pos de usar genéricos a favor de abstraer el requisito de tipo de dato que actualmente tiene nuestra Cola.

    Actualicemos la implementación de Queue a la siguiente versión:

    Básicamente lo que hemos hecho es cambiar la primera línea y establecer el clásico <T> (hemos elegido T por convención pero pudo haber sido cualquier otra letra o palabra, es sencillamente un placeholder) y luego sustituir en todos los lugares donde había un Int por una T, la cual es la representación genérica de ese tipo indeterminado (en este punto) que en un futuro podría ser un valor Int, String o un Double.

    No he explicado en detalles los últimos cambios ya que es un tema que se ha abordado en otro artículo. Si deseas aprender más te exhorto a que visites nuestro tutorial sobre los tipos genéricos en Swift.

    Luego de esto podemos hacer la siguiente prueba:

    …la salida en pantalla sería:

    Ya en este punto queda poco por explicar: en el código anterior hemos declarado dos Colas, cada una de un tipo de dato distinto, la primera intQueue de tipo Int y la segunda de nombre stringQueue de tipo String.

    Resumen

    En este artículo hemos implementado una estructura de datos que en ocasiones nos servirá para gestionar ciertos modelos que pudieran coincidir con esta estructura. Al mismo tiempo hemos visto como haciendo uso de una Lista Enlazada definimos el comportamiento de nuestra Cola, reutilizando nuestro propio código y evitando reinventar esa rueda que ya hemos creado y que funciona bien.

    Continuaremos publicando artículos en la sección de Algoritmos, abordando otras estructuras de datos que nos ayuden a mejorar en este nuestro camino hacia la excelencia como desarrolladores Swift.

    Falta aún mucho por aprender en nuestro camino a convertirnos en iOS Developer. Suscríbete a nuestra lista de correo mediante el formulario en el panel derecho y síguenos en nuestras redes sociales. Mantente así al tanto de todas nuestras publicaciones futuras.

    Espero que todo cuanto se ha dicho aquí, de una forma u otra le haya servido de aprendizaje, de referencia, que haya valido su preciado tiempo.

    Este artículo, al igual que el resto, será revisado con cierta frecuencia en pos de mantener un contenido de calidad y actualizado.

    Cualquier sugerencia, ya sea errores, información o ejemplos a añadir será, más que bienvenida, necesaria!

    • 1
    • 1
    • 0
    • 1
    • 1
    • 1
    • 0
    • 1

    Entradas relacionadas

    close
    Gracias!

    Gracias por compartir, eres increíble

    RECIBE CONTENIDO SIMILAR EN TU CORREO

    RECIBE CONTENIDO SIMILAR EN TU CORREO

    Suscríbete a nuestra lista de correo y mantente actualizado con las nuevas publicaciones.

    Se ha suscrito correctamente!