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);
1
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
2
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
3
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
4
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;