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