igor santos grueiro. de este tipo de pilas no vamos a hablar
TRANSCRIPT
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