igor santos grueiro. de este tipo de pilas no vamos a hablar

Programación IIPilas

Igor Santos Grueiro

De este tipo de pilas

NO vamos a hablar

¿Qué es una pila?

Tengo una pila de fichas

Tengo una pilade trabajos

Tengo una pila de galletas

Objeto

Una pila es una estructura formada por una secuencia de 0 a N elementos, en la que se extraen los elementos en orden inverso al de inserción

Objeto

Pila

Apilar/Push Desapilar/Pop

Cima de la pila

En un pila sólo se hacen operaciones con la cima de la pila

Es un tipo de estructura LIFO (Last Input First Output)

Podemos hacer varias operaciones:

Crear una pila

Objeto

Vaciar una pila

Objeto

Objeto

Comprobar sí una pila está vacía

Objeto

NOSÍ

Obtener una copia del elemento en la cima

Objeto

Objeto

Objeto

Insertar un elemento en la cima

Objeto

Objeto

Objeto

Se conoce como apilar o “push”

Recoger y eliminar de la pila el elemento cima

Objeto

Objeto

Se conoce como desapilar o “pop”

Vamos a construirla clase o tipo pila

Una pila se puede construir:

De forma estática De forma dinámica

De forma estática: la pila tiene un tamaño fijo

public class PilaEstatica {private Object [] elementos;

private int cont;

public PilaEstatica(int tamaño){elementos = new Object[tamaño];cont = 0;for (int i=0; i< elementos.length; i++){

elementos [i] = null;}

}//…

}

//…public void vaciar(){

for (int i = 0; i < this.contador; i++){ this.elementos[i] = null;

}}//…

Para vaciar ponemos a null los elementos insertados

//…public boolean estaVacia(){

return (cont == 0);}//…

Para comprar si está vacía miramos al contador

//…public void push(Object x){

if (cont != this.elementos.length){this.elementos[cont] = x;cont++;

} else {System.out.println(“Error, Pila llena”);

}}//…

Para insertar un elemento se añade al array en la posición del contador

//…public Object cima(){

if (cont > 0){return this.elementos[cont -

1];}else{

return null;} }//…

Para devolver el elemento en la cima se mira la posición

del contador

public Object cima(){ return v[cont-1]; }

//…public Object borrar(){

if (cont != 0){this.cont--;this.elementos[cont] = null;

}else{System.out.println(“Error, la pila esta vacia”);

}}//…

Para borrar el elemento en la cima se pone a null la

posición del contador (-1)

public Object cima(){ return v[cont-1]; }

//…public Object pop(){

if (cont == 0){return null;

} else {cont--;Object temp = this.elementos[cont] ;this.elementos[cont] = null;return temp;

}}//…

Para desapilar el elemento en la cima se recupera y se borra el

elemento de la cima

public Object cima(){ return v[cont-1]; }

//…public int tamanyo(){

return cont;}//…

También, podemos recuperar el número de elementos

insertados en la pila

public Object cima(){ return v[cont-1]; }

Ya dominamos un tipo de pila

Pero, ¿y cuándo no sabemos

cuántos elementos vamos a insertar?

Nos hace falta una estructura que enlace un elemento al siguiente

Object elementoNodo siguiente

Nodo

public class NodoPilaDinamica{private Object elemento;

private NodoPilaDinamica siguiente;

public NodoPilaDinamica(Object elemento, NodoPilaDinamica siguiente){

this.elemento = elemento;this.siguiente = siguiente;

}

public NodoPilaDinamica(Object elemento){this.elemento = elemento;this.siguiente = null;

}public Object getElemento(){

return elemento;}public NodoPilaDinamica getSiguiente(){

return siguiente;}

}

}

Ahora la clase PilaDinamica

public class PilaDinamica{private NodoPilaDinamica cima;

private int cont;

public PilaDinamica(){this.cima = null;this.cont = 0;

}//…

}

}

//…public void vaciar(){

this.cima = null;this.cont = 0;

}//…

Para vaciar ponemos a null la cima

//…public boolean estaVacia(){

return (this.cima == null); }//…

Para comprobar si está vacía miramos si la cima es null

//…public void push(Object x){

this.cima = new NodoPilaDinamica(x, this.cima);this.cont++;

}//…

Para insertar un elemento se añade un elemento como siguiente de

la cima y se actualiza la cima

Cima Cima

//…public Object cima(){

if (this.cima != null){return this.cima.getElemento();

} else {return null;

}}//…

Para devolver el elemento en la cima se devuelve el elemento de la cima

public Object cima(){ return v[cont-1]; }

//…public void borrar(){

if (this.cima != null){this.cima = this.cima.getSiguiente();this.cont--;

}}//…

Para borrar el elemento en la cima se pone la cima al valor siguiente de la cima previa

public Object cima(){ return v[cont-1]; }

Cima Cima

//…public Object pop(){

if (this.cima == null){return null;

} else {this.cont--;NodoPilaDinamica nodoTmp = this.cima;this.cima = this.cima.getSiguiente();return nodoTmp.getElemento();

}}//…

Para desapilar el elemento en la cima se recupera y se borra el

elemento de la cima

public Object cima(){ return v[cont-1]; }

Cima Cima

Se devuelve el objeto contenido en el nodo

Objeto

//…public int tamanyo(){

return cont;}//…

También, podemos recuperar el número de elementos

insertados en la pila

public Object cima(){ return v[cont-1]; }

Y, ¿para qué sirven las pilas?

Podemos implementar recursividad

Podemos evaluar

expresiones matemáticas

Las pilas son una estructura fundamental

de la computación