Cola circular

Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden cosultarse, añadirse y eliminarse unicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

Anillo en Maude

fmod ANILLO {X :: TRIV} is
	sorts AnilloNV{X} Anillo{X} .
	subsort AnilloNV{X} < Anillo{X} .

	op crear : -> Anillo{X} [ctor] .
	op insertar : X$Elt Anillo{X} -> AnilloNV {X} [ctor] .

	op eliminar : Anillo{X} -> Anillo{X} .
	ops rotarDch rotarIzq : Anillo{X} -> Anillo{X} .
	op cabeza : AnilloNV{X} -> X$Elt .
	op esVacio? : Anillo{X} -> Bool .
	op aLaCola : X$Elt Anillo{X} -> Anillo{X} .
	op elimCola : Anillo{X} -> Anillo{X} .
	op cola : AnilloNV {X} -> X$Elt .

	var A : Anillo{X} .
	vars E E2 : X$Elt .

	eq eliminar(crear) = crear .
	eq eliminar(insertar(E, A)) = A .

	eq cabeza(insertar(E, A)) = E .

	eq esVacio?(crear) = true .
	eq esVacio?(insertar(E, A)) = false .

	eq cola(insertar(E, crear)) = E .
	eq cola(insertar(E, insertar(E2, A))) = cola(insertar(E2, A)) .

	eq elimCola(crear) = crear .
	eq elimCola(insertar(E, crear)) = crear .
	eq elimCola(insertar(E, insertar(E2, A))) = insertar(E, elimCola(insertar(E2, A))) .

	eq aLaCola(E, crear) = insertar(E, crear) .
	eq aLaCola(E, insertar(E2, A)) = insertar(E2, aLaCola(E, A)) .

	eq rotarDch(crear) = crear .
	eq rotarDch(insertar(E, A)) = aLaCola(E, A) .

	eq rotarIzq(crear) = crear .
	eq rotarIzq(insertar(E, A)) = insertar(cola(insertar(E, A)), elimCola(insertar(E, A))) .
endfm

Anillo en Pseudolenguaje

FUNC CrearCola() : TCola
VARIABLES
cola: TCola
INICIO
	cola.frente <- MAXCOLA
	cola.final <- MAXCOLA
	RESULTADO <- cola
FIN

PROC DestruirCola(&cola: TCola)
INICIO
//No hay q hacer nada
FIN

FUNC ColaLlena(cola: TCola): LÓGICO
INICIO
	RESULTADO <- (cola.final MOD MAXCOLA) + 1 = cola.frente
FIN

FUNC ColaVacia(cola: TCola): LÓGICO
INICIO
	RESULTADO <- cola.final = cola.frente
FIN


PROC MeterCola (&cola: TCola; &e: Telemento; &error: Terror)
VARIABLES
fin: NATURAL
INICIO
	SI ColaLlena(cola) ENTONCES
		error <- ErrorColaLlena
	EN OTRO CASO
		error <- NoError
		fin <- (cola.final MOD MAXCOLA) + 1
		cola.final <- fin
		cola.elementos[fin] <- e
	FINSI
FIN

PROC SacarCola (&cola: TCola; &e: Telemento; &error: Terror)
VARIABLES
	ini: NATURAL
INICIO
	SI ColaVacia(cola) ENTONCES
                error <- ErrorColaLlena
	EN OTRO CASO
		error <- NoError
		ini <- (cola.frente MOD MAXCOLA) + 1
		cola.frente <- ini
		e <- cola.elementos[ini]
	FINSI
FIN

Véase también

• Cola (estructura de datos)
• Cola de prioridad (estructura de datos)
• Bicola