Pilas y colas

Información general

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

• Pila: un contenedor en el que se añaden y eliminan elementos siguiendo el orden FILO (primero en entrar, último en salir), como cuando se saca un libro de una pila para leerlo.

• Cola: un contenedor en el que se añaden y eliminan elementos siguiendo el orden FIFO (primero en entrar, primero en salir), como cuando se procesa una cola de clientes que esperan una comida.

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 panqueques. Imagina que desayunas en un restaurante y el camarero te sirve una pila interminable de panqueques. Como es de buena educación, solo tomarás uno a la vez, y solo de la parte superior de la pila. Puedes pedirle al camarero que empuje un nuevo panqueque a la parte superior de la pila, y cuando tengas hambre puedes quitar un panqueque de la parte superior de la pila y ponerlo en tu plato para comértelo. Si quieres comerte un panqueque específico de la mitad de la pila, tendrás que seguir comiendo panqueques de la parte superior hasta que llegues al que quieres. El primer panqueque añadido será el último que quites. Esto hace que una pila sea una estructura de datos FILO, o primero en entrar, último en salir.

Cuándo usarlas

Las pilas son útiles cuando necesitas retroceder, o recordar en qué orden se realizaron los eventos. Puede ser una función de deshacer, una cadena de eventos o una serie de elecciones. Por ejemplo, quizás tengas un robot que necesita resolver un laberinto con caminos ramificados. Cuando el robot llega a una ramificación en el laberinto, elige un camino y lo empuja a la pila. Cuando llega a un callejón sin salida, regresa por la pila, quitando opciones hasta que encuentra un nuevo camino que puede tomar.

Implementación en Verse

La API de Verse no tiene una implementación integrada de las pilas, pero puedes crear una por tu cuenta.

Puedes representar los elementos de una pila utilizando cualquier estructura de datos ordenada, como una matriz o una lista enlazada. En este ejemplo, usarás una matriz, ya que te da fácil acceso a la parte superior de la pila.

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

La matriz de elementos 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. El uso de type como argumento para la clase pila 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 utilizar Push() y Pop() elementos de ella. 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 Size() simplemente devuelve la longitud de la matriz de elementos. 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 en el índice superior (Longitud - 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 usar una función constructor. Un constructor es una función especial que crea una instancia de la clase a la que está asociado. La función constructor establece los valores iniciales de un objeto y te permite acceder al valor de elementos 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 empujar y quitar de las pilas

Para añadir y eliminar elementos de la pila, es necesario empujar el nuevo elemento a la parte superior de la pila, o quitarlo 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 en la parte superior de la pila y devuelve una nueva pila con el elemento en la parte superior. Devolver una nueva pila en lugar de modificar la pila actual es un ejemplo de programación funcional y reduce el riesgo de que se produzcan efectos secundarios.

Para implementar la función Pop(), primero necesitas encontrar el elemento en la parte superior de la pila usando Peek(). A continuación, debes 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 muestra el código completo de la clase pila.

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 en una cinta transportadora de sushi. Supongamos que estás en un restaurante de sushi que te envía platos de sushi de uno a la vez por una cinta transportadora, y que llegan en el orden en que se pidieron. Puedes sacar de la cola el plato que está al principio de la cola para tomarlo y comértelo, pero solo puedes tomar un plato cada vez. Si quieres pedir otro plato, pídele al cocinero que lo ponga en cola al final. Si en la cola ya hay otros platos de sushi, tendrás que seguir comiendo platos de los primeros de la cola hasta llegar al plato del final. El primer plato de sushi que añadas será el primero que quites. Esto hace que una cola sea una estructura de datos FIFO, o primero en entrar, primero en salir.

Cuándo usarlas

Las colas son útiles cuando se necesita procesar datos en función del momento en que llegan. Esto podría ser servir a los clientes mediante una ventanilla de autoservicio, ordenar las llamadas en un centro de llamadas o formular al jugador una serie de preguntas en una entrevista. Por ejemplo, si necesitas crear una sala de espera para que los jugadores vayan mientras realizan una tarea o atraviesan una experiencia de a uno, puedes 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 las colas, pero puedes crear una por tu cuenta.

Al igual que las pilas, puedes representar los elementos de la cola utilizando cualquier estructura de datos ordenada, como una matriz o una lista enlazada. En este ejemplo, usarás una matriz ya que te da fácil acceso tanto al principio como al final de la cola. Para implementar una cola con una lista enlazada, consulta este fragmento de código.

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

La matriz de elementos almacena los objetos en la cola del tipo t. Esto significa que puedes inicializar una cola con cualquier tipo de elemento, como int, float, queue, etc. El uso de type como argumento para la clase pila 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án el principio y el final de la cola para poder ejecutar Enqueue() y Dequeue(). También es útil saber el tamaño de la cola y si está vacía. Definirás esto 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 Size() devuelve la longitud de la matriz de elementos. 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 a los índices del principio (índice 0) y del final (longitud - 1) de la matriz de los elementos. Ambas funciones tienen los especificadores <decides><transacts>, ya que el acceso a la matriz puede fallar si la matriz está vacía.

Al igual que la clase stack, queue también tiene que utilizar una función de constructor para asignar la matriz de elementos. La función constructor te permite acceder al valor de elementos 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 poner elementos en cola y sacarlos de ella

Para añadir y eliminar elementos de la cola, es necesario poner en cola el nuevo elemento en la parte final de la cola, o sacarlo de la cola desde la parte superior.

# 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 añadir a la cola y devuelve una nueva cola con el nuevo elemento en la parte final. Devolver una nueva cola en lugar de modificar la cola actual es un ejemplo de programación funcional y reduce el riesgo de que se produzcan efectos secundarios.

Para la función Dequeue(), necesitas eliminar y devolver el elemento a la parte del principio de la cola y devolver una nueva cola con el primer elemento eliminado (mediante 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 muestra el código completo de la clase cola.

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

Existen varias formas de iterar y mejorar las pilas y las colas, por lo que deberías explorar diferentes maneras de añadir funcionalidad. Para empezar, te presentamos las siguientes ideas:

• ¿Puedes convertir una cola en una cola circular, donde el último elemento se conecta al primer elemento y la cola sigue en bucle?

• ¿Qué pasa con la cola de prioridades, en la cual los objetos se ordenan en base al momento en el que entran a la cola ADEMÁS de algún otro valor?

• ¿Puedes crear juegos mediante una pila, como la Torre de Hanói? ¿Qué te parece un juego de restaurante, en el que los clientes hagan una cola?