Pilas y colas

Resumen

Las pilas y las colas son estructuras de datos habituales en informática que especifican el orden en que puedes añadir y eliminar elementos. Puedes utilizarlas para controlar el orden en que interactúas con los datos:

• Pila: un contenedor en el que se introducen y retiran elementos siguiendo el orden FILO (primero en entrar, último en salir), como coger un libro de la parte superior de una pila de libros para leerlo.

• Cola: un contenedor en el que se introducen y retiran elementos siguiendo el orden FIFO (primero en entrar, primero en salir), como la gestión de una cola de clientes que esperan para comer.

Aunque el código subyacente de las pilas y las colas es similar, cada una tiene diferencias clave y puntos fuertes que puedes aprovechar para que tu experiencia sea rápida, eficiente e intuitiva.

Pilas

Puedes pensar en una pila como en una pila de tortitas. Supón que estás en una cafetería para desayunar y la persona que te atiende te sirve una pila interminable de tortitas. Como quieres comportarte con educación, solo cogerás una tortita cada vez y solo de la parte superior de la pila. Puedes pedir al camarero que aplique una nueva tortita a la parte superior de la pila y, cuando tengas hambre, puedes sacar una tortita de la parte superior de la pila y pasarla al plato para comértela. Si quieres comerte una tortita concreta del medio de la pila, tendrás que seguir comiendo tortitas desde arriba hasta llegar a la que quieres. La primera tortita que se añada será la última que retires. Esto hace que una pila sea una estructura de datos *FILO (primero en entrar, último en salir).

Cuándo utilizarlas

Las pilas son útiles cuando necesitas retroceder o recordar en qué orden realizaste los eventos. Puede ser una función de deshacer, una cadena de eventos o una serie de elecciones. Por ejemplo, quizá tengas un robot que deba resolver un laberinto con caminos que se ramifican. Cuando el robot llega a una división en el laberinto, elige un camino y añade esa elección a la pila. Cuando llega a un callejón sin salida, retrocede por la pila y elimina opciones hasta que encuentra un nuevo camino que pueda tomar.

Implementación en Verse

La API de Verse no tiene una implementación integrada de pilas, pero puedes crear una tú mismo.

Puedes representar los elementos de una pila mediante cualquier estructura de datos ordenada, como una matriz o una lista vinculada. En este ejemplo, utilizarás una matriz, ya que te permite acceder fácilmente a la parte superior de la pila.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

La matriz Elements almacena los objetos de la pila, que son de tipo t. Esto significa que puedes inicializar una pila con cualquier tipo de elemento, como int, float, stack, etc. Utilizar type como argumento de la clase `stack` es un ejemplo de [tipo paramétrico](parametric-types-in-verse).

Definamos primero algunas funciones de ayuda. Necesitas saber dónde está la parte superior de la pila para poder añadir y sacar elementos con Push() y Pop(). Para ello, necesitarás tres funciones: Size(), IsEmpty() y Peek().

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

La función de tamaño Size() simplemente devuelve la longitud Length de la matriz Elements. La función IsEmpty() llama a la función Size() y tiene el especificador <transacts>, lo que significa que fallará si Size() no es igual a 0.

La función Peek() devuelve el elemento situado en el índice superior (Length - 1) de la matriz de elementos. Esta función tiene los especificadores <decides><transacts>, ya que el acceso a la matriz puede fallar si la matriz está vacía.

Para instanciar una pila puedes utilizar una función constructor. Un constructor es una función especial que crea una instancia de la clase a la que está asociado. El constructor establece los valores iniciales de un objeto y te permite acceder al valor de Elements y asignarlo a una matriz inicial de elementos.

# Creates and returns a stack from an initial array of elements InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

Cómo añadir y sacar

Para añadir y eliminar elementos de la pila, tienes que añadir (push) el nuevo elemento a la parte superior de la pila o sacarlo (pop) de la parte superior.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

La función Push() toma el elemento que quieres poner encima de la pila y devuelve una nueva pila con el elemento encima. Devolver una nueva pila en lugar de modificar la pila actual es un ejemplo de programación funcional y reduce el riesgo de efectos secundarios.

Para implementar la función Pop(), primero tienes que encontrar el elemento de la parte superior de la pila con Peek(). A continuación, tienes que eliminar el elemento de la parte superior (mediante la función RemoveElement[]) y también devolver una nueva pila sin el elemento. Puedes utilizar una tupla para devolver simultáneamente la nueva pila y el elemento eliminado. Debido a las expresiones falibles para el acceso a la matriz y la llamada a Peek(), Pop() debe tener los especificadores <decides><transacts>.

