Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

TAD: Pila de Enteros (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

Terminación anticipada
Parar 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: pilaVacia
Terminación anticipada: existe dato ? no se realizan más llamadas recursivas
Fase 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

Monografias.com

Quitar el elemento del fondo
public 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;
}

Monografias.com

Buscar un valor
(Gp:) 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;
}
(Gp:) Terminación anticipada
(Gp:) Terminación pesimista

Monografias.com

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

Monografias.com

Varias Pilas: Mezclar dos Pilas (AND). (II). Argumentos
apilar1 y apilar2
Según lo que haya ocurrido en la instancia anterior: pendiente de apilar en pila1 ó en pila2
Se 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)

Monografias.com

Varias Pilas: Mezclar dos Pilas (AND). (III). Modelo

Monografias.com

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.

Monografias.com

Varias Pilas: Mezclar dos Pilas (OR). (II). Argumentos
apilar1 y apilar2
Según lo que haya ocurrido en la instancia anterior: pendiente de apilar en pila1 ó en pila2
Se 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)

Monografias.com

Varias Pilas: Mezclar dos Pilas (OR). (III). Modelo

Monografias.com

elem1 = 1
elem2 = 2

if (elem1 < elem2) {
mezclarPila (pila1,pila2,pila3,false,true,1,2) [1]
pila1.apilar (1);
pila3.apilar (1);
}
(Gp:) 7
(Gp:) 5
(Gp:) 1
(Gp:) 2
(Gp:) 6
(Gp:) 4
(Gp:) 7
(Gp:) 5
(Gp:) 6
(Gp:) 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 = 5
elem2 = 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)

Monografias.com

elem1 = 5
elem2 = 4

if (elem2
Monografias.com

Ambas pilas tienen elementos por tratar (aux1 && aux2)
elem1 = 7
elem2 = 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 ();
(Gp:) 7

[5]
pend1; ! pend2; apilar1
if (apilar1)
pila1.apilar (elem1);
pila3.apilar (elem1);
FASE DE VUELTA
(Gp:) 7
(Gp:) 7

Varias Pilas: Mezclar dos Pilas (OR). (IV). Simulación (III)

Monografias.com

7
7
6
6
4
2
1
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)

Monografias.com

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.

Monografias.com

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.

Monografias.com

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

Monografias.com

Recapitulamos.
Especificación de un TAD:
Propiedades sintácticas, propiedades semánticas y excepciones
TAD Pila
Estructura LIFO (Last Input First Output)
Recursividad
Fase de ida – fase de transición – fase de vuelta
Desapilar – Procesar – Apilar

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter