Queue

La interfaz Queue habilita las operaciones adicionales de inserción, extración e inspección . Los elementos en una cola Queue se ordenan típimamente en una base FIFO. El segundo árbol inicia con la interfaz Map, la cual mapea claves y valores similarmente a una tabla de identificadores Hashtable.
Un uso ideal de LinkedList es para la creación de “colas”, en las que los elementos se añaden alfinal, y se eliminal del comienzo. Para este uso se puede usar, en vez de List, la interfaz Queue (también implementada por LinkedList) que es más específica para esta tarea.
Queue y Deque
Se conoce como cola a una colección especialmente diseñada para ser usada como almacenamiento temporario de objetos a procesar. Las operaciones que suelen admitir las colas son “encolar”, “obtener siguiente”,etc. Por lo general las colas siguen un patrón que en computación se conoce como FIFO (por la sigla en inglés de “First In - First Out” - “lo que entra primero, sale primero”), lo que no quiere decir otra cosa que lo obvio: El orden en que se van obteniendo los “siguientes” objetos coincide con el orden en que fueron introducidos en la cola. Esto análogo a su tocaya del supermercado: La gente quehace la cola va siendo atendida en el orden en que llegó a ésta.
Hasta hace poco, para implementar una cola FIFO en Java la única opción provista por la biblioteca de colecciones era LinkedList. Como ya se dijo más arriba, esta implementación ofrece una implementación eficiente de las operaciones “poner primero” y “sacar último”. Sin embargo, aunque la implentación es la correcta, a nivel deinterfaz dejaba algo que desear. Los métodos necesarios para usar una LinkedList como una cola eran parte solamente de la clase LinkedList, no existía ninguna interfaz que abstraiga el concepto de “cola”. Esto hacía imposible crear código genérico que use indistintamente diferentes implementaciones de colas (que por ejemplo no sean FIFO sino que tengan algún mecanismo de prioridades). Esta situacióncambió recientemente a partir del agregado a Java de dos interfaces expresamente diseñadas para el manejo de colas: La interfaz Queue tiene las operaciones que se esperan en una cola. También se creó Deque, que representa a una “double-ended queue”, es decir, una cola en la que los elementos pueden añadirse no solo al final, sino también “empujarse” al principio.
Mis implementaciones de colaslineales y circulares usan un array uni-dimensional y empiezan con el interface Queue que puede ver en el siguiente listado:
// Queue.java

package com.javajeff.cds;

public interface Queue {
void insert (Object o);
boolean isEmpty ();
boolean isFull();
Object remove ();
}
Queue declara cuatro métodos para almacenar un datos, determinar si la cola está vacía, determinar si la cola está llena y recuperar/borrar un dato de la cola. Llame a estos métodos (y a un constructor) para trabajar con cualquier implementación de Queue.
El siguiente listado presenta una a implementación de Queue de una colalineal basada en un array uni-dimensional:
// ArrayLinearQueue.java

package com.javajeff.cds;

public class ArrayLinearQueue implements Queue {
private int front = -1, rear = -1;
private Object [] queue;

public ArrayLinearQueue (int maxElements) {
queue = new Object [maxElements];
}

public void insert (Object o) {
if (rear ==queue.length - 1)
throw new FullQueueException ();
queue [++rear] = o;
}

public boolean isEmpty () {
return front == rear;
}

public boolean isFull () {
return rear == queue.length - 1;
}

public Object remove () {
if (front == rear)
throw new...