Igor Santos Grueiro
Qué es una
¿
pila?
Tengo una pila de fichas
Tengo
de trabajos
Tengo una pila de galletas
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
Cima de
la pila
Desapilar/Pop
Apilar/Push
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
Vaciar una pila
Objeto
Objeto
Comprobar sí una pila
está vacía
NO
SÍ
Objeto
Objeto
Obtener una copia del
elemento en la cima
Objeto
Objeto
Se conoce
como en
Insertar
un elemento
apilar
o “push”
la cima
Objeto
Objeto
Objeto
Recoger
y eliminar
Se conoce
comode la
pila
el elemento
cima
desapilar
o “pop”
Objeto
Objeto
Vamos a construir
la 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;
}
}
//…
}
Para vaciar ponemos a null
los elementos insertados
//…
public void vaciar(){
for (int i = 0; i < this.contador; i++){
this.elementos[i] = null;
}
}
//…
Para comprar si está vacía
miramos al contador
//…
public boolean estaVacia(){
return (cont == 0);
}
//…
Para insertar un elemento
se añade al array en la
posición del contador
//…
public void push(Object x){
if (cont != this.elementos.length){
this.elementos[cont] = x;
cont++;
} else {
System.out.println(“Error, Pila llena”);
}
}
//…
public Object cima(){
return v[cont-1];
}
Para devolver el elemento en
la cima se mira la posición
del contador
//…
public Object cima(){
if (cont > 0){
return this.elementos[cont - 1];
}else{
return null;
}
}
//…
public Object cima(){
return v[cont-1];
}
Para borrar el elemento en la
cima se pone a null la
posición del contador (-1)
//…
public Object borrar(){
if (cont != 0){
this.cont--;
this.elementos[cont] = null;
}else{
System.out.println
(“Error, la pila esta vacia”);
}
}
//…
public Object cima(){
return v[cont-1];
}
Para desapilar el elemento en la
cima se recupera y se borra el
elemento de la cima
//…
public Object pop(){
if (cont == 0){
return null;
} else {
cont--;
Object temp = this.elementos[cont] ;
this.elementos[cont] = null;
return temp;
}
}
//…
public Object cima(){
return v[cont-1];
}
También, podemos recuperar
el número de elementos
insertados en la pila
//…
public int tamanyo(){
return cont;
}
//…
Ya dominamos
Pero, ¿y cuándo no sabemos
cuántos elementos
vamos a insertar?
Nos hace falta una estructura que
enlace un elemento al siguiente
Nodo
Nodo siguiente
Object elemento
}
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;
}
//…
}
Para vaciar ponemos a null
la cima
//…
public void vaciar(){
this.cima = null;
this.cont = 0;
}
//…
Para comprobar si está vacía
miramos si la cima es null
//…
public boolean estaVacia(){
return (this.cima == null);
}
//…
Para insertar un elemento
se añade un elemento como siguiente de
la cima y se actualiza la cima
//…
public void push(Object x){
this.cima = new NodoPilaDinamica(x, this.cima);
this.cont++;
}
//…
Cima
Cima
public Object cima(){
return v[cont-1];
}
Para devolver el elemento en
la cima se devuelve el
elemento de la cima
//…
public Object cima(){
if (this.cima != null){
return this.cima.getElemento();
} else {
return null;
}
}
//…
public Object cima(){
return v[cont-1];
}
Para borrar el elemento en la
cima se pone la cima al valor
siguiente de la cima previa
//…
public void borrar(){
if (this.cima != null){
this.cima = this.cima.getSiguiente();
this.cont--;
}
}
//…
Cima
Cima
public Object cima(){
return v[cont-1];
}
Para desapilar el elemento en la
cima se recupera y se borra el
elemento de la 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();
}
}
//…
Cima
Cima
Objeto
Se devuelve el objeto contenido en el
nodo
public Object cima(){
return v[cont-1];
}
También, podemos recuperar
el número de elementos
insertados en la pila
//…
public int tamanyo(){
return cont;
}
//…
para qué sirven las pilas?
Y, ¿
Podemos implementar recursividad
Las pilas son una
estructura fundamental
de la computación
Descargar

05a-Pilas