Resumen
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 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. El uso de type como argumento para la clase pila es un ejemplo de tipo paramétrico.
Definamos primero algunas funciones de ayuda. Necesitas saber dónde está la parte superior de la pila para que puedas utilizar Push() y Pop() en sus elementos. Para ello, necesitarás tres funciones, Size(), IsEmpty(), y Peek().
# Devuelve el tamaño de la pila.
Size<public>()<transacts>:int=
Elements.Length
# Tiene éxito si la pila está vacía.
IsEmpty<public>()<decides><transacts>:void=
Size() = 0
# Devuelve el elemento superior de la pila.
Peek<public>()<decides><transacts>:t=
Elements[Elements.Length - 1]
La función Size() solo devuelve la 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 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 se puede 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 permite acceder al valor de Elements y asignarlo a una matriz inicial de elementos.
# Crea y devuelve una pila a partir de una matriz inicial de elementos InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
Elements := InitialElements
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" desde la parte superior.
# Añade el NewElement a la parte superior de la pila devolviendo una nueva
# pila con NewElement en la parte superior
Push<public>(NewElement:t):stack(t)=
stack(t){Elements := Elements + array{NewElement}}
# Elimina el elemento de la parte superior de la pila y devuelve una tupla de una nueva
# pila con el elemento superior eliminado y el elemento eliminado.
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{}
# Añade el NewElement a la parte superior de la pila devolviendo una nueva
# pila con NewElement en la parte superior
Push<public>(NewElement:t):stack(t)=
stack(t){Elements := Elements + array{NewElement}}
# Elimina el elemento de la parte superior de la pila y devuelve una tupla de una nueva
# pila con el elemento superior eliminado y el elemento eliminado.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
FirstElement := Peek[]
(stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)
# Devuelve el tamaño de la pila.
Size<public>()<transacts>:int=
Elements.Length
# Tiene éxito si la pila está vacía.
IsEmpty<public>()<decides><transacts>:void=
Size() = 0
# Devuelve el elemento superior de la pila.
Peek<public>()<decides><transacts>:t=
Elements[Elements.Length - 1]
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 utilizando una lista enlazada, consulta este fragmento de código.
queue<public>(t:type) := class:
Elements<internal>:[]t = array{}
La matriz Elements 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.
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().
# Devuelve el tamaño de la cola
Size<public>()<transacts>:int=
Elements.Length
# Tiene éxito si la cola está vacía.
IsEmpty<public>()<decides><transacts>:void=
Size() = 0
# Devuelve el elemento al principio de la cola.
Front<public>()<decides><transacts>:t=
Elements[0]
# Devuelve el elemento al final de la cola.
Rear<public>()<decides><transacts>:t=
Elements[Elements.Length - 1]
La función Size() devuelve la 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 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 Elements. La función constructor te permite acceder al valor de Elements y asignarlo a una matriz inicial de elementos.
# Crea y devuelve una cola a partir de una matriz inicial de elementos InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
Elements := InitialElements
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.
# Añade el elemento nuevo a la parte final de la cola mediante la devolución
# de una nueva cola con NewElement al final.
Enqueue<public>(NewElement:t):queue(t)=
queue(t){Elements := Elements + array{NewElement}}
# Elimina el elemento del principio de la cola y devuelve una tupla
# de una nueva cola con el elemento eliminado.
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 de fallo 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{}
# Añade el elemento nuevo a la parte final de la cola mediante la devolución
# de una nueva cola con NewElement al final.
Enqueue<public>(NewElement:t):queue(t)=
queue(t){Elements := Elements + array{NewElement}}
# Elimina el elemento del principio de la cola y devuelve una tupla
# de una nueva cola con el elemento eliminado.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
FirstElement := Front[]
(queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)
# Devuelve el tamaño de la cola
Size<public>()<transacts>:int=
Elements.Length
# Tiene éxito si la cola está vacía.
IsEmpty<public>()<decides><transacts>:void=
Size() = 0
# Devuelve el elemento al principio de la cola.
Front<public>()<decides><transacts>:t=
Elements[0]
# Devuelve el elemento al final de la cola.
Rear<public>()<decides><transacts>:t=
Elements[Elements.Length - 1]
# Crea y devuelve una cola a partir de una matriz inicial de elementos InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
Elements := InitialElements
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?