Implementación TAD Cola

Const N:......;

Type

Telem:.....;

Tpuntero=^Nodo;

Nodo=record

elem:Telem;

sig:Tpuntero

end

Tcola=record

primero,ultimo:Tpuntero

end;

Procedure Crearcola(var cola:Tcola);

begin

cola.primero:=nil;

cola.ultimo:=nil

end;

Function Colavacia(cola:Tcola):boolean;

begin

Colavacia:=cola.primero=nil

end;

Procedure Encolar(var cola:Tcola;elem:Telem);

var aux:Tpuntero;

begin

new(aux);

aux^.elem:=elem;

aux^.sig:=nil;

if Colavacia(cola) then

cola.primero:=aux

else

cola.ultimo^.sig:=aux;

cola.ultimo:=aux

end;

Procedure Desencolar(var cola:Tcola);

var aux:Tpuntero;

begin

if not Colavacia(cola) then

with cola do

begin

aux:=primero;

primero:=primero^.sig;

dispose(aux)

if primero=nil then ultimo:=nil

end

else

writeln (`cola vacia')

end;

Procedure Primero(cola:Tcola;var elem:Telem);

begin

if not Colavacia(cola) then

elem:=cola.primero^.elem

else

writeln(`cola vacia')

end;

Problemas

* Funcion que obtenga el número de elementos contenidos en una cola

Function Elementos(var cola:Tcola):integer;

Function Calcular(var cola:Tcola):integer;

var elem:Telem;

begin

if not Colavacia(cola) then

begin

Primero(cola,elem);

Desencolar(cola);

Calcular:=Calcular(cola)+1;

Encolar(cola,elem)

end

else

Calcular:=0

end;

begin

Elementos:=(Calcular(cola)+Calcular(cola)) div 2

end;

Nota: En éste solo se efectúa un solo recorrido por la cola puesto que solo hay una llamada

` Elementos:=.....', sin embargo la funcion Calcular nos devuelve la cola invertida más el número de elementos, luego debemos llamar 2 veces a la función para que nos deje la cola igual y dividir por 2 para obtener el número de elementos.

* Procedimiento que invierte el contenido de una cola

Procedure Invertircola(var cola:Tcola);

var elem:Telem;

begin

if not Colavacia(cola) then

begin

Primero(cola,elem);

Desencolar(cola);

Invertircola(cola);

Encolar(cola,elem)

end

else

writeln(` cola vacia')

end;

* Procedimiento que inserta un elemento al principio de la cola

Procedure InsertarPrincipio(var cola:Tcola;elem:Telem);

begin

Invertir(cola);

Encolar(cola,elem);

Invertir(cola)

end;

* Procedimiento anterior conociendo el número de elementos en la cola

Procedure Insertar(var cola:Tcola;elem:Telem);

var

i:integer;

aux:Telem;

begin

Encolar(cola,elem);

For i:=1 to Elementos(cola)-1 do

begin

Primero(cola,aux);

Desencolar(cola);

Encolar(cola,aux)

end

end;

* Dada una cola de la que conocemos su número de elementos convertirla en capicúa. Solo se podrá efectuar un solo recorrido de la cola.

Procedure Capicua(var cola:Tcola; N:integer);

var elem:Telem;

begin

If N>0 then

begin

Primero(cola,elem);

Desencolar(cola);

Encolar(cola,elem);

Capicua(cola,N-1);

Encolar(cola,elem)

end

end;