pilas y colas parte 1

Vista previa del material en texto

Algoritmos y Estructuras de 
Datos
Departamento de Informática
LAS - TUP
Unidad N° 4 - Parte I
Temario
Contenedores lineales: Pilas y Colas.
Introducción 
Nivel lógico 
Nivel usuario
Nivel de implementación
Qué es una pila?
Qué es una pila?
A nivel lógico, una PILA es un grupo ordenado de elementos homogéneos. 
Para agregar nuevos elementos o quitar elementos residentes en ella, solo es 
posible mediante la Cabeza (o Tope).
Qué es una pila?
Porque un grupo ordenado de elementos? 
Definición: Una PILA es una estructura de datos en la que sus elementos son 
agregados y eliminados sólo por un extremo. También es conocida como 
estructura LIFO (Last In, First Out).
Operaciones sobre pilas
La operación que agrega un elemento a la pila (mediante la Cabeza/Tope) se 
conoce como Meter(Push) y la operación que toma el elemento de la pila (por la 
Cabeza/Tope) y lo quita de la misma, se conoce como Sacar(Pop).
Operaciones sobre pilas
Antes de comenzar a operar con una PILA, la misma debe estar vacía. 
Necesitamos una operación LimpiarPila que cree una pila vacía.
A su vez, antes de quitar algún elemento de una PILA deberíamos verificar si la 
misma contiene elementos. A tal efecto, necesitamos una operación PilaVacia 
que verifique esto.
Asimismo, antes de agregar un nuevo elemento en la PILA deberíamos verificar si 
su capacidad de almacenamiento no está colmada. Para ello, necesitamos de la 
operación PilaLlena.
Operaciones sobre pilas
❏ LimpiarPila(Pila): tenemos Pila vacía.
❏ Meter(Pila, x): el valor de x se agrega a Pila (siempre que no esté llena!). 
Supongamos x=6.
❏ Meter(Pila, x): el valor de x se agrega quedando al TOPE de Pila. 
Supongamos x=-2.
❏ Sacar(Pila, x): se saca el elemento ubicado al TOPE de Pila y se almacena 
en x. En este caso x=-2.
❏ Meter(Pila, x): el valor de x es se ubica al TOPE de Pila. Supongamos x=5. 
Pila tendría los elementos 5 y 6.
❏ . . . ( y así sucesivamente)
Operaciones sobre pilas
Para definir el Tipo de Dato Abstracto PILA, es necesario conocer y determinar la 
estructura lógica de la misma, como así también definir un conjunto de 
operaciones que le permita (luego) al usuario, manipular los elementos de la 
misma.
Importante: debemos tener en cuenta que una PILA es una estructura dinámica. 
Cambia a medida que se agregan y eliminan elementos de la misma.
Tipo de Dato Abstracto PILA
El usuario de la PILA aún no está preparado para usarla.
Antes, debe conocer la interfaz que le permita operar con la pila (debiendo 
ocultarse los detalles de implementación!).
Describiremos el Tipo de Dato Abstracto PILA y sus operaciones más importantes.
Tipo de Dato Abstracto PILA
Función de acceso Los elementos se agregan y quitan por la cabeza de la pila
 LimpiarPila(Pila)FunciónEntradaPre-condición SalidaPost-condición inicializa Pila a estado vacíoPila a inicializarNingunaPila (inicializada)Pila está vacía
