Implementación Eficiente de TDA Cola: Optimización de Procedimientos y Almacenamiento

TDA Cola

Implementación de TDA Cola que prioriza velocidad de procedimiento

CONST
max = 10

TIPO
t_cola = registro
contenedor = array[1…max] de tipo_dato
e, s = entero
fin_registro

VAR
cola = t_cola

e: posición en la que debe ingresar el nuevo elemento
s (frente): posición de la cual se debe extraer un elemento

Proc. inicializar_cola (var cola: t_cola)
INICIO
cola.e = 1
cola.s = 1
FIN

Función cola_vacia (cola: t_cola): lógico
INICIO
cola_vacia = (cola.s = cola.e)
FIN

Proc. agregar_cola (var cola: t_cola, nuevo: tipo_dato)
INICIO
Si (NO(cola_llena(cola))) entonces
cola.contenedor[cola.e] = nuevo
cola.e = SIG(cola.e)
Sino
Escribir «Cola llena»
Fin_Si
FIN

Función sacar_cola (var cola: t_cola): tipo_dato
VAR
sacado = tipo_dato

e: posición en la que debe ingresar el nuevo elemento
s (frente): posición de la cual se debe extraer un elemento

Proc. inicializar_cola (var cola: t_cola)
INICIO
cola.e = 1
cola.s = 1
FIN

Función cola_vacia (cola: t_cola): lógico
INICIO
cola_vacia = (cola.s = cola.e)
FIN

Función sacar_cola (var cola: t_cola): tipo_dato
VAR
sacado = tipo_dato
INICIO
sacado = NULL
Si (NO(cola_vacia(cola))) entonces
sacado = cola.contenedor[cola.s]
cola.s = SIG(cola.s)
Fin_Si
sacar_cola = sacado
FIN

Función SIG (num: entero): entero
VAR
siguiente = entero
INICIO
Si (num = max) entonces
siguiente = 1
Sino
siguiente = num + 1
Fin_Si
SIG = siguiente
FIN

Función cola_llena (cola: t_cola): lógico
INICIO
cola_llena = (SIG(cola.e) = cola.s)
FIN

Implementación de TDA Cola que prioriza espacio de almacenamiento.

CONST
max = 10
TIPO
t_cola = registro
contenedor = array[1…max] de tipo_dato
e, s, c = entero
fin_registro

VAR
cola = t_cola

Proc. inicializar_cola (var cola: t_cola)
INICIO
cola.e = 1
cola.s = 1
cola.c = 0
FIN

Proc. agregar_cola (var cola: t_cola, nuevo: tipo_dato)
INICIO
Si (NO(cola_llena(cola))) entonces
cola.contenedor[cola.e] = nuevo
cola.e = SIG(cola.e)
cola.c = cola.c + 1
Sino
Escribir «Cola llena»
Fin_Si
FIN

Función cola_vacia (cola: t_cola): lógico
INICIO
cola_vacia = (cola.c = 0)
FIN

Función cola_llena (cola: t_cola): lógico
INICIO
cola_llena = (cola.c = max)
FIN

Función SIG (num: entero): entero
VAR
siguiente = entero
INICIO
Si (num = max) entonces
siguiente = 1
Sino
siguiente = num + 1
Fin_Si
SIG = siguiente
FIN

Consultar

CONST
max = 10

TIPO
t_cola = registro
contenedor = array[1…max] de tipo_dato
e, s = entero
fin_registro

VAR
cola = t_cola

Función consultar_frente (cola: t_cola): tipo_dato
VAR
consultado = tipo_dato
INICIO
consultado = NULL
Si (NO(cola_vacia(cola))) entonces
consultado = cola.contenedor[cola.s]
Fin_Si
consultar_frente = consultado
FIN

Función consultar_final (cola: t_cola): tipo_dato
VAR
consultado = tipo_dato
INICIO
consultado = NULL
Si (NO(cola_vacia(cola))) entonces
consultado = cola.contenedor[ANT(cola.e)]
Fin_Si
consultar_final = consultado
FIN

Función ANT (num: entero): entero
INICIO
Si (num = 1) entonces
ANT = max
Sino
ANT = num – 1
Fin_Si
FIN

Prioriza velocidad de procedimiento:

Función Consultar_Cant_Elem (cola: t_cola): entero
INICIO
Si (NO(cola_vacia(cola))) entonces
Si (cola.e) > 0
CCE = (max – cola.s) + cola.e
Sino
Si (cola_llena(cola)) entonces
CCE = max – 1
Sino
CCE = 0
Fin_Si
Fin_Si
Sino
CCE = max – 1
Fin_Si
FIN

Prioriza espacio de almacenamiento:

Función Consultar_Cant_Elem (cola: t_cola): entero
INICIO
Si (NO(cola_vacia(cola))) entonces
Si (cola.e) > 0
CCE = cola.c
Sino
Si (cola_llena(cola)) entonces
CCE = max – 1
Sino
CCE = 0
Fin_Si
Fin_Si
Sino
CCE = max – 1
Fin_Si
FIN

CONST
max = 10

TIPO
t_cola = array[1…max] de tipo_dato

VAR
cola = t_cola

Proc. inicializar_cola (var cola: t_cola)
INICIO
cola[1] = 3
cola[2] = 3
FIN

Proc. agregar_cola (var cola: t_cola, nuevo: tipo_dato)
INICIO
Si (NO(cola_llena(cola))) entonces
cola[cola[1]] = nuevo
cola[1] = SIG(cola[1])
Sino
Escribir «Cola llena»
Fin_Si
FIN

Función sacar_cola (var cola: t_cola): tipo_dato
VAR
sacado = tipo_dato
INICIO
sacado = NULL
Si (NO(cola_vacia(cola))) entonces
sacado = cola[cola[2]]
cola[2] = SIG(cola[2])
Fin_Si
sacar_cola = sacado
FIN

CONST
max = 10

TIPO
t_cola = registro
contenedor = array[1…max] de tipo_dato
e, s = entero
fin_registro

VAR
cola = t_cola

Proc. inicializar_cola (var cola: t_cola)
INICIO
cola.e = max
cola.s = max
FIN

Función cola_vacia (cola: t_cola): lógico
INICIO
cola_vacia = (cola.e = cola.s)
FIN

Proc. agregar_cola (var cola: t_cola, nuevo: tipo_dato)
INICIO
Si (NO(cola_llena(cola))) entonces
cola.contenedor[cola.e] = nuevo
cola.e = ANT(cola.e)
Sino
Escribir «Cola llena»
Fin_Si
FIN

Función ANT (num: entero): entero
INICIO
Si (num = 1) entonces
ANT = max
Sino
ANT = num – 1
Fin_Si
FIN

Función cola_llena (cola: t_cola): lógico
INICIO
cola_llena = (ANT(cola.e) = cola.s)
FIN

Función CCE (cola: t_cola): entero
INICIO
Si (NO(cola_vacia(cola))) entonces
Si (cola.e) > 0
CCE = (max – cola.e) + cola.s
Sino
CCE = cola.s – cola.e
Fin_Si
Sino
CCE = max – 1
Fin_Si
FIN

CONST
max = 5

TIPO
t_cola = registro
contenedor1 = array[1…max] de tipo_dato
contenedor2 = array[1…max] de tipo_dato
contenedor3 = array[1…max] de tipo_dato
e, s, c = entero
fin_registro

VAR
cola = t_cola

Proc. inicializar_cola (var cola: t_cola)
INICIO
cola.e = 1
cola.s = 1
cola.c = 0
FIN

Proc. agregar_cola (var cola: t_cola, nuevo: tipo_dato)
INICIO
Si (NO(cola_llena(cola))) entonces
Si (cola.e >= 1) y (cola.e <= 5) entonces
cola.contenedor1[cola.e] = nuevo
Sino
Si (cola.e >= 6) y (cola.e <= 10) entonces
cola.contenedor2[cola.e] = nuevo
Sino
cola.contenedor3[cola.e] = nuevo
Fin_Si
cola.e = SIG(cola.e)
cola.c = cola.c + 1
Sino
Escribir «Cola llena»
Fin_Si
FIN

Función cola_vacia (cola: t_cola): lógico
INICIO
cola_vacia = (cola.c = 0)
FIN

Función cola_llena (cola: t_cola): lógico
INICIO
cola_llena = (cola.c = max * 3)
FIN

Función sacar_cola (var cola: t_cola): tipo_dato
VAR
sacado = tipo_dato
INICIO
sacado = NULL
Si (NO(cola_vacia(cola))) entonces
Si (cola.s >= 1) y (cola.s <= 5) entonces
sacado = cola.contenedor1[cola.s]
Sino
Si (cola.s >= 6) y (cola.s <= 10) entonces
sacado = cola.contenedor2[cola.s]
Sino
sacado = cola.contenedor3[cola.s]
Fin_Si
cola.s = SIG(cola.s)
cola.c = cola.c – 1
Fin_Si
sacar_cola = sacado
FIN

