Pilas y Colas (Programacion)

COLAS
La Cola es una estructura de datos donde la inserción de ítem se hace en un final (el fin de la cola) y la recuperación/borrado de elementos se hace en el otro final (el inicio de la cola). Como el primer elemento insertado es el primero en ser recuperado, los desarrolladores se refieren a estas colas como estructuras FIFO (first-in, first-out).
Normalmente los desarrolladores trabajancon dos tipos de colas: lineal y circular. En ambas colas, la inserción de datos se realiza en el fin de la cola, se mueven hacia adelante y se recuperan/borran del inicio de la cola. 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 adicionalesporque 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, frontavanza una posición hacia la derecha.
La cola circular de la figura anterior tiene siete datos enteros, con el entero 1 primero. Esta cola está llena y no puede almacenar más datos hasta que front avance una posición en sentido horario (para recuperar el entero 1) y rear avance una posición en la misma dirección (para identificar la posición que contendrá el nuevo entero). Al igual que con la colalineal, la razón de la posición vacía, que identifica front, implica el comportamiento circular de la cola. Inicialmente, front y rear identifican la misma posición, lo que indica una cola vacía. Entonces rear avanza una posición por cada nueva inserción. De forma similar, front avanza una posición por cada recuperación/borrado.
Las colas son muy útiles en varios escenarios de programación, entrelos que se encuentran:
• Temporización de Threads:
Una JVM o un sistema operativo subyacente podrían establecer varias colas para coincidir con diferentes prioridades de los threads. La información del thread se bloquea porque todos los threads con una prioridad dada se almacenan en una cola asociada.
• Trabajos de impresión:
Como una impresora normalmente es más lenta queun ordenador, un sistema operativo maneja los trabajos de impresión en un subsistema de impresión, que inserta esos trabajos de impresión en una cola. El primer trabajo en esa cola se imprime primero, y así sucesivamente.
Los desarrolladores normalmente utilizan una array uni-dimensional para implementar una cola. Sin embargo, si tienen que co-existir múltiple colas o las inserciones en las colasdeben ocurrir en posiciones distintas a la última por motivos de prioridades, los desarrolladores suelen cambiar a la lista doblemente enlazada. Con un array uni-dimensional dos variables enteras (normalmente llamadas front y rear) contienen los índices del primer y último elemento de la cola, respectivamente. Mis implementaciones de colas lineales y circulares usan un array uni-dimensional yempiezan 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 dela 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 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;...