Cua circular
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.[1]
Anell en Maude
[modifica]Exemple d'Anell en Maude:[2]
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
[modifica]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
[modifica]- ↑ «Cua circular». Arxivat de l'original el 2013-06-20. [Consulta: 3 octubre 2016].
- ↑ Estructura de datos
Bibliografia
[modifica]- Isidre Guixà i Miranda Dades lineals en memòria dinàmica