9.2 Implementación

La siguiente implementación de Cola es con apuntadores. La implementación con arreglos es muy ineficiente cada vez que se retira de la cola se deben correr todos los elementos del arreglo.

/*

cola.h

Autor: L. Alejandro Bernal R.

Fecha: 2000.12.10

Descripción: Implementación con apuntadores de Cola.

*/

#ifndef _COLA_H_

#define _COLA_H_

#include <stdlib.h>

/*

TDA Nodo 

    Descripción: Un nodo representa a cado uno de los elementos de la cola.

    Invariante: nodo pertenece a Nodo y nodo=(inf,sig) y sig pertenece a *Nodo y inf pertenece a TipoB 

*/

template<class TipoB>

class Nodo{

    private:

    // Atributos:

    TipoB inf; // Información del nodo.

    Nodo *sig; // Apuntador al siguiente nodo.

    public:

    //Operaciones: 

    /*

    Operación Nodo 

        Descripción: Construye un nodo con la información.

        Descripción operacional: Nodo: TipoB -> Nodo

        Precondición: in pertenece a TipoB 

        Poscondición: nodo=(inf,sig)

    */

    Nodo(TipoB in) { inf = in; }

    /*

    Operación obtinf 

        Descripción: Obtiene la información del nodo.  

        Descripción operacional: obtinf: Nodo -> TipoB 

        Precondición: 

        Poscondición: obtinf=inf

    */

    TipoB obtinf() { return inf; }

    /*

    Operación modinf 

        Descripción: Modifica la información del nodo.

        Descripción operacional: modinf: Nodo x TipoB -> Nodo

        Precondición: nue pertenece a TipoB 

        Poscondición: nodo=(nue,sig) 

    */

    void modinf(TipoB nue) { inf = nue;  }

    /*

    Operación obtsig 

        Descripción: Obtiene el apuntador al siguiente nodo.

        Descripción operacional: obtsig: Nodo -> *Nodo

        Precondición: 

        Poscondición: obtsig=sig 

    */

    Nodo *obtsig() { return sig; }

    /*

    Operación modsig 

        Descripción: Modifica el apuntador al siguiente.

        Descripción operacional: modsig: Nodo x *Nodo -> Nodo

        Precondición: si pertenece a *Nodo

        Poscondición: nodo=(ing,si)

    */

    void modsig(Nodo *si) { sig = si; }

}; // class Nodo

/*

TDA Cola.

    Descripción: El TDA Cola de caracteriza por que el primero en entrar es el primero en salir (PEPS) o FIFO (Last In Firts Out).

    Invariante: Cola=(elem,cab.col) y elem=<elem[0],elem[1],elem[2],...,elem[i],...,elem[n-1]> y (Para todo i,0<=i<n,elem[i] pertenece a TipoB) y elem[0]=cab y elem[n-1]=col

*/

template<class TipoB>

class Cola{

    private:

    // Atributos:

    Nodo<TipoB> *cab; // apuntador a la cabeza, apunta al primer elemento.

    Nodo<TipoB> *col; // Apuntador a la cola, apunta al último elemento.

    public:

    // Excepciones:

    class Excepcion { }; // Excepción general.

    class NoHayMemoria : public Excepcion { }; // No hay memoria.

    class NoHayCabeza : public Excepcion { }; // No hay cabeza.

    // Operaciones:

    /*

    Operación Cola

        Descripción: Construlle una Cola nueva.

        Descripción operacional: Cola: -> Cola.

        Precondición: verdadero.

        Poscondición: cola pertenece a Cola y cola=(<>,,).

    */

    Cola() { cab = NULL; col = NULL; }

    /*

    Operación Cola

        Descripción: Destruye la cola.

        Descripción operacional: Cola: Cola ->.

        Precondición:

        Poscondición:

    */

    Cola();

    /*

    Operación adicionar

        Descripción: Adiciona un nuevo elemento a la Cola.

        Descripción operacional: adicionar:Cola x TipoB -> Cola.

        Precondición: cola pertenece a Cola y cola=(<elem[0],elem[1],elem[2],...,elem[n-1]>,elem[0],elem[n-1]) y nuevo pertenece a TipoB

        Poscondición: cola=(<elem[0],elem[1],elem[2],...,elem[n-1],nuevo>,elem[0],nuevo)

    */

    void adicionar(TipoB elem);

    /*

    Operación retirar

        Descripción: Retira el primer elemento de la Cola.

        Descripción operacional: retirar:Cola -> Tipo.

        Precondición: cola pertenece a Cola y cola=(<elem[0],elem[1],elem[2],...,elem[n-1]>,elem[0],elem[n-1])

        Poscondición: cola=(<elem[1],elem[2],...,elem[n-1]>,elem[1],elem[n-1]) y retirar=elem[0]

    */

    TipoB retirar();

    /*

    Operación estavacia

        Descripción: Dice si la Cola está vacia.

        Descripción operacional: estavacia: Cola -> Booleano

        Precondición: cola pertenece a Cola.

        Poscondición: cola=<> => estavacia=verdadero o cola != <> => estavacia=falso.

    */

