Especificación de Pilas y Colas: Estructuras de Datos en Pascal con Tipos Abstractos
Especificación de Pilas
Parámetros genéricos
TIPOS
TipoElemento
FIN PARÁMETROS GENÉRICOS
TIPOS TipoPila
Operaciones
Constructoras generadoras
CrearPilaVacía : → TipoPila
Apilar : TipoElemento × TipoPila → TipoPila
Observadoras selectoras
parcial Cima : TipoPila → TipoElemento
Observadoras no selectoras
EsPilaVacía : TipoPila → booleano
IgualPila : TipoPila × TipoPila → booleano
Constructoras no generadoras
parcial Desapilar : TipoPila → TipoPila
CopiarPila : TipoPila → TipoPila
Variables
ep: TipoElemento;
pila: TipoPila;
Ecuaciones de definitud
Def (Cima (Apilar (ep, pila)))
Def (Desapilar (Apilar (ep, pila)))
Ecuaciones
EsPilaVacía (CrearPilaVacía) = CIERTO
EsPilaVacía (Apilar (ep,pila)) = FALSO
Cima (Apilar (ep,pila)) = ep
Desapilar (Apilar (ep,pila)) = pila
CopiarPila (CrearPilaVacía) = CrearPilaVacía
CopiarPila (Apilar (ep,pila)) = Apilar (ep, CopiarPila(pila))
Implementación en Pascal: Unidad Pilas
UNIT Pilas;
INTERFACE
TYPE
TipoElemento = Integer;
TipoPila = ^TipoNodo;
TipoNodo = RECORD
info : TipoElemento;
sig : TipoPila
END; (* registro *)
PONER CABECERAS DE LOS SUBPROGRAMAS
IMPLEMENTATION
PROCEDURE CrearPilaVacia (VAR pila: TipoPila);
BEGIN
pila := NIL
END;
PROCEDURE Apilar (ep: TipoElemento; VAR pila: TipoPila);
VAR
paux : TipoPila;
BEGIN
New (paux);
paux^.info := ep;
paux^.sig := pila;
pila := paux;
END;
FUNCTION Cima (pila: TipoPila): TipoElemento;
BEGIN
IF (NOT EsPilaVacia(pila)) THEN
BEGIN
Cima := pila^.info;
END;
END;
FUNCTION EsPilaVacia (pila: TipoPila): BOOLEAN;
BEGIN
EsPilaVacia := (pila = NIL);
END;
PROCEDURE Desapilar (VAR pila: TipoPila);
BEGIN
IF NOT EsPilaVacia(pila) THEN
pila := pila^.siguiente
END;
Especificación de Colas
Parámetros genéricos
TIPOS TipoElemento
FIN PARÁMETROS GENÉRICOS
TIPOS TipoCola
Operaciones
Constructoras generadoras
CrearColaVacía : → TipoCola
Insertar : TipoElemento × TipoCola → TipoCola
Observadoras selectoras
parcial PrimeroCola : TipoCola → TipoElemento
Observadoras no selectoras
EsColaVacía : TipoCola → booleano
Iguales : TipoCola × TipoCola → booleano
Constructoras no generadoras
parcial Eliminar : TipoCola → TipoCola
Variables
e: TipoElemento;
cola, cola1, cola2: TipoCola;
Ecuaciones de definitud
Si No EsColaVacía(Cola) → DEF (PrimeroCola(Cola))
Si No EsColaVacía(cola) → DEF (Eliminar (Cola))
Ecuaciones
PrimeroCola (Insertar (e,cola)) =
SI EsColaVacía (cola) → e
| PrimeroCola (cola)
EsColaVacía (CrearColaVacía) = CIERTO
EsColaVacía (Insertar (e,cola)) = FALSO
Iguales(CrearColaVacía, CrearColaVacía) = CIERTO
Iguales(Insertar(e,cola), CrearColaVacía) = FALSO
Iguales(Insertar(e,cola1), Insertar(e,cola2)) =
Si e1 = e2 → Iguales(cola1,cola2)
| FALSO
Eliminar (Insertar (e,cola)) =
SI EsColaVacía (cola) → CrearColaVacía
| Insertar (e, Eliminar (cola))
FIN ESPECIFICACIÓN
Implementación en Pascal: Unidad Colas
UNIT Colas;
INTERFACE
TYPE
TipoElemento = Integer;
TipoCursor = ^TipoNodo;
TipoNodo = RECORD
info : TipoElemento;
sig : TipoCursor
END; (* registro *)
TipoCola = RECORD
principio: TipoCursor;
final: TipoCursor;
END;
PONER CABECERAS DE LOS SUBPROGRAMAS
IMPLEMENTATION
PROCEDURE CrearColaVacia (VAR Cola: TipoCola);
BEGIN
Cola.principio := NIL;
Cola.final := NIL;
END;
PROCEDURE Insertar (ec: TipoElemento; VAR Cola: TipoCola);
VAR
caux : TipoCursor;
BEGIN
New(caux);
Asignar(ec, caux^.info);
caux^.sig := NIL;
IF (EsColaVacia(Cola)) THEN
BEGIN
Cola.principio := caux;
END
ELSE
BEGIN
Cola.final^.sig := caux;
END;
Cola.final := caux;
END;
FUNCTION Primero (Cola: TipoCola; VAR ec: TipoElemento);
BEGIN
IF (NOT EsColaVacia (Cola)) THEN
BEGIN
Asignar(Cola.principio^.info, ec);
END;
END;
FUNCTION EsColaVacia(Cola: TipoCola): Boolean;
BEGIN
EsColaVacia := ((EsNulo(Cola.principio)) AND (EsNulo(Cola.final)));
END;
FUNCTION Iguales (cola1, cola2: TipoCola): Boolean;
VAR
Ciguales: Boolean;
BEGIN
Ciguales := TRUE;
WHILE ((Ciguales) AND (NOT EsColaVacia(cola1)) AND (NOT EsColaVacia(cola2))) DO
BEGIN
Ciguales := cola1.principio^.info = cola2.principio^.info;
cola1.principio := Siguiente(cola1.principio);
cola2.principio := Siguiente(cola2.principio);
END;
Iguales := ((Ciguales) AND (EsColaVacia(cola1)) AND (EsColaVacia(cola2)));
END;
Versión recursiva
RECURSIVAMENTE
FUNCTION Iguales(cola1, cola2: TipoCola): Boolean;
VAR
eiguales: Boolean;
BEGIN
IF ((EsColaVacia(cola1)) AND (EsColaVacia(cola2))) THEN
BEGIN
Iguales := TRUE;
END
ELSE IF ((EsColaVacia(cola1)) AND (NOT EsColaVacia(cola2))) THEN
BEGIN
Iguales := FALSE;
END
ELSE IF ((EsColaVacia(cola2)) AND (NOT EsColaVacia(cola1))) THEN
BEGIN
Iguales := FALSE;
END
ELSE IF (NOT EsColaVacia(cola1)) AND (NOT EsColaVacia(cola2))) THEN
BEGIN
eiguales := Igual(cola1.principio^.info; cola2.principio^.info);
cola1.principio := Siguiente(cola1.principio);
cola2.principio := Siguiente(cola2.principio);
Iguales := eiguales AND Iguales(cola1, cola2));
END;
END;
PROCEDURE Eliminar(VAR Cola: TipoCola);
VAR
caux: TipoCursor;
BEGIN
IF (NOT EsColaVacia(Cola)) THEN
BEGIN
IF (Cola.principio = Cola.final) THEN
BEGIN
Dispose(Cola.principio);
Cola.principio := NIL;
Cola.final := NIL;
END
ELSE
BEGIN
caux := Cola.principio;
Cola.principio := Siguiente(Cola.principio);
Dispose(caux);
END;
END;
END;