Después de revisar los arrays, diccionarios y los conjuntos llegamos a las pilas y a las colas. Estos tipos de datos son complementarios y tienen una forma muy parecida de trabajar. Sin embargo, los algoritmos internos para su funcionamiento difieren.
Comenzaremos por las definiciones. Las pilas son listas de datos en las que los elementos se agregan al final y se toman del final, se suelen denominar LIFO en inglés que significa Last In, First Out o traducido Último en Entrar, Primero en Salir. Hacen referencia a las pilas de libros o platos. Cuando se acumulan el primero que puedes tomar es el último que se ha depositado.
Las colas también son listas de datos en las que los elementos se agregan al final y se toman del principio. Se suelen denominar FIFO en inglés que significa First In, First Out o traducido Primero en Entrar, Primero en Salir. Un símil muy empleado son las colas de los supermercados o cines.
Creando pilas y colas
El módulo que emplearemos para la creación de los elementos es queue. Este módulo contiene los métodos necesarios para poder hacer pilas, colas e incluso mezclarlas sin ningún problema. La forma en la que podemos crearlo es:
%%% creamos una pila/cola
Queue = queue:new().Gestión de datos: Cola
Comenzaremos por el ejemplo sencillo. El módulo queue dispone de cuatro funciones que permiten agregar y extraer elementos a/de la cola. Según combinemos estas funciones podemos conseguir el comportamiento de una cola o de una pila. Las funciones son:
in/2 : Inserta un elemento al final de la cola.
in_r/2 : Inserta un elemento al principio de la cola.
out/1 : Extrae un elemento del principio de la cola.
out_r/1 : Extrae un elemento del final de la cola.
Esto quiere decir que si empleamos la función para agregar in/2 deberemos emplear la función para extracción out/2 y si empleamos la función de agregación in_r/2 deberemos de emplear la función de extracción out_r/2 para conseguir el comportamiento de una cola. Por tanto:
%% creamos una cola con 3 elementos
QueueIn0 = queue:new().
QueueIn1 = queue:in(1, QueueIn0).
QueueIn2 = queue:in(2, QueueIn1).
QueueIn = queue:in(3, QueueIn2).
%% extraemos elemento a elemento:
{{value, 1}, QueueOut2} = queue:out(QueueIn).
{{value, 2}, QueueOut1} = queue:out(QueueOut2).
{{value, 3}, QueueOut} = queue:out(QueueOut1).
{empty, QueueOut} = queue:out(QueueOut).Gestión de datos: Pilas
Para conseguir el tratamiento de una pila con las funciones anteriores deberemos en este caso mezclarlas. Esto quiere decir que si empleamos la función de agregación in/2 para la extracción deberemos de emplear out_r/1 y si quisiéramos emplear la función de agregación in_r/2 deberíamos de emplear la función de extracción out/1. Veamos un ejemplo:
%% insertamos 3 elementos en la pila:
StackIn0 = queue:new().
StackIn1 = queue:in_r(1, StackIn0).
StackIn2 = queue:in_r(2, StackIn1).
StackIn = queue:in_r(3, StackIn2).
%% extraemos uno a uno:
{{value, 3}, StackOut2} = queue:out(StackIn).
{{value, 2}, StackOut1} = queue:out(StackOut2).
{{value, 1}, StackOut} = queue:out(StackOut1).
{empty, StackOut} = queue:out(StackOut).Otras métodos para Manipulación
Además de las funciones mencionadas, existen las funciones de la API extendida: get/1 y get_r/1. Estas funciones son equivalentes a out/1 y out_r/1 respectivamente. La única diferencia es que las primeras generan una excepción en caso de estar la cola vacía y no eliminan el elemento de la cola. Es decir, solo retornan el elemento no la modificación de la cola. También se puede emplear peek/1 o peek_r/1 que a diferencia de las funciones get/1 y get_r/1 no lanzan una excepción si la cola está vacía, sino que retornan el átomo empty.
Esta API extendida también dispone de otras funciones drop/1 y drop_r/1 que hace la operación complementaria de get/1 y get_r/1 respectivamente. Es decir, eliminan el primer o último elemento de la cola, respecitvamente, y retornan únicamente la cola modificada.
Otras funciones que podemos emplear son las de la API Okasaki. Podemos insertar elementos a la cola con scons/2 o cons/2 teniendo el mismo resultado que in/2 y in_r/2 respectivamente. La lectura podemos realizarla con las funciones head/1 que nos proporciona el primer elemento y last/1 que nos proporciona el último.
Las funciones liat/1 y tail/1 son las equivalentes a drop/1 y drop_r/1.
Filtrado y comprobaciones
En el módulo disponemos de funciones que nos permiten saber si se trata de una cola como is_queue/1 o si está vacía con is_empty/1. También podemos preguntar el tamaño de la cola con len/1 o si un elemento es miembro de la cola con member/2.
NOTA: todas estas funciones son pertenecientes al módulo queue por lo que no se pueden emplear para las guardas.
El filtrado podemos realizarlo con filter/2. El filtrado nos puede ser útil para tratar con los datos como si fuesen una lista. Si hemos agregado una serie de elementos y queremos eliminar unos que cumplan una serie de condiciones podemos realizarlo a través del filtro. Por ejemplo:
%% Insertamos 3 elementos:
QueueIn0 = queue:new().
QueueIn1 = queue:in(1, QueueIn0).
QueueIn2 = queue:in(2, QueueIn1).
QueueIn = queue:in(3, QueueIn2).
%% Filtramos para eliminar los impares:
QueuePares = queue:filter(fun(X) ->
X rem 2 =:=
end, QueueIn).
% [2]
%% Filtramos para multiplicar por 2 los pares:
Queue2xPares = queue:filter(fun
(X) when X rem 2 =:= -> [2 * X];
(X) -> true
end, QueueIn).
% [1,4,3]El filtrado de queue nos permite no solo decir si un elemento se queda o no sino también si queremos cambiarlo por otro o incluso por varios elementos en lugar de solo uno, ya que se retorna una lista de valores.
También comentar que existen join/2 para unir dos colas en una sola colocando la cola del primer parámetro como la primera y la cola del segundo parámetro a continuación de esta. La función split/2 sirve para lo contrario. Dado un número y una cola, parte la cola en dos. Una con el tamaño indicado en el primer parámetro y la otra con el resto de elementos.
Conversiones
Como viene siendo costumbre, estos tipos de datos se pueden convertir en listas de elementos. Por tanto, existen las funciones típicas: to_list/1 y from_list. Estas funciones nos pueden ser de ayuda si queremos realizar acciones más complejas con las pilas/colas.
Conclusiones
El uso de la pila y cola a través de estas funciones y el filtrado que proponen así como la comprobación de membresía hace que muchos algoritmos básicos sean fáciles de implementar en Erlang. Otra estructura de datos a tener en cuenta en nuestros programas.
