Colas (Queue) en Swift

En la anterior guía hablamos sobre las estructuras de datos y realizamos la implementación de un pila (Stack) en Swift. Ahora continuaremos con otra de las estructuras llamadas colas (Queues).

Definición de Colas (Queues)

Las colas son otra de las estructuras de datos usadas en la programación para almacenar datos de forma secuencial.

queue example

La forma mas fácil de visualizar una Cola (queue) en la vida real son las típicas colas o filas que hacemos en los bancos. Siempre se rigen por el principio FI-FO que significa "First In - First Out", el primero que entra es el primero en salir.

En la imagen anterior puedes ver una descripción gráfica de como funciona una Cola (queue). Tienen dos funciones básicas queue y dequeue que se encargan de agregar y sacar elementos de la Cola respectivamente.

Implementación

Lo primero que necesitamos es crear una clase que modele cada una de las cajas azules (Nodos) que vimos en la imagen de anterior.

class Node<E> {  
    var element: E?
    var next: Node<E>?

    init(element: E) {
        self.element = element
    }
}

Si viste el post se Pilas (Stack) notaras que esta clase es exactamente igual.

Ahora crearemos la clase que se encarga de modelar la Cola (Queue)

class Queue<E> {

    var head: Node<E>?
    var size = 0

    func enqueue(element: E) {
        size += 1
        if head == nil {
            head = Node(element: element)
            return
        }

        var lastNode = head
        while lastNode?.next != nil {
            lastNode = lastNode?.next
        }

        lastNode?.next = Node(element: element)
    }

    func dequeue() -> E? {
        let element = head?.element
        head = head?.next
        size -= 1
        return element
    }
}

Ahora te daré un poco de contexto sobre las funciones queuey dequeue.

queue

Lo primero que hay que tener en cuenta es el caso base, que es cuando la Cola esta vacia en ese caso cremos un nuevo nodo y lo asignamos como head ya que es el primero.

Cuando agregamos mas elementos, lo que hacemos es buscar el ultimo elemento desde head, para esto iteramos por cada uno de los nodos (next) hasta que lleguemos a nil, esto nos indicará que es el ultimo nodo así que aquí es donde agregamos el nuevo elemento.

deuque

Es la función mas sencilla, como es una Cola sabemos que el elemento que sale debe ser el primero que llegó y en este caso corresponde a head, simplemente obtenemos el elemento y movemos head al siguiente nodo.

Bonus

peek la función útil que no devuelve el primer elemento de la Cola.

func peek() -> E? {  
    return head?.element
}

Con esto terminamos esta guía, recuerda que puedes encontrar el código fuente en GitHub.

Jose Aponte

Desarrollador full-stack apasionado por las tecnologías de información y los lenguajes de programación. Me gustan divertirme con mi familia, mi lema es "Nunca paras de Aprender"

Bogota

Subscribe to Jappsku Engineering Blog

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!