Monografías Plus »

TAD: Pila de Enteros



Monografias.com
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ó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. (Gp:) desapilar (Gp:) apilar (Gp:) Cima de la Pila 5 3 7 2 (Gp:) Cima de la Pila
Monografias.com
TAD Pila de Enteros: especificación (I) * Se lanza una excepción (PilaVacia) si se intenta utilizar alguna de estas operaciones cuando la pila está vacía
Monografias.com
Especificación de TAD’s. TAD Pila de Enteros (II)
Monografias.com
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
Monografias.com
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.
Monografias.com
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
Monografias.com
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 (); } }
Monografias.com
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 (); } }
Monografias.com
Algoritmos básicos con Pilas Tratamiento 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.
Monografias.com
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; }
Monografias.com
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.
Monografias.com
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) (Gp:) 5 (Gp:) 3 (Gp:) 7 (Gp:) 2 2 7 3 5 Estado inicial (Gp:) 5 (Gp:) 3 (Gp:) 7 (Gp:) 2
Monografias.com
(Gp:) 7 (Gp:) 2 if (! pilaO.pilaVacia ()) { elem = pilaO.desapilar (); pilaD.apilar (elem); invertirPila (pilaO, pilaD); (Gp:) 3 (Gp:) 5 elem = 3 (Gp:) 7 (Gp:) 2 (Gp:) 3 (Gp:) 5 elem = 5 (Gp:) 7 2 5 elem = 2 3 7 2 5 elem = 7 3 pilaO.apilar (elem); } 7 2 3 (Gp:) 7 (Gp:) 7 (Gp:) 2 (Gp:) 5 (Gp:) 3 (Gp:) 7 (Gp:) 2 (Gp:) 7 (Gp:) 2 (Gp:) 3 5 (Gp:) 7 (Gp:) 2 (Gp:) 5 (Gp:) 3 (Gp:) 7 (Gp:) 2 (Gp:) 5 (Gp:) 3 (Gp:) 7 (Gp:) 2 (Gp:) 5 (Gp:) 3
Monografias.com
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.
Monografias.com
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
Monografias.com
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); } }