Función SIG (num: entero): entero
VAR
siguiente = entero
INICIO
Si (num = 3 * max) entonces
siguiente = 1
Sino
siguiente = num + 1
Fin_Si
SIG = siguiente
FIN

CONST
max = 100

TIPO
t_cola = registro
contenedor = array[1…max] de carácter
ei, si, ep, sp, cp = entero
fin_registro

VAR
cola = t_cola
opción = entero

Proc. inicializar_cola (var cola: t_cola)
INICIO
cola.ei = 1
cola.si = 1
cola.ep = 2
cola.sp = 2
cola.cp = 0
FIN

Proc. agregar_cola (var cola: t_cola, nuevo: carácter, opción: entero)
INICIO
Si (NO(cola_llena(cola, opción))) entonces
Según opción hacer
1: cola.contenedor[cola.ei] = nuevo
cola.ei = SIG(cola.ei)
2: cola.contenedor[cola.ep] = nuevo
1: sacado = cola.contenedor[cola.si]
cola.si = SIG(cola.si)
2: sacado = cola.contenedor[cola.sp]
cola.sp = SIG(cola.sp)
cola.cp = cola.cp – 1
Fin_Segun
FIN

Punto 7

CONST
MAX: 100

TIPO
t_cola: Registro
contenedor: array [1…MAX] de carácter
e, s: entero
FinRegistro

t_cadena: array [1…MAX] de carácter

VAR
Cola: t_cola
Cadena: t_cadena

Procedimiento Palindromo(cadena: t_cadena)
VAR
Sacado: carácter
i: entero
cola: t_cola
band: lógico
INICIO
i := 1
band := VERDADERO
Mientras i <= longitud(cadena) hacer
Cargar-Cola(cola, cadena[i])
i := i + 1
FinMientras
i := longitud(cadena)
Mientras i >= 1 y band = VERDADERO hacer
Mientras cadena[i] = » » hacer
i := i – 1
FinMientras
Sacado := Sacar-Cola(cola)
Mientras sacado = » » hacer
Sacado := Sacar-Cola(cola)
FinMientras
Si sacado <> cadena[i] entonces
band := FALSO
FinSi
i := i – 1
FinMientras
Si band = VERDADERO entonces
Escribir «La frase es un palíndromo»
Sino
Escribir «La frase no es un palíndromo»
FinSi
FIN

Punto 9

CONST
MAX: 100

TIPO
t_cola: Registro
contenedor: array [1…MAX] de tipo-dato
e, s: entero
FinRegistro

VAR
Cola: t_cola

/* Si opción = 1 entonces la operación de agregar se realiza por el frente. Si opción = 2 entonces la operación de agregar se realiza por el final.

Procedimiento Agregar_Cola(var cola: t_cola, nuevo: tipo-dato, opción: entero)
INICIO

Si NO(COLA-LLENA(cola)) entonces
Según opción hacer
1: cola.contenedor[ANT(cola.s)] := nuevo
cola.s := ANT(cola.s)
2: cola.contenedor[cola.e] := nuevo
cola.e := SIG(cola.e)
FinSegun
FinSi
FIN

Función SIG(num: entero): entero
INICIO
Si (num = MAX) entonces
num := 1
Sino
num := num + 1
FinSi
SIG := num
FIN

Función ANT(num: entero): entero
INICIO
Si (num = 1) entonces
num := MAX
Sino
num := num – 1
FinSi
ANT := num
FIN

Punto 10

CONST
MAX: 100

TIPO
t_cola: Registro
contenedor: array [1…MAX] de tipo-dato
e, s: entero
FinRegistro

VAR
Cola: t_cola

/* Si opción = 1 entonces la eliminación se realiza por el frente. Si opción = 2 entonces la eliminación se realiza por el final.

Función Eliminar_Cola(var cola: t_cola, opción: entero): tipo-dato
VAR
sacado: tipo-dato
INICIO
sacado = NULL
Si NO(COLA-VACIA(cola)) entonces
Según opción hacer
1: sacado = cola.contenedor[cola.s]
cola.s = SIG(cola.s)
2: sacado = cola.contenedor[ANT(cola.e)]
cola.e = ANT(cola.e)
FinSegun
FinSi
Eliminar_Cola = sacado
FIN

Función SIG(num: entero): entero
INICIO
Si (num = MAX) entonces
num := 1
Sino
num := num + 1
FinSi
SIG := num
FIN

Función ANT(num: entero): entero
INICIO
Si (num = 1) entonces
num := MAX
Sino
num := num – 1
FinSi
ANT := num
FIN

TDA Cola

Deja una respuesta Cancelar la respuesta