Una cua circular o anell és una estructura de dades en la qual els elements estan de forma circular i cada element té un successor i un predecessor. Els elements poden consultar, afegir i eliminar únicament des del cap de l'anell que és una posició distingida. Hi ha dues operacions de rotacions, una a cada sentit, de manera que el cap de l'anell passa a ser l'element successor, o el predecessor, respectivament, del cap actual.
Anell en Maude Exemple d'Anell en Maude:Estructura de datos fmod ANELL {X :: TRIV} is sorts AnellNV{X} Anell{X}. subsort AnellNV{X} < Anell{X}.
op crear : -> Anell{X} [ctor]. op insertar : X$Elt Anell{X} -> AnellNV {X} [ctor].
op eliminar : Anell{X} -> Anell{X}. ops rotarDret rotarEsq : Anell{X} -> Anell{X}. op cap : AnellNV{X} -> X$Elt. op esVuit? : Anell{X} -> Bool. op aLaCua : X$Elt Anell{X} -> Anell{X}. op elimCua : Anell{X} -> Anell{X}. op cua : AnellNV {X} -> X$Elt.
var A : Anell{X}. vars E E2 : X$Elt.
eq eliminar(crear) = crear. eq eliminar(insertar(E, A)) = A.
eq cap(insertar(E, A)) = E.
eq esVuit?(crear) = true. eq esVuit?(insertar(E, A)) = false.
eq cua(insertar(E, crear)) = E. eq cua(insertar(E, insertar(E2, A))) = cua(insertar(E2, A)).
eq elimCua(crear) = crear. eq elimCua(insertar(E, crear)) = crear. eq elimCua(insertar(E, insertar(E2, A))) = insertar(E, elimCua(insertar(E2, A))).
eq aLaCua(E, crear) = insertar(E, crear). eq aLaCua(E, insertar(E2, A)) = insertar(E2, aLaCua(E, A)).
eq rotarDret(crear) = crear. eq rotarDret(insertar(E, A)) = aLaCua(E, A).
eq rotarEsq(crear) = crear. eq rotarEsq(insertar(E, A)) = insertar(cua(insertar(E, A)), elimCua(insertar(E, A))). endfm
Anell en Pseudollenguatge FUNC CrearCua() : TCua VARIABLES cua: TCua INICI cua.front <- MAXCUA cua.final <- MAXCUA RESULTAT <- cua FINAL
PROC DestruirCua(&cua: TCua) INICI //No hay q hacer nada FINAL
FUNC CuaPlena(cua: TCua): LÒGIC INICI RESULTAT <- (cua.final MOD MAXCUA) + 1 = cua.front FINAL
FUNC CuaVuida(cua: TCua): LÒGIC INICI RESULTAT <- cua.final = cua.front FINAL
PROC PosarCua (&cua: TCua; &e: Telement; &error: Terror) VARIABLES final: NATURAL INICI SI CuaPlena(cua) LLAVORS error <- ErrorCuaPlena ALTRAMENT error <- NoError final <- (cua.final MOD MAXCUA) + 1 cua.final <- final cua.elements[final] <- e FINALSI FINAL
PROC TreureCua (&cua: TCua; &e: Telement; &error: Terror) VARIABLES ini: NATURAL INICI SI CuaVuida(cua) LLAVORS error <- ErrorCuaPlena ALTRAMENT error <- NoError ini <- (cua.front MOD MAXCUA) + 1 cua.front <- ini e <- cua.elements[ini] FINALSI FINAL
Referències
Bibliografia Isidre Guixà i Miranda Dades lineals en memòria dinàmica Vegeu també Cua (estructura de dades). Cua de prioritat (estructura de dades).
Categoria:Estructura de dades