Código completo

A continuación se proporciona el código completo de la clase stack.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

Colas

Puedes pensar en una cola como una cinta transportadora de sushi. Supón que estás en un restaurante de sushi que te envía platos de uno en uno por una cinta transportadora y que llegan en el orden en que se pidieron. Puedes sacar de la cola el plato del principio de la cola para cogerlo y comértelo, pero solo puedes coger un plato cada vez. Cuando quieras pedir otro plato, pídele al cocinero que ponga un plato al final de la cola. Si en la cola ya hay otros platos de sushi, tendrás que seguir comiendo platos de la parte delantera de la cola hasta llegar al plato del fondo. El primer plato de sushi que añadas será el primero que retires. Esto hace que una cola sea una estructura de datos FIFO(primero en entrar, primero en salir).

Cuándo utilizarlas

Las colas son útiles cuando necesitas procesar datos en función del momento en que llegan. Puede tratarse de atender clientes en un autoservicio, hacer cola en un centro de llamadas o realizar una serie de preguntas en una entrevista. Por ejemplo, si necesitas crear una sala de espera para los jugadores mientras realizan una tarea o pasan por una experiencia de uno en uno, podrías utilizar una cola para ordenar a los jugadores por orden de llegada.

Implementación en Verse

La API de Verse no tiene una implementación integrada de colas, pero puedes crear una tú mismo.

Al igual que las pilas, puedes representar los elementos de la cola mediante cualquier estructura de datos ordenada, como una matriz o una lista vinculada. En este ejemplo, utilizarás una matriz, ya que te permite acceder fácilmente tanto a la parte delantera como a la trasera de la cola. Para implementar una cola mediante una lista vinculada, consulta este fragmento de código.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

La matriz Elements almacena los objetos de la cola de tipo t. Esto significa que puedes inicializar una cola con cualquier tipo de elemento, como int, float, queue, etc. Utilizar type como argumento de la clase `stack` es un ejemplo de [tipo paramétrico](parametric-types-in-verse).

Al igual que las pilas, las colas necesitan algunas funciones auxiliares. Necesitas saber dónde está la parte delantera y trasera de la cola para poder añadir o sacar con las funciones Enqueue() y Dequeue(). También es útil saber el tamaño de la cola y si la cola está vacía. Lo definirás en cuatro funciones: Size(), IsEmpty(), Front() y Back().

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

La función de tamaño Size() devuelve la longitud Length de la matriz Elements. La función IsEmpty() llama a la función Size() y tiene el especificador <transacts>, lo que significa que fallará si Size() no es igual a 0.

Las funciones Front() y Rear() devuelven el elemento en el índice anterior (index 0) y posterior (Length - 1) de la matriz de elementos. Estas dos funciones tienen los especificadores <decides><transacts>, ya que el acceso a la matriz puede fallar si la matriz está vacía.

Al igual que stack, la clase queue también tiene que utilizar una función `constructor` para asignar la matriz Elements. La función `constructor` permite acceder al valor de Elements y asignarlo a una matriz inicial de elementos.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Cómo añadir y sacar de la cola

Para añadir y sacar elementos de la cola, tienes que añadir el nuevo elemento en la parte trasera de la cola, o sacar un elemento de la parte delantera.

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

La función Enqueue() toma el elemento que quieres insertar en la cola y devuelve una nueva cola con el nuevo elemento al final. Devolver una nueva cola en lugar de modificar la cola actual es un ejemplo de programación funcional y reduce el riesgo de efectos secundarios.

Para la función Dequeue(), tienes que eliminar y devolver el elemento al principio de la cola y también devolver una nueva cola con el primer elemento eliminado (utilizando la función RemoveElement[]). Debido a las expresiones falibles para el acceso a la matriz y la llamada a Front(), Dequeue() debe tener los especificadores <decides><transacts>.

Código completo

A continuación se proporciona el código completo de la clase queue.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

Por tu cuenta

Hay muchas formas de iterar y mejorar las pilas y las colas, por lo que te recomendamos que explores diferentes maneras de añadir funcionalidad. Aquí tienes algunas ideas para empezar:

• ¿Puedes convertir una cola en una cola circular, en la que el último elemento esté conectado al primer elemento y la cola siga haciendo un bucle?

• ¿Y una cola prioritaria, en la que los objetos se ordenan en función del momento en que entran en la cola Y de algún otro valor?

• ¿Puedes utilizar una pila, como la Torre de Hanoi, para crear juegos? ¿Y un juego de restaurante, en el que los clientes tengan que esperar en una cola?