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 MaudeModifica

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 PseudollenguatgeModifica

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ènciesModifica

  1. «Cua circular». Arxivat de l'original el 2013-06-20. [Consulta: 3 octubre 2016].
  2. Estructura de datos

BibliografiaModifica

Vegeu tambéModifica