Colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.
Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

La siguiente figura ilustra las colas lineal y circular:

La cola lineal de la figura anterior almacena cuatro enteros, con el entero 1 en primer lugar. Esa cola está llena y no puede almacenar más datos adicionales porque rear identifica la parte final de la cola. La razón de la posición vacía, que identifica front, implica el comportamiento lineal de la cola. Inicialmente, front y rear identifican la posición más a la izquierda, lo que indica que la cola está vacía. Para almacenar el entero 1, rear avanza una posición hacia la derecha y almacena 1 en esa posición. Para recuperar/borrar el entero 1, front avanza una posición hacia la derecha.

• Crear: se crea la cola vacía.
• Enqueue (añadir, entrar, push): se añade un elemento a la cola. Se añade al final de esta.
• Dequeue (sacar, salir, pop): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primero elemento que entró.

El siguiente listado presenta una a implementación de Queue de una cola lineal 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 EmptyQueueException ();
return queue [++front];
}
}

[+/-] Ejemplo...