Los desarrolladores utilizan los arrays y las variantes de listas enlazadas para construir una gran variedad de estructuras de datos complejas. Las Pilas, las Colas .
Pilas
La Pila es una estrucutra de datos donde las inserciones y recuperaciones/borrados de datos se hacen en uno de los finales, que es conocido como el top de la pila. Como el último elemento insertado es el primero en recuperarse/borrarse, los desarrolladores se refieren a estas pilas como pilas LIFO (last-in, first-out).
Los datos se push (insertan) dentro y se pop (recuperan/borran) de la parte superior de la pila. La siguiente figura ilustra una pila con tres String cada uno insertado en la parte superior de la pila:
Como muestra la figura anterior, las pilas se construyen en memoria. Por cada dato insertado, el itém superior anterior y todos los datos inferiores se mueven hacia abajo. Cuando llega el momento de sacar un ítem de la pila, se recpupera y se borra de la pila el ítem superior (que en la figura anterior se revela como "third").
Las pilas son muy útiles en varios escenarios de programación. Dos de los más comunes son:
- Pilas que contienen direcciones de retorno:
Cuando el código llama a un método, la dirección de la primera instrucción que sigue a la llamada se inserta en la parte superior de la pila de llamadas de métodos del thread actual. Cuando el método llamado ejecuta la instrucción return, se saca la dirección de la parte superior de la pila y la ejecución continúa en sa dirección. Si un método llama a otro método, el comportamiento LIFO de la pila asegura que la instrucción return del segundo método transfiere la ejecución al primer método, y la del primer método transfiere la ejecución al código que sigue al código que llamó al primer método. Como resultado una pila "recuerda" las direcciones de retorno de los métodos llamados. - Pilas que contienen todos los parámetros del método llamado y las variables locales:
Cuando se llama a un método, la JVM reserva memoria cerca de la dirección de retorno y almacena todos los parámetros del método llamado y las variables locales de ese método. Si el método es un método de ejemplar, uno de los parámetros que almacena en la pila es la referencia this del objeto actual.
Es muy común implementar una pila utilizando un array uni-dimensional o una lista de enlace simple. En el escenario del array uni-dimensional, una variable entera, típicamente llamada top, contiene el índice de la parte superior de la pila. De forma similar, una variable de referencia, también nombrada noramlmente como top, referencia el nodo superior del escenario de la lista de enlace simple.
He modelado mis implementaciones de pilas después de encontrar la arquitectura del API Collections de Java. Mis implementaciones constan de un interface Stack para una máxima flexibilidad, las clases de implementación ArrayStack yLinkedListStack, y una clase de soporte FullStackException. Para facilitar su distribución, he empaquetado estas clases en un paquete llamado com.javajeff.cds, donde cds viene de estructura de datos complejas. El siguiente listado presenta el interfaceStack:
// Stack.java
package com.javajeff.cds;
public interface Stack {
boolean isEmpty ();
Object peek ();
void push (Object o);
Object pop ();
}
Sus cuatro métodos determinan si la pila está vacía, recuperan el elemento superior sin borrarlo de la pia, situan un elemento en la parte superior de la pila y el último recuera/borra el elemento superior. Aparte de un constructor específico de la implementación, su programa únicamente necesita llamar a estos métodos.
El siguiente listado presenta una implementación de un Stack basado en un array uni-dimensional:
// ArrayStack.java
package com.javajeff.cds;
public class ArrayStack implements Stack {
private int top = -1;
private Object [] stack;
public ArrayStack (int maxElements) {
stack = new Object [maxElements];
}
public boolean isEmpty () {
return top == -1;
}
public Object peek () {
if (top < 0)
throw new java.util.EmptyStackException ();
return stack [top];
}
public void push (Object o) {
if (top == stack.length - 1)
throw new FullStackException ();
stack [++top] = o;
}
public Object pop () {
if (top < 0)
throw new java.util.EmptyStackException ();
return stack [top--];
}
}
ArrayStack revela una pila como una combinación de un índice entero privado top y variables de referencia de un array uni-dimensional stack. top identifica el elemento superior de la pila y lo inicializa a -1 para indica que la pila está vacía. Cuando se crea un objeto ArrayStack llama a public ArrayStack(int maxElements) con un valor entero que representa el número máximo de elementos. Cualquier intento de sacar un elemento de una pila vacía mediante pop() resulta en el lanzamiento de unajava.util.EmptyStackException. De forma similar, cualquier intento de poner más elementos de maxElements dentro de la pila utilizando push(Object o) lanzará una FullStackException, cuyo código aparece en el siguiente listado:
// FullStackException.java
package com.javajeff.cds;
public class FullStackException extends RuntimeException {
}
Por simetría con EmptyStackException, FullStackException extiende RuntimeException. Como resultado no se necesita añadirFullStackException a la clausula throws del método.
El siguiente listado presenta una implementación de Stack utilizando una lista de enlace simple:
// LinkedListStack.java
package com.javajeff.cds;
public class LinkedListStack implements Stack {
private static class Node {
Object o;
Node next;
}
private Node top = null;
public boolean isEmpty () {
return top == null;
}
public Object peek () {
if (top == null)
throw new java.util.EmptyStackException ();
return top.o;
}
public void push (Object o) {
Node temp = new Node ();
temp.o = o;
temp.next = top;
top = temp;
}
public Object pop () {
if (top == null)
throw new java.util.EmptyStackException ();
Object o = top.o;
top = top.next;
return o;
}
}
LinkedListStack revela una pila como una combinación de una clase anidada privada de alto nivel llamada Node y una variable de referencia privada top que se inicialia a null para indicar una pila vacía. Al contrario que su contrapartida del array uni-dimensional,LinkedListStack no necesita un constructor ya que se expande dinámicamente cuando se ponen los ítems en la pila. Así, void push(Object o) no necesita lanzar una FullStackException. Sin embargo, Object pop() si debe chequear si la pila está vacía, lo que podría resultar en el lanzamiento de una EmptyStackException.
Ahora que ya hemos visto el interface y las tres clases que generan mis implementaciones de las pilas, juguemos un poco. El siguiente listado muestra casi todo el soporte de pilas de mi paquete com.javajeff.cds:
// StackDemo.java
import com.javajeff.cds.*;
class StackDemo {
public static void main (String [] args) {
System.out.println ("ArrayStack Demo");
System.out.println ("---------------");
stackDemo (new ArrayStack (5));
System.out.println ("LinkedListStack Demo");
System.out.println ("--------------------");
stackDemo (new LinkedListStack ());
}
static void stackDemo (Stack s) {
System.out.println ("Pushing \"Hello\"");
s.push ("Hello");
System.out.println ("Pushing \"World\"");
s.push ("World");
System.out.println ("Pushing StackDemo object");
s.push (new StackDemo ());
System.out.println ("Pushing Character object");
s.push (new Character ('C'));
System.out.println ("Pushing Thread object");
s.push (new Thread ("A"));
try {
System.out.println ("Pushing \"One last item\"");
s.push ("One last item");
}
catch (FullStackException e) {
System.out.println ("One push too many");
}
System.out.println ();
while (!s.isEmpty ())
System.out.println (s.pop ());
try {
s.pop ();
}
catch (java.util.EmptyStackException e) {
System.out.println ("One pop too many");
}
System.out.println ();
}
}
Cuando se ejecuta StackDemo, produce la siguiente salida:
ArrayStack Demo --------------- Pushing "Hello" Pushing "World" Pushing StackDemo object Pushing Character object Pushing Thread object Pushing "One last item" One push too many Thread[A,5,main] C StackDemo@7182c1 World Hello One pop too many LinkedListStack Demo -------------------- Pushing "Hello" Pushing "World" Pushing StackDemo object Pushing Character object Pushing Thread object Pushing "One last item" One last item Thread[A,5,main] C StackDemo@cac268 World Hello One pop too many
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 tabajan con 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 incio 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 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.
| Nota: |
|---|
| Para señalar que la cola lineal está vacía, no necesita gastar una posición, aunque esta aproximación algunas veces es muy conneniente. En su lugar asigne el mismo valor que indique una posición no existente a front y a rear. Por ejemplo, asumiendo una implementación basada en un array uni-dimensional, front y rear podrían contener -1. El índice 0 indica entonces la posición más a la izquierda, y los datos se insertarán empezando en este índice.
Cuando rear identifique la posición más a la derecha, la cola lineal podría no estar llena porque front podría haber avanzado almenos una posición para recuperar/borrar un dato. En este esceario, considere mover todos los ítems de datos hacia la izquierda y ajuste la posición de front y rear de la forma apropiada para crear más espacio. Sin embargo, demasiado movimiento de datos puede afectar al rendimiento, por eso debe pensar cuidadosamente en los costes de rendimiento si necesita crear más espacio.
|
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 direción (para identificar la posición que contendrá el nuevo entero). Al igual que con la cola lineal, la razon 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, entre los 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 que un 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 colas deben 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 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 deQueue.
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];
}
}
ArrayLinearQueue revela que una cola es una combinación de variables privadas front, rear, y queue. front y rear se inicializan a -1 para indicar una cola vacía. Igual que el constructor de ArrayStack llama a public ArrayLinearQueue(int maxElements)con un valor entero que especifique el número máximo de elementos durante la construcción de un objeto ArrayLinearQueue.
El método insert(Object o) de ArrayLinearQueue lanza una FullQueueException cuando rear identifica el elemento final del array uni-dimensional. El código de FullQueueException aparece en el siguiente listado:
// FullQueueException.java
package com.javajeff.cds;
public class FullQueueException extends RuntimeException {
}
El método remove() de ArrayLinearQueue lanza una EmptyQueueException cuando los objetos front y rear son iguales. El siguiente listado presenta el código de esta clase:
// EmptyQueueException.java
package com.javajeff.cds;
public class EmptyQueueException extends RuntimeException {
}
El siguiente listado presenta una implementación de Queue para una cola circular basada en un array uni-dimensional:
// ArrayCircularQueue.java
package com.javajeff.cds;
public class ArrayCircularQueue implements Queue {
private int front = 0, rear = 0;
private Object [] queue;
public ArrayCircularQueue (int maxElements) {
queue = new Object [maxElements];
}
public void insert (Object o) {
int temp = rear;
rear = (rear + 1) % queue.length;
if (front == rear) {
rear = temp;
throw new FullQueueException ();
}
queue [rear] = o;
}
public boolean isEmpty () {
return front == rear;
}
public boolean isFull () {
return ((rear + 1) % queue.length) == front;
}
public Object remove () {
if (front == rear)
throw new EmptyQueueException ();
front = (front + 1) % queue.length;
return queue [front];
}
}
ArrayCircularQueue revela una implementación, en terminos de variables privadas y un constructor, muy similar aArrayLinearQueue. El método insert(Object o) es interesante porque guarda el valor actual de rear antes de hacer que esa variable apunte a la siguiente posición. Si la cola circular está llena, rear restaura su valor original antes de lanzar unaFullQueueException. La restauración de rear es necesaria porque front es igual a rear (en ese punto), y una subsecuente llamada a remove() resulta en la lanzamiento de una EmptyQueueException (incluso aunque la cola circular no esté vacía).
Después de estudiar el código del interface y de varias clases que lo implementan basándose en arrays uni-dimensionales
