TAD: Pila de 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ó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

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

Especificación de TAD’s. TAD Pila de Enteros (II)

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 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.

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)

(Gp:) 5 (Gp:) 3 (Gp:) 7 (Gp:) 2

2 7 3 5 Estado inicial (Gp:) 5 (Gp:) 3 (Gp:) 7 (Gp:) 2

(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

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); } }