Pilas Y Colas Estructura De Datos

Pilas y Colas

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

...