Los desarrolladores utilizan los arrays y las variantes de listas enlazadas para construir una gran variedad de estructuras de datos complejas. Este p�gina explora dos de esas estructuras: las Pilas, las Colas . Cuando presentemos los algoritmos lo haremos �ncamente en c�digo Java por motivos de brevedad.
�Pilas que "Recuerdan"
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 y LinkedListStack, 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 interface Stack:
// 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 una java.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�adir FullStackException 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
�Priorizar con 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 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;
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 a ArrayLinearQueue. 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 una FullQueueException. 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, consideremos en el siguiente listado una aplicaci�n que demuestra las colas lineales y circulares:
// QueueDemo.java
import com.javajeff.cds.*;
class QueueDemo {
public static void main (String [] args) {
System.out.println ("ArrayLinearQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayLinearQueue (5));
System.out.println ("ArrayCircularQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayCircularQueue (6)); // Need one more slot because
// of empty slot in circular
// implementation
}
static void queueDemo (Queue q) {
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
System.out.println ("Inserting \"This\"");
q.insert ("This");
System.out.println ("Inserting \"is\"");
q.insert ("is");
System.out.println ("Inserting \"a\"");
q.insert ("a");
System.out.println ("Inserting \"sentence\"");
q.insert ("sentence");
System.out.println ("Inserting \".\"");
q.insert (".");
try {
System.out.println ("Inserting \"One last item\"");
q.insert ("One last item");
}
catch (FullQueueException e) {
System.out.println ("One insert too many");
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
}
System.out.println ();
while (!q.isEmpty ())
System.out.println (q.remove () + " [Is empty = " + q.isEmpty () +
", Is full = " + q.isFull () + "]");
try {
q.remove ();
}
catch (EmptyQueueException e) {
System.out.println ("One remove too many");
}
System.out.println ();
}
}
Cuando se ejecuta QueueDemo, se produce la siguiente salida:
ArrayLinearQueue Demo --------------------- Is empty = true Is full = false Inserting "This" Inserting "is" Inserting "a" Inserting "sentence" Inserting "." Inserting "One last item" One insert too many Is empty = false Is full = true This [Is empty = false, Is full = true] is [Is empty = false, Is full = true] a [Is empty = false, Is full = true] sentence [Is empty = false, Is full = true] . [Is empty = true, Is full = true] One remove too many ArrayCircularQueue Demo --------------------- Is empty = true Is full = false Inserting "This" Inserting "is" Inserting "a" Inserting "sentence" Inserting "." Inserting "One last item" One insert too many Is empty = false Is full = true This [Is empty = false, Is full = false] is [Is empty = false, Is full = false] a [Is empty = false, Is full = false] sentence [Is empty = false, Is full = false] . [Is empty = true, Is full = false] One remove too many