PilaVacia(Pila)Función EntradaPre-condiciónSalidaPost-condición devuelve un valor lógicoverifica si Pila está vacía Pila a verificarNingunaPilaVacia (variable lógica)PilaVacia devuelve Verdadero si Pila no tiene elementos, sino Falso
PilaLlena(Pila)FunciónEntradaPre-condiciónSalidaPost-condición devuelve un valor lógicoverifica si Pila está llenaPila a verificarNingunaPilaLlena (variable lógica)PilaLlena devuelve Verdadero si Pila colmó su capacidad, sino Falso
Tipo de Dato Abstracto PILA
Meter(Pila, nuevoElemento) 
Función
Entrada
Pre-condición
Salida
Post-condición
agrega nuevoElemento a Pila 
Pila, nuevoElemento
Pila no está llena 
Pila (modificada)
Meter agrega nuevoElemento al tope de Pila
Pila=nuevoElemento + Pila
Sacar(Pila, ElemSacado) 
Función
Entrada
Pre-condición
Salida
Post-condición
saca el elemento ubicado al tope de Pila y lo devuelve en 
ElemSacado
Pila
Pila no está vacía 
Pila (modificada)
ElemSacado=Tope(Pila), Pila=Pila-Tope(Pila)
Uso
Mediante las especificaciones del TAD PILA, el USUARIO puede hacer uso de 
nuestra PILA sin saber COMO se implementará.
Sería recomendable entonces, informar al USUARIO de la interfaz del TAD Pila.
La interfaz en JAVA
Public interface OperacionesCL1
{
public void meter(Object elemento);
Object public sacar();’
public void limpiar();
public boolean estaVacia();
}
Implementación
En este nivel, nos concentramos en implementar el Tipo Abstracto de Datos Pila.
Implementaremos (por ahora) una PILA usando arreglos de JAVA.
Luego, lo haremos usando Lista enlazada.
Propuesta
Teniendo en cuenta que nuestra PILA no tiene capacidad infinita, debemos 
establecer un tamaño máximo.
Asimismo, mediante el uso de un Arreglo podemos agregar y quitar fácilmente los 
elementos de la PILA. Para ello, debemos tener en cuenta que todo sale y entra 
por la cabeza de la pila y que dado que ahora estamos ubicados como 
programadores, deberíamos implementar una pila con el menor uso de recursos 
posible.
Cola
Cola
Todos hemos experimentado alguna vez estar en una cola.
Una cola de supermercado, una cola para subir al colectivo…
Cola
A nivel lógico, una COLA es un grupo ordenado de elementos homogéneos, en el 
que los nuevos elementos se agregan por un extremo (el final) y se quitan por el 
otro (el frente).
Como ejemplo de cola FIFO (First In First Out) tenemos el caso de una cola 
simple de supermercado.
Todo nuevo cliente que llega a la cola se ubica al final de la cola.
Cuando el cajero esté listo para atender a un nuevo cliente, le avisa al cliente que 
está al principio de la cola. Una vez que dicho cliente paga la cuenta, se retira de 
la cola.
Cola
Podemos manipular directamente cualquier elemento de la cola? No!. 
Debe llegar al frente, luego se puede manipular y si es necesario, se agrega 
nuevamente a la cola.
Definición: Una cola FIFO es una estructura de datos en la que los elementos se 
agregan por el final y se quitan por el frente.
Operaciones sobre colas FIFO
Recordando el ejemplo de la cola simple de 
supermercado, existen dos operaciones aplicadas 
comúnmente en las colas.
La operación que agrega nuevos elementos al final de la 
cola se conoce como Meter(o Insertar). 
Para quitar elementos del frente de la cola, 
necesitaremos la operación Sacar(o Servir).
Operaciones sobre colas FIFO
Verificar si la cola está vacía es una operación útil (por ejemplo, antes de intentar 
quitar el elemento del frente). La llamaremos ColaVacia.
Como la cola no tiene capacidad ilimitada, verificar si la misma ha llegado a su 
capacidad es necesario.
Se necesita también de una operación que inicialice la cola a estado vacío y se 
conoce como LimpiarCola.
Operaciones sobre colas FIFO
❏ LimpiarCola(Cola): tenemos la cola inicializada.
❏ Meter(Cola, x): el valor de x se agrega al final de Cola.
Supongamos x=6.
❏ Meter(Cola, x): el valor de x se agrega al final de Cola (suponiendo que su 
capacidad no está colmada).
Supongamos x=9.
❏ Meter(Cola, x): el valor de x se agrega al final de Cola.
Supongamos x=10. Hasta el momento tenemos en Cola a 6, 9, 10.
❏ Sacar(Cola, x): el elemento al frente de Cola es sacado y devuelto en x. En 
nuestro caso, x=6.
Tipo de Dato Abstracto COLA
Función de acceso Los elementos se agregan y quitan por la cabeza de la pila
 LimpiarCola(Cola)FunciónEntradaPre-condición SalidaPost-condición inicializa Cola a vacíoCola a inicializarNingunaCola (inicializada)Cola está vacía
