PDF de programación - Unidades IV y Y - Pilas y Colas

Unidades IV y V - Pilas y Colas



• Pilas que "Recuerdan"
• Priorizar con Colas



Java en castellano (Tutorial Estructuras de Datos y Algoritmos en Java)
http://www.programacion.com/java/tutorial/jap_data_alg/

Tutorial original en Inglés
http://www.javaworld.com/



Pilas y Colas

Los desarrolladores utilizan los arrays y las variantes de listas enlazadas para construir una gran variedad
de estructuras de datos complejas. Esta página explora dos de esas estructuras: las Pilas, las Colas.
Cuando presentemos los algoritmos lo haremos únicamente en código Java por motivos de brevedad.

Pilas que "Recuerdan"

La Pila es una estructura 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 ítem
superior anterior y todos los datos inferiores se mueven hacia abajo. Cuando llega el momento de sacar
un ítem de la pila, se recupera 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 esa 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 normalmente
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 una interfase 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 la interfase 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 pila,
sitúan un elemento en la parte superior de la pila y el último recuerda/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 cláusula 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 inicializa 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 la interfase 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