    int estavacia() { return cab == NULL; }

}; // class cola

// Operaciones:

/*

Operación Cola

    Descripción: Destruye la cola.

    Descripción operacional: construir: Cola ->.

    Precondición:

    Poscondición:

*/

template<class TipoB>

Cola<TipoB>::Cola()

{

    Nodo<TipoB> *ap = cab, *ap_sig;

    while(ap){

        ap_sig = ap->obtsig();

        delete ap;

        ap = ap_sig;

    }

} //Cola Cola<TipoB>::Cola()

/*

Operación adicionar

    Descripción: Adiciona un nuevo elemento a la Cola.

    Descripción operacional: adicionar:Cola x TipoB -> Cola.

    Precondición: cola pertenece a Cola y cola=(<elem[0],elem[1],elem[2],...,elem[n-1]>,elem[0],elem[n-1]) y nuevo pertenece a TipoB

    Poscondición: cola=(<elem[0],elem[1],elem[2],...,elem[n-1],nuevo>,elem[0],nuevo)

*/

template<class TipoB>

void Cola<TipoB>::adicionar(TipoB elem)

{

    // Paso 0: Pedir memoria para el nuevo nodo.

    Nodo<TipoB> *ap = new Nodo<TipoB>(elem);

    if(ap == NULL){

        throw NoHayMemoria();

    }

    if(cab == NULL){

        cab = ap;

        col = ap;

        return ;

    } 

    // Paso 1: reencadenar.

    col->modsig(ap);

    col = ap;

} //void Cola<TipoB>::adicionar(Tipo elem)

/*

Operación retirar

Descripción: Retira el primer elemento de la Cola.

Descripción operacional: retirar:Cola -> Tipo.

Precondición: cola pertenece a Cola y cola=(<elem[0],elem[1],elem[2],...,elem[n-1]>,elem[0],elem[n-1])

Poscondición: cola=(<elem[1],elem[2],...,elem[n-1]>,elem[1],elem[n-1]) y retirar=elem[0]

*/

template<class TipoB>

TipoB Cola<TipoB>::retirar()

{

     if(cab == NULL){

         throw NoHayCabeza();

    }

    // Paso 0:

    Nodo<TipoB> *ap = cab;

    // Paso 1: Reencadenar.

    cab = ap->obtsig();

    ap->modsig(NULL);

    TipoB info = ap->obtinf();

    delete ap;

    return info;

} //TipoB Cola<TipoB>::retirar()

#endif

//---------- Fin cola.h

Las dos operaciones importantes de ver en detalle son: adicionar y retirar. El código de adicionar es:

void Cola<TipoB>::adicionar(TipoB elem)

{

    // Paso 0: Pedir memoria para el nuevo nodo.

    Nodo<TipoB> *ap = new Nodo<TipoB>(elem);

    if(ap == NULL){

        throw NoHayMemoria();

    }

    if(cab == NULL){

        cab = ap;

        col = ap;

        return ;

    } 

    // Paso 1: reencadenar.

    col->modsig(ap);

    col = ap;

} //void Cola<TipoB>::adicionar(Tipo elem)

Cada uno de los pasos importantes está antecedido de un comentario y estos se correosponden con loas pasos en la figura

Figure: Pasos de la operación adicionar de Cola.

El paso 0 es pedir la memoria del Nodo que guarda la información. El paso 1, es reencadenar todos los apuntadores de tal forma que este nuevo nodo quede como la nueva cola.

El código de retirar es el siguiente:

TipoB Cola<TipoB>::retirar()

{

     if(cab == NULL){

         throw NoHayCabeza();

    }

    // Paso 0:

    Nodo<TipoB> *ap = cab;

    // Paso 1: Reencadenar.

    cab = ap->obtsig();

    ap->modsig(NULL);

    TipoB info = ap->obtinf();

    delete ap;

    return info;

} //TipoB Cola<TipoB>::retirar()

También aquí hemos marcados los ditintos pasos que se corresponden a los de la figura .

Figure: Pasos de la operación retirar de el TDA Cola.

El paso 0 consiste en colocar al apuntador ap en el Nodo que se va a retirar. Y el paso 1 consiste en reencadenar todos los apuntadores para dejar aislado este nodo. Después de esto se copia la información del Nodo, se libera el espacio en memoria ocupado por este y finalmente se retorna la información.

El siguiente código ilustra como se puede usar el TDA Cola:

/*

cola_prueba.cpp

Autor: L. Alejandro Bernal R.

Fecha: 2000.12.10

Descripción: Una prueba informal del TDA Cola.

*/

#include "cola.h"

#include <iostream.h>

int main()

{

    Cola<int> col;

    col.adicionar(20);

    col.adicionar(33);

    col.adicionar(67);

    col.adicionar(23);

    while(!col.estavacia()){

        cout << col.retirar() << '\n';

    }

    return 0;

}

//-------- Fin cola_prueba.cpp

El anterio código simplemente adiciona algunos elementos a la cola y los retira hasta que la Cola esté vacia.