Embed Size (px)
Citation preview
Tema 2 Tipos abstractos de datos.
2.2 Pila de números enteros
Especificación de TAD’s. TAD Pila de Enteros.
Definición: Estructura de Datos que contiene una serie de elementos de tipo entero a los que sólosólo se puede acceder por un único lado.
Característica: Primer elemento obtenido es el último introducido
Estructura LIFO (Last Input, First Output)
Operaciones:apilar.desapilar.pilaVacía. inicializarPila.
desapilar
apilar
Cima de la Pila
5
3
7
2
Cima de la Pila
TAD Pila de Enteros: especificación (I)
Operación Especificación semántica Especificación sintáctica
apilar * Método que entrega un elemento (x) para que quede incorporado en la cima de la pila.
void apilar (int x)
desapilar * Método que elimina el elemento que ocupa la cima de la pila y devuelve como resultado dicho elemento.
int desapilar () throws PilaVacia
pilaVacia Método que al ejecutarse devuelve true si la pila está vacía (no tiene elementos), y false en caso contrario.
boolean pilaVacia ()
cima * Método que devuelve la cima de la pila (sin alterarla).
int cima () throws PilaVacia
decapitar * Método que elimina el elemento de la cima de la pila.
void decapitar () throws PilaVacia
* Se lanza una excepción (PilaVacia) si se intenta utilizar alguna de estas operaciones cuando la pila está vacía
Especificación de TAD’s. TAD Pila de Enteros (II)
Operación Especificación semántica Especificación sintáctica
leerPila Método que se utiliza para realizar la carga inicial de elementos de la pila.
void leerPila () throws NumberFormatException, IOException
imprimirPila Método que muestra en la pantalla el contenido de la pila.
void imprimirPila ()
eliminar Método que recibe una pila (que puede tener elementos o no) y la devuelve vacía.
void eliminarPila ()
numElemPila Método que devuelve el número de elementos de la pila.
int numElemPila ()
Excepciones (I)
Excepción: circunstancia que produce que una operación válida sobre un TAD no se pueda efectuar.
Ejemplos:apilar:
Al intentar apilar un nuevo elemento en la pila, ésta está llena. La operación apilar no debe producir ningún efecto.
desapilar, cima, decapitar: Al intentar desapilar un elemento de la pila, obtener su
cima o decapitarla, ésta está vacía. Estas operaciones no deben producir ningún efecto
Excepciones (II)
Para especificar completa y correctamente cada operación válida de un TAD se debe indicar:Especificaciones Sintácticas.Especificaciones Semánticas.Excepciones: Se indicarán como parte de las
especificaciones semánticas.
import java.io.*;
public interface Pila {boolean pilaVacia ();void eliminarPila ();int cima () throws PilaVacia;void apilar (int x);int desapilar () throws PilaVacia;void decapitar () throws PilaVacia;void imprimirPila ();void leerPila () throws NumberFormatException, IOException;
int numElemPila ();}
Interfaz del TAD Pila
Define los métodos de objeto utilizados en la clase TadPila
Prueba (condiciones normales)
import java.io.*;public class pruebaPila1 {
public static void main (String [ ] args) throws PilaVacia {Pila p = new TadPila ();int x;p.apilar (1);p.apilar (2);p.apilar (3);p.apilar (11);p.apilar (15);x = p.desapilar ();System.out.println ("x = " + x);x = p.desapilar ();System.out.println ("x = " + x);p.eliminarPila ();
}}
Situaciones de excepción
public class pruebaPila2 {public static void main (String [] args) throws PilaVacia {
Pila pila1 = new TadPila (); int i, j;
for (I = 1; I < 10; i++) pila1.apilar (i);j = pila1.desapilar ();for (I = 1; I < 10; i++)
j = pila1.desapilar ();pila1.eliminarPila ();
}}
Algoritmos básicos con PilasTratamiento recursivo.
Ventaja: legibilidad.Inconveniente: consumo de memoria Justificación:
Adecuación de la estructura a la técnica. Restricciones del enunciado.
Mecánica: desapilar – llamar – apilar.Terminaciones:
“Pesimista”: Llegar al final. Anticipada: No llamar más.
Ejemplos: Imprimir los elementos de una pila - Contar los elementos de una pila
static void escribirPila (Pila pila) throws PilaVacia {int elem;if (! pila.pilaVacia ()) {
elem = pila.desapilar ();System.out.println (elem);escribirPila (pila);pila.apilar (elem);
}}
static int contarPila (Pila pila) throws PilaVacia {
int elem, resul;if (! pila.pilaVacia ()) {
elem = pila.desapilar (); resul = 1 + contarPila (pila); pila.apilar (elem);
}else resul = 0;
return resul;}
Obtener el duplicado de una pila
static void copiarPila (Pila pilaO, Pila pilaD) throws PilaVacia {int elem;if (! pilaO.pilaVacia ()) {
elem = pilaO.desapilar ();copiarPila (pilaO, pilaD);pilaO.apilar (elem);pilaD.apilar (elem);
}}
Ejercicio propuesto: duplicar invirtiendo el orden de los elementos en la pila copia.
Invertir el contenido de una pila Argumentos: Pila de origen y pila de destino (ambos por referencia) Fase de ida: desapilamos en pila origen y apilamos en la pila
destino Fase de vuelta: apilamos en pila origen (para restablecer la pila) Fase de transición: no hacemos nada Condición de parada: pila vacía (sin terminación anticipada)
5
3
7
2
2
7
3
5
Estado inicial
5
3
7
2
7
2
if (! pilaO.pilaVacia ()) {elem = pilaO.desapilar ();pilaD.apilar (elem);invertirPila (pilaO, pilaD);
3
5
elem = 3
7
2
3
5
elem = 5
7
2
5
elem = 2
3
7
2
5
elem = 7
3
pilaO.apilar (elem);}
7
2
3
7
7
2
5
3
7
2
7
2
3
5 7
2
5
3
7
2
5
3
7
2
5
3
Sumergir un elemento
Consideraciones:Fase de ida: desapilamos un elemento.Condición de parada: pila.pilaVacia () (sin
terminación anticipada).Transición:
Apilamos el dato que queremos sumergir.Fase de vuelta: restablecemos la pila, apilando
el elemento desapilado a la ida.
static void sumergir (Pila pila, int dato) throws PilaVacia {int elem;if (!pila.pilaVacia ()) {
elem = pila.desapilar ();sumergir (pila, dato);pila.apilar (elem);
}else pila.apilar (dato);
}
Sumergir un elemento
Invertir los elementos de una pila
static void invertir (Pila pila) throws PilaVacia {int elem;if (!pila.pilaVacia ()) {
elem = pila.desapilar ();invertir (pila);sumergir (pila, elem);
}}
Terminación anticipadaParar la ejecución del programa antes de alcanzar la
condición de parada si se cumple determinada condición No se realizan más llamadas recursivas.
Condición de parada pesimista: pilaVacia.Ejemplo: buscar un valor.
Condición de parada pesimista: pilaVaciaTerminación anticipada: existe dato → no se realizan
más llamadas recursivasFase de ida:
desapilar elem de pila y comparar con dato Si igual → termino llamadas recursivas Si no → llamada a funcion recursiva
Fase de vuelta: apilar elem en pila
Quitar el elemento del fondopublic static int desfondar (Pila p) throws PilaVacia {
int elem, dato;if (!p.pilaVacia ()) {
elem = p.desapilar (); if (! p.pilaVacia ()) {
dato = desfondar (p); p.apilar (elem);
} else dato = elem;
}else {
System.out.println ("error, la pila está vacía");dato = -9999;
}return dato;
}
Buscar un valor
static boolean esta (Pila pila, int dato) throws PilaVacia{int elem;boolean resul;if (!pila.pilaVacia ()) {
elem = pila.desapilar ();if (elem == dato)
resul = true; else resul = esta (pila,dato);pila.apilar (elem);
} else resul = false;return resul;
}
Terminación anticipada
Terminación pesimista
Varias Pilas: Mezclar dos Pilas (AND). (I). Estrategia Entrada: Dos pilas ordenadas ascendentemente (pila1 y pila2) Salida: Pila ordenada ascendentemente (pila3) con los elementos de pila1y de pila2 sin
repeticiones. Argumentos:
pila1, pila2, pila3: clase Pila. elem1, elem2: enteros. (No pueden ser variables locales). apilar1, apilar2: lógicos. (Elemento pendiente de apilar).
Fase de ida: Variables de control: pend1 y pend2 (lógicos): La pila (1 ó 2) tiene algo pendiente de
tratar. Condición de terminación: Alguna de la pilas no tiene elementos por tratar (!(pend1 &&
pend2) ≡ (!pend1 || !pend2). Tratamiento:
desapilar según proceda (utilizar apilar1|2). Comparar elementos de pila1 y pila2. Llamada recursiva con los valores oportunos de apilar1 y apilar2.
Fase de transición: apilar en pila1 o pila2 algún posible elemento pendiente.
Fase de vuelta: apilar en pila1o pila2 según el valor de apilar1|2. apilar en pila3 solo cuando se corresponda con una instancia de la fase de ida en la que
elem1 = elem2
Varias Pilas: Mezclar dos Pilas (AND). (II). Argumentos
apilar1 y apilar2Según lo que haya ocurrido en la instancia anterior:
pendiente de apilar en pila1 ó en pila2Se inicializan en la llamada externa al programa,
ambas a false.
pend1 y pend2: quedan elementos por tratar en pila1|2 si no están vacías (!pila1|2.pilaVacia ())o que dan elementos por tratar (apilar1|apilar2)pend1 = (!pila1.pilaVacia () || apilar1)pend1|2 = (!pila2.pilaVacia () || apilar2)
Varias Pilas: Mezclar dos Pilas (AND). (III). Modelo
Varias Pilas: Mezclar dos Pilas (OR). (I). Estrategia Entrada: Dos pilas ordenadas ascendentemente (pila1 y pila2) Salida: Pila ordenada ascendentemente (pila3) con los elementos de pila1y de pila2 sin
repeticiones. Argumentos:
pila1, pila2, pila3: clase Pila. elem1, elem2: enteros. (No pueden ser variables locales). apilar1, apilar2: lógicos. (Elemento pendiente de apilar).
Fase de ida: Variables de control: pend1 y pend2 (lógicos): La pila (1 ó 2) tiene algo pendiente de tratar. Condición de terminación: Alguna de la pilas no tiene elementos por tratar (!(pend1 &&
pend2) ≡ (!pend1 || !pend2). Tratamiento:
desapilar según proceda (utilizar apilar1|2). Comparar elementos de pila1 y pila2. Llamada recursiva con los valores oportunos de apilar1 y apilar2.
Fase de transición: Copiar el resto de la pila no vacía en pila3 ( Llamada al método copiarPila). Tratar algún posible elemento pendiente de pila1 o pila2.
Fase de vuelta: apilar en pila3. apilar en pila1o pila2 según el valor de apilar1|2.
Varias Pilas: Mezclar dos Pilas (OR). (II). Argumentos
apilar1 y apilar2Según lo que haya ocurrido en la instancia anterior:
pendiente de apilar en pila1 ó en pila2Se inicializan en la llamada externa al programa,
ambas a false.
pend1 y pend2: quedan elementos por tratar en pila1|2 si no están vacías (!pila1|2.pilaVacia ()) o que dan elementos por tratar (apilar1|apilar2)pend1 = (!pila1.pilaVacia () || apilar1)pend1|2 = (!pila2.pilaVacia () || apilar2)
Varias Pilas: Mezclar dos Pilas (OR). (III). Modelo
elem1 = 1elem2 = 2
if (elem1 < elem2) {mezclarPila (pila1,pila2,pila3,false,true,1,2) [1]
pila1.apilar (1); pila3.apilar (1);}
7
5
1 2
6
4
7
5
6
4
Ambas pilas tienen elementos por tratar (pend1 && pend2)if (!apilar1)
elem1 = pila1.desapilar ();if (!apilar2)
elem2 = pila2.desapilar ();
[1]If (!apilar1)
elem1 = pila1.desapilar ();
elem1 = 5elem2 = 2
if (elem2 < elem1) {mezclarPila (pila1,pila2,pila3,true, false,5,2); [2]
pila2.apilar (2); pila3.apilar (2);}
Varias Pilas: Mezclar dos Pilas (OR). (IV). Simulación (I)
elem1 = 5elem2 = 4
if (elem2<elem1) mezclarPila(pila1,pila2,pila3,true,false,true,5,4); [3] pila2.apilar (4); pila3.apilar (4);}
Ambas pilas tienen elementos por tratar (pend1 && pend2)
[2] if (! apilar2) elem2 = pila2.desapilar ();
elem1 = 5elem2 = 6
if (elem1<elem2) { mezclarPila (pila1,pila2,pila3,false,true,5,6); [4] pila1.apilar (5); pila3.apilar (5);}
[3] if (! apilar2) elem2 = pila2.desapilar ();
7 6
4
7 6
Varias Pilas: Mezclar dos Pilas (OR). (IV). Simulación (II)
Ambas pilas tienen elementos por tratar (aux1 && aux2)
elem1 = 7elem2 = 6
if (elem2 < elem1) { mezclarPila (pila1,pila2,pila3,true,false,7,6);
[5] pila2.apilar (6); pila3.apilar (6);}
[4]if (!apilar1)
elem1 = pila1.desapilar ();
7
[5] pend1; ! pend2; apilar1
if (apilar1) pila1.apilar (elem1);pila3.apilar (elem1);
FASE DE VUELTA
7 7
Varias Pilas: Mezclar dos Pilas (OR). (IV). Simulación (III)
7 76
64
21
5
5
4
2
1
[5]pila2.apilar (6);pila3.apilar (6);
[4]pila1.apilar (5);pila3.apilar (5);
[3]pila2.apilar (4);pila3.apilar (4);
[2]pila2.apilar (2);pila3.apilar (2);[1]pila1.apilar (1);pila3.apilar (1);
Varias Pilas: Mezclar dos Pilas (OR). (IV). Simulación (IV)
Varias pilas. Terminación anticipada (I).Ejemplo. Método que devuelve un valor lógico que indica si una pila de enteros
ordenados ascendentemente desde la cima hacia el fondo (pila2) está contenida en otra (pila1) de las mismas características.
Es una variante del algoritmo de mezcla AND con terminación anticipada si durante la fase ida aparece un elemento de pila2 que no está en pila1 (elem2 < elem1).
Fase de ida: Variables de control: pend1 y pend2 (lógicos): La pila (1 ó 2) tiene algo pendiente de
tratar. Condición de terminación (pesimista): Alguna de la pilas no tiene elementos por
tratar (!(pend1 && pend2) ≡ (!pend1 || !pend2). Tratamiento:
desapilar según proceda (utilizar apilar1|2). Comparar elementos de pila1 y pila2.
Si elem1 ≤ elem2, llamada recursiva con los valores oportunos de apilar1 y apilar2.
En otro caso (Terminación anticipada). No hay más llamadas.
Varias pilas. Terminación anticipada (II).
Fase de transición: Por terminación anticipada: Se apilan los elementos pendientes en
pila1 y pila2 Se devuelve false.
Por terminación pesimista. Posibilidades: Se ha terminado con pila2 (y no con pila1).
Se apila el elemento pendiente de pila1 Se devuelve true.
Se ha terminado con pila1 (y no con pila2). Se apila el elemento pendiente de pila2 Se devuelve false.
Se ha terminado con ambas pilas. Se devuelve true.
Fase de vuelta: apilar en pila1o pila2 según el valor de apilar1|2. Se devuelve el resultado a la instancia de llamada.
En resumen. A la hora de manipular un TAD ¿Qué tipo de problema? Crear un TAD a partir de otro, modificar
el contenido, realizar cálculos con los elementos del TAD Parámetros:
TAD por referencia. Otros argumentos: ¿por referencia o por valor?. Cuáles están implícitos en el enunciado y cuáles no pero son
necesarios ¿Requieren inicialización? ¿Dónde los inicializo (fuera del
módulo recursivo, o dentro)? Condición de parada Finalización anticipada: circunstancia que la provoca Diseño:
Fase de ida: desapilar (+ operaciones) Transición: se alcanza la condición de parada y se realiza el
proceso correspondiente Fase de vuelta: (Operaciones +) apilar
