PILAS 1

Vista previa del material en texto

PILAS
DEFINICIÓN DE UNA PILA
Es una estructura de datos (TDA) caracterizada por:
Es lineal
Es homogénea: Todos los elementos son del mismo tipo de dato
Se tiene acceso solo al extremo denominado CIMA:
Se puede ver el elemento de la CIMA
Se puede eliminar el elemento de la CIMA
Se puede insertar un nuevo elemento por la CIMA
DEFINICIÓN DE UNA PILA
 Debido a que las operaciones de extracción e inserción se realizan por el mismo extremo, el último elemento en ser añadido será el primero en ser extraído; por ello a estas estructuras se las conoce con el nombre de LIFO (last-in, first-out; último en entrar, primero en salir).
PILA
GESTIÓN DE MEMORIA DINÁMICA
Base de la pila
cima
EJEMPLOS DE PILAS
	Un ejemplo es un montón de platos colocados uno encima del otro: Cuando se quiere introducir un nuevo plato, éste se coloca en la posición más accesible, encima del último plato. Cuando se toma un plato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido.
 Otro ejemplo es una caja llena de libros. Sólo podemos ver cuál es el libro que está más arriba en la caja, y si ponemos o tomamos un libro, sólo podremos actuar sobre este primer libro. No podemos siquiera saber el número total de libros guardados en la pila. Sólo sabremos el número de elementos de la pila de libros si previamente los sacamos hasta vaciar la caja.
EJEMPLOS DE PILAS
	Otra aplicación de la estructura pila es durante la ejecución de un programa de computadora, en la forma en que la máquina procesa las llamadas a los procedimientos. Cada llamada a un procedimiento (o función) hace que el sistema almacene toda la información asociada con ese procedimiento (parámetros, variables, constantes, dirección de retorno, etc...) de forma independiente a otros procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y que toda esa información almacenada pueda ser recuperada convenientemente cuando corresponda. Como en un procesador sólo se puede estar ejecutando un procedimiento, esto quiere decir que sólo es necesario que sean accesibles los datos de un procedimiento (el último activado, el que está en la cima). De ahí que la estructura pila sea apropiada para este fin.
OPERACIONES CON UNA PILA
INICIACIÓN DE LA ESTRUCTURA:
- CREAR LA PILA: INICIA LA PILA COMO VACÍA
OPERACIONES DE ACCESO, ELIMINACIÓN E INSERCIÓN
VER EL ELEMENTO DE LA CIMA
ELIMINAR EL ELEMENTO DE LA CIMA
INSERTAR UN ELEMENTO POR LA CIMA
VERIFICAR SI LA PILA ESTÁ VACÍA
VERIFICAR SI LA PILA ESTÁ LLENA (SI PUEDE LLENARSE)
IMPLEMENTACIÓN DE UNA PILA
UNA PILA PUEDE REPRESENTARSE MEDIANTE:
ESTRUCTURAS ESTÁTICAS (CON UN VECTOR)
ESTRUCTURAS DINÁMICAS (CON UNA LISTA ENLAZADA)
IMPLEMENTACION DE UNA PILA CON UN VECTOR
	20	5	10			
LA CLASE PILA TIENE DOS CAMPOS:
1 VECTOR ELEM, DONDE ESTAN LOS ELEMENTOS DE LA PILA
 ELEM
 1 2 3 4 . . . . . MAX
2 CIMA (ENTERO) QUE CONTIENE LA POSICIÓN DEL ELEMENTO DE LA CIMA
 CIMA
	3
CLASE PILA
class Pila {
// campos
int cima;
int[] elem;
final int MAX=50;
// constructor
public Pila ()
{ cima=0;
 elem = new int[MAX + 1];
}
// verifica si la pila está vacía
public boolean pilaVacia()
{ return cima==0; }
	Pila
	cima
elem[]
MAX
	Constructor por defecto
pilaVacia()
pilaLlena()
ver()
eliminar()
insertar(x)
CLASE PILA
// verifica si la pila está llena
public boolean pilaLlena()
{ return cima==MAX; }
// ver el elemento de la CIMA
public int ver ()
{ return elem[cima]; }
// eliminar el elemento de la CIMA
public void eliminar()
{ if (!pilaVacia() ) {cima = cima - 1; } }
// insertar un elemento por la CIMA
public void insertar (int x)
{ if (!pilaLlena() ) { cima = cima + 1;
 elem[cima] = x; }
 } 
}
	Pila
	cima
elem[]
MAX
	Constructor por defecto
pilaVacia()
pilaLlena()
ver()
eliminar()
insertar(x)
CLASE OPERACIONES
class Operaciones {
// INSERTAR N ELEMENTOS
public Pila insertarN(Pila p)
{	System.out.print("Nº de elementos= ");
	int n=Leer.datoInt();
	int d;
	for(int c=1;c<=n && !p.pilaLlena();++c)
	{System.out.print("Dato"+c+"= ");
	d=Leer.datoInt();
	p.insertar(d);
}
return p;
}
	Operaciones
	
	insertarN(p)
mostrar(p)
eliminarPos(p)
CLASE OPERACIONES
// MOSTRAR
public void mostrar(Pila p)
{ Pila paux=new Pila(); // SE CREA UNA PILA AUXILIAR VACIA: paux
 int d; // SE VACÍA LA PILA p EN LA PILA paux
 while(!p.pilaVacia()) { 
 // SE RECUPERA EL ELEMENTO DE LA CIMA DE LA PILA p Y SE LO MUESTRA
 d=p.ver();
 System.out.println(" "+d);
 p.eliminar(); // SE ELIMINA EL ELEMENTO DE LA CIMA DE p
 paux.insertar(d); // SE INSERTA EN LA CIMA DE paux EL ELEMENTO ELIMINADO DE p 
 } // AL FINAL LA PILA p QUEDA VACIA Y paux CON LOS ELEMENTOS DE p, INVERTIDOS
CLASE OPERACIONES
// SE VACIAN LOS ELEMENTOS DE paux EN p, QUEDANDO COMO ESTABAN ORIGINALMENTE
 while(!paux.pilaVacia()){
 d=paux.ver(); // SE RECUPERA EL ELEMENTO DE LA CIMA DE LA PILA paux
 paux.eliminar(); // SE ELIMINA EL ELEMENTO DE LA CIMA DE paux
 p.insertar(d); // SE INSERTA EN LA CIMA DE p EL ELEMENTO ELIMNADO DE paux 
	}
}
CLASE OPERACIONES
// ELIMINAR LOS ELEMENTOS POSITIVOS
public void eliminarPos(Pila p)
{	Pila paux=new Pila();
	int d;
	while(!p.pilaVacia())
	{d=p.ver();
	p.eliminar();
	if(d<=0)paux.insertar(d);
	}
	while(!paux.pilaVacia())
	{d=paux.ver();
	paux.eliminar();
	p.insertar(d);
	}
} }
CLASE PRINCIPAL
	Pila pil=new Pila();
	Operaciones op = new Operaciones();
	pil = op.insertarN(pil);
 op.mostrar(pil);
	op.eliminarPos(pil);
 op.mostrar(pil);
PROBLEMAS
DEFINIR UNA PILA CON ELEMENTOS TIPO doublé
INSERTAR N ELEMENTOS
MOSTRAR
ENCONTRAR EL PROMEDIO DE LOS POSITIVOS
ENCONTRAR EL MAYOR DE LOS NEGATIVOS
INSERTAR UN ELEMENTO EN LA BASE D LA PILA