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