UNIVERSIDAD DE LA SABANA FACULTAD DE INGENIERIA

ASIGNATURA: ESTRUCTURAS DE DATOS PROFESOR: EDUARDO ROBAYO

ESTRUCTURA DE DATOS: PILA

Concepto de PILA Una PILA es una estructura de datos que se comporta muy parecido al hecho de apilar elementos sobre una mesa, como por ejemplo apilar camisas una sobre otra, o apilar platos uno sobre otro, en ese caso, si se desea obtener el primer elemento que fue colocado en la pila, entonces es necesario remover los que estn sobre l. En una PILA, el ltimo elemento aadido siempre ser colocado en el TOPE de la PILA. La estructura de PILA es conocida como una estructura LIFO (Last In First Out, primero en entrar ltimo en salir). Las tres funciones que se pueden realizar en una PILA son:

- Insertar elementos en el TOPE - Eliminar elementos del TOPE - Buscar los elementos de la PILA

Vamos a crear una Pila haciendo uso de las listas enlazadas, analizando los algoritmos de las tres funciones anteriores.

Investigue: Se puede implementar la estructura de PILA con el uso de Vectores.

CODIGO

1 EMPEZAR LA PILA Crear la clase Nodo

Con un atributo ENTERO Con un apuntador a Nodo sig

Crear el Nodo raiz, ya en la Pila, el cual empieza apuntado a Null en el constructor de la Pila

public class Pila {

class Nodo {

int info;

Nodo sig;

}

private Nodo raiz;

public Pila () {

raiz=null;

}

2 EL METODO INSERTAR Construyamos el mtodo insertar Crear un nuevo nodo para almacenar un nuevo entero

public void insertar(int x) {

Nodo nuevo;

nuevo = new Nodo();

nuevo.info = x;

Si el nodo raz est apuntado a Null, entonces el nodo nuevo debe apuntar a null, y raz debe apuntar a nuevo

Si el nodo raz no est apuntado a null, entonces el nuevo nodo debe apuntar a raz, y el nodo nuevo pasa a ser raz.

if (raiz==null)

{

nuevo.sig = null;

raiz = nuevo;

}

else

{

nuevo.sig = raiz;

raiz = nuevo;

}

}

3 EL METODO EXTRAER Si raz NO apunta a null, es porque la pila NO ESTA VACIA, entonces raz debe apuntarle al siguiente nodo.

Si raz SI est apuntado a null, es porque la pila est vaca, entonces no se puede borrar ningn nodo.

public int extraer ()

{

if (raiz!=null)

{

int informacion =

raiz.info;

raiz = raiz.sig;

return informacion;

}

else

{

int valor = 99999;

return valor; //retorna

cualquier valor

}

}

4 EL METODO IMPRIMIR Para recoger la PILA, se puede crear un nodo temporal que servir de PIVOTE. Este nodo pivote recorrer la PILA desde RAIZ, hasta el ltimo nodo el cual apunta a null.

public void imprimir() {

Nodo reco=raiz;

System.out.println("Listado de

todos los elementos de la

pila.");

while (reco!=null) {

System.out.print(reco.info+"-

");

reco=reco.sig;

}

System.out.println();

}

5 EL METODO MAIN Probemos el funcionamiento de la PILA insertando y eliminando elementos.

public static void

main(String[] ar) {

Pila pila1=new Pila();

pila1.insertar(10);

pila1.insertar(40);

pila1.insertar(3);

pila1.imprimir();

System.out.println("Extraemos

de la pila:"+pila1.extraer());

pila1.imprimir();

}

}

6 CONTAR LOS NODOS DE LA PILA Para contar la cantidad de nodos en la pila, es necesario: Inicializar una variable para contar e incrementarla cada vez que pasa a un nodo. Recorrer la pila desde la raz usando un nodo temporal.

public int cantidad() {

int cant=0;

Nodo reco=raiz;

while (reco!=null) {

cant++;

reco=reco.sig;

}

return cant;

}

7 AVERIGUAR SI LA PILA ESTA VACIA El detalle que indica si una pila est vaca es si el nodo raz est apuntado a null. El mtodo devuelve true si el nodo raz est apuntando a null.

public boolean vacia() {

if (raiz==null) {

return true;

} else {

return false;

}

}

8 UN METODO UTIL, CONOCER EL PRIMER NODO. Recordemos que debemos empezar siempre por el nodo RAIZ, entonces, la solucin es mostrar la informacin del nodo al que apunta precisamente el nodo RAIZ, la informacin del nodo siguiente. Tener en cuenta que si la PILA ESTA VACIA se debe retornar un cdigo de error, por ejemplo Integer.MAX_VALUE.

public int retornar ()

{

if (raiz!=null)

{

int informacion =

raiz.info;

return informacion;

}

else

{

return

Integer.MAX_VALUE;

}

}

9 EJERCICIO Desarrolle el mtodo para buscar un nodo en especfico.