ColaVacia(Cola)Función EntradaPre-condiciónSalidaPost-condición devuelve un valor lógicoverifica si Cola está vacía Cola a verificarNingunaColaVacia (variable lógica)devuelve Verdadero si Cola no tiene elementos, sino Falso
ColaLlena(Cola)FunciónEntradaPre-condiciónSalidaPost-condición devuelve un valor lógicoverifica si Cola está llenaCola a verificarNingunaColaLlena (variable lógica)Ddevuelve Verdadero si Cola colmó su capacidad, sino Falso
Tipo de Dato Abstracto COLA
Meter(Cola, nuevoElemento) 
Función
Entrada
Pre-condición
Salida
Post-condición
agrega nuevoElemento al final de la cola 
Cola, nuevoElemento
Cola no está llena 
Cola (modificada)Cola = Cola + nuevoElemento
Sacar(Cola, ElemSacado) 
Función
Entrada
Pre-condición
Salida
Post-condición
saca el elemento ubicado al frente de la cola y lo devuelve en ElemSacado
Cola
Cola no está vacía 
Cola (modificada), Elemsacado
Elemsacado = frente de Cola Original,
Cola=Cola original sin el elemento del frente
Implementación
De manera similar a lo visto con PILAS, en este nivel nos centraremos en la 
implementación de una cola FIFO en JAVA.
Una COLA puede implementarse con un Arreglo.
También con Lista enlazada.
Aplicaciones
Las PILAS y COLAS tienen muchas aplicaciones. 
Implementación: 
Arrays
Listas enlazadas
Aplicaciones
Las PILAS y COLAS tienen muchas aplicaciones. 
Pilas: Las últimas páginas visitadas en un browser, las acciones a deshacer de 
Microsoft, . . . . 
Colas: simulación de eventos discretos, colas de procesos, de impresión, . . . .
Implementación: Tener en cuenta el uso de memoria y los movimientos...
Arrays
Listas enlazadas
public class clsPilaArr implements OperacionesCL1{ 
private Object[] pila; 
private int cabeza; 
private int tamPila; 
public clsPilaArr(int tamPila){ 
this.tamPila=tamPila; 
this.pila=new Object[this.tamPila]; limpiar(); 
}
public void meter(Object elemento){ 
if (!estaLlena()){ 
incrementaCabeza(); 
this.pila[this.cabeza] = elemento; }
else { System.out.println(”Error. Pila llena...”); }
}
public Object sacar{
Object elemento = null;
if (!estaVacia()){
elemento = this.pila[this.cabeza];
decrementaCabeza();
} else{
System.out.println(”Error. Pila vacia...”);
}
return elemento;
}
public void limpiar(){
this.cabeza=-1;
}
public boolean estaLlena(){
return (this.cabeza==this.tamPila-1);
}
public boolean estaVacia(){
return (this.cabeza==-1);
}
private void incrementaCabeza(){
this.cabeza++;
}
private void decrementaCabeza(){
this.cabeza -;
}
// fin de la clase
}
Prueba de la clase
clsPilaArr objPila = new clsPilaArr(5);
Object objAux;
Integer objInt1,objInt2,objInt3;
objInt1=new Integer(30);
objInt2=new Integer(50);
objInt3=new Integer(-4);
objPila.meter(objInt1);
objPila.meter(objInt2);
objPila.meter(objInt3);
objPila.meter(objInt3);
objPila.meter(objInt3);
objPila.meter(objInt3);
while (!objPila.estaVacia()){
objAux = objPila.sacar();
if (objAux!=null){
System.out.println(”Elemento Pila ” + objAux.toString());
}
}