Estructura de TRABAJO PRÁCTICO N° 4 - Ciclo 2023

Tema: Listas - Cola (Queue)

El trabajo práctico permite que cada estudiante conozca, distinga, desarrolle y utilice la o las implementaciones
o estructuras de datos del tipo de dato abstracto Queue o Cola.

Este trabajo práctico también está pensado para que cada estudiante desarrolle habilidades de búsqueda y
selección de información técnica y/o científica necesaria para resolver los ejercicios.

Casos Ejemplo

a) Encolar números en una cola hasta que se ingrese el número 99; luego desencolarlos y hacer lo
siguiente: calcular el factorial de los números positivos, sumar los negativos y contar los ceros.

b) Escribir una función, método o subprograma que reciba como parámetros dos colas y devuelva una
cola que resulte ser la unión de las otras dos. Se debe definir el mecanismo de “unión entre colas”,
puede ser que la primera cola se encole detrás de la segunda, o que la segunda cola se encole después
de la primera.

c) Dada una frase determinar si la misma es o no un palíndromo haciendo uso de una pila y una cola. No
se debe tener en cuenta los espacios en blanco.

Ejercicios propuestos

1) Codificar una implementación del tipo de dato abstracto Queue o Cola que utilice un arreglo como
contenedor de elementos, e implemente los conceptos vistos como “Cola Circular” para el caso de una cola
que prioriza memoria. Incluir el método existeEnCola(elemento) que devuelve el valor lógico verdadero
cuando elemento se encuentra en el objeto cola que llama al método, o el valor lógico falso en caso
contrario. Comprobar el correcto funcionamiento de la implementación propuesta creando una instancia
de la cola y utilizando las operaciones de la misma a pedido del operador. Para ello, puede usar un menú
de opciones.

Indicaciones:
Este ejercicio necesita del objeto scanner para ingresar datos por la consola o teclado, se espera que el
código controle los problemas que normalmente ocurren al operar con la consola o teclado.
Se espera una correcta modularización entre el código que realiza el ingreso y validación de los datos
respecto del código que hace lo que se solicita en el ejercicio.
El ejercicio debe implementar un mecanismo para seleccionar el ingreso de valores por consola o
generados aleatoriamente.

1
Estructura de TRABAJO PRÁCTICO N° 4 - Ciclo 2023
Tema: Listas - Cola (Queue)
Datos
INGENIERÍA INFORMÁTICA – LICENCIATURA EN SISTEMAS
FACULTAD DE INGENIERÍA – UNIVERSIDAD NACIONAL DE JUJUY

2) Codificar una implementación del tipo de dato abstracto Queue o Cola que utilice un arreglo como
contenedor de elementos, e implemente los conceptos vistos como “Cola Circular” para el caso de una cola
que prioriza velocidad. Comprobar el correcto funcionamiento de la implementación propuesta creando
una instancia de la cola y utilizando las operaciones de la misma a pedido del operador. Para ello, puede
usar un menú de opciones.

Indicaciones:
Este ejercicio necesita del objeto scanner para ingresar datos por la consola o teclado, se espera que el
código controle los problemas que normalmente ocurren al operar con la consola o teclado.
Se espera una correcta modularización entre el código que realiza el ingreso y validación de los datos
respecto del código que hace lo que se solicita en el ejercicio.
El ejercicio debe implementar un mecanismo para seleccionar el ingreso de valores por consola o
generados aleatoriamente.

3) Una bicola también es conocida como una cola doble y es una variante de la estructura de datos cola
simple. La variante consiste en que los elementos van a poder ser insertados o eliminados por cualquiera
de los dos extremos de la cola. Por tanto, la entrada o salida de elementos podrá efectuarse tanto por el
principio como por el final de la misma, aunque la estructura seguirá comportándose como una cola en
cuanto al procesamiento de elementos.

Implementar una bicola conforme a lo comentado anteriormente. Comprobar el correcto funcionamiento

Indicaciones:
Este ejercicio necesita del objeto scanner para ingresar datos por la consola o teclado, se espera que el
código controle los problemas que normalmente ocurren al operar con la consola o teclado.
Se espera una correcta modularización entre el código que realiza el ingreso y validación de los datos
respecto del código que hace lo que se solicita en el ejercicio.
El ejercicio debe implementar un mecanismo para seleccionar el ingreso de valores por consola o
generados aleatoriamente.

4) Escribir una función, método o subprograma que reciba como parámetros dos colas y devuelva una cola
que resulte ser la unión de las otras dos, sin elementos repetidos. Para este caso el mecanismo de “unión
entre colas” es en el que sucesiva y alternadamente se toma un elemento de cada cola y se encola en una

2
Estructura de TRABAJO PRÁCTICO N° 4 - Ciclo 2023
Tema: Listas - Cola (Queue)
Datos
INGENIERÍA INFORMÁTICA – LICENCIATURA EN SISTEMAS
FACULTAD DE INGENIERÍA – UNIVERSIDAD NACIONAL DE JUJUY

nueva. El mecanismo de unión debe incluir las consideraciones necesarias para incorporar solo una vez
cada valor a la cola resultante de manera que no haya elementos repetidos. Considere que las colas
pueden ser de longitudes diferentes.

Indicaciones:
Este ejercicio necesita del objeto scanner para ingresar datos por la consola o teclado, se espera que el
código controle los problemas que normalmente ocurren al operar con la consola o teclado.
Se espera una correcta modularización entre el código que realiza el ingreso y validación de los datos
respecto del código que hace lo que se solicita en el ejercicio.
El ejercicio debe implementar un mecanismo para seleccionar el ingreso de valores por consola o
generados aleatoriamente.

5) Cifrado es una técnica que permite “codificar” un mensaje (cadena de caracteres) utilizando una clave de
cifrado y un procedimiento. Solamente las personas que conozcan el procedimiento y la clave de cifrado
pueden “decodificar” el texto cifrado y obtener el mensaje original.
A continuación se explicará una forma muy pero muy simple de cifrar (codificar) que nos permitirá
practicar el uso del tipo de dato abstracto cola y sus implementaciones o estructuras de datos.
Sabemos que los caracteres son en realidad la implementación de un tipo de dato abstracto definido como
una colección de símbolos de un alfabeto y las operaciones permitidas son las de comparaciones. El
alfabeto que se menciona en la definición es el que indica la secuencia en que los símbolos se encuentran
en la colección, de ese modo podemos saber que ‘A’ es menor ‘R’, porque el símbolo ‘A’ se encuentra en
el alfabeto antes que el símbolo ‘R’.
Un objeto del tipo char (carácter) se puede ver como si fuese un entero utilizando el “casting” para
convertir el tipo de dato; lo que se está viendo es su código o ubicación dentro de la colección que
mantiene el alfabeto. De este modo se puede ejecutar el siguiente código:

char letra = 'A';

System.out.println((int)letra);

Lo que aparece en la consola es el número 65 que resulta ser el código del símbolo ‘A’. También se puede
ejecutar el siguiente código:

char letra = 'A';

System.out.println((int)letra + 3);

3
Estructura de TRABAJO PRÁCTICO N° 4 - Ciclo 2023
Tema: Listas - Cola (Queue)
Datos
INGENIERÍA INFORMÁTICA – LICENCIATURA EN SISTEMAS
FACULTAD DE INGENIERÍA – UNIVERSIDAD NACIONAL DE JUJUY

Entonces aparecerá el valor 68, pero lo más interesante de esta situación es que podemos volver a realizar
el “casting” y mostrar que símbolo le corresponde al valor 68, o sea:

char letra = 'A';

System.out.println((char)((int)letra + 3));

En este caso lo que aparece en la consola es el símbolo ‘D’, obviamente es el que está tres lugares después
del símbolo ‘A’.
Este concepto nos permite elaborar un simple mecanismo de cifrado; “le sumemos a todos los símbolos
de una cadena el número 3 para obtener otra cadena”.

String original = "HOLA";

String codificado = "";

for (char c: original.toCharArray())

codificado += (char)((int)c + 3);

System.out.println(codificado);

Para decodificar el texto cifrado bastará con restar a cada símbolo el valor 3 y obtener entonces el
mensaje original.
Lamentablemente esta técnica es demasiado sencilla, dado que se puede hacer pruebas hasta encontrar el
valor que se suma y una vez conocido entonces se puede decodificar cualquier texto cifrado.
Una técnica más elaborada sería utilizar un vector de valores en lugar de un solo valor para todos los
símbolos, de este modo a cada símbolo del mensaje original le tocaría un valor diferente
El siguiente cuadro muestra la idea, en la primera fila se tienen los distintos valores, en este caso un vector
de cuatro elementos {5, 2, 8, 1}; en la segunda fila se tiene el mensaje original y en la última fila los
símbolos que resultan de tomar el valor correspondiente al símbolo del mensaje original y sumarle el valor
de la clave de cifrado.

4
Estructura de TRABAJO PRÁCTICO N° 4 - Ciclo 2023
Tema: Listas - Cola (Queue)
Datos
INGENIERÍA INFORMÁTICA – LICENCIATURA EN SISTEMAS
FACULTAD DE INGENIERÍA – UNIVERSIDAD NACIONAL DE JUJUY

5 2 8 1

H O L A Q U E T A L

M Q T B

Para que esto funcione tendríamos que tener tantos valores como símbolos tiene el mensaje original, sin
embargo es posible implementar un codificador que “reutilice” los valores de la clave de cifrado, entonces
quedaría de esta manera:

5 2 8 1 5 2 8 1 5 2 8 1

H O L A Q U E T A L

M Q T B % S ] F % V I M

Se puede ver que la clave de cifrado se repite al finalizar la misma. Esa forma de reutilizar los valores de la
clave de cifrado se puede lograr con una estructura de datos que tenga comportamiento FIFO, o sea una
cola.
Teniendo en cuenta lo antes mencionado, deberá crear los métodos que permitan Codificar y Decodificar
una cadena de caracteres (mensaje) para una determinada clave (vector de valores).

Indicaciones:
Este ejercicio necesita del objeto scanner para ingresar datos por la consola o teclado, se espera que el
código controle los problemas que normalmente ocurren al operar con la consola o teclado.

5
Estructura de TRABAJO PRÁCTICO N° 4 - Ciclo 2023
Tema: Listas - Cola (Queue)
Datos
INGENIERÍA INFORMÁTICA – LICENCIATURA EN SISTEMAS
FACULTAD DE INGENIERÍA – UNIVERSIDAD NACIONAL DE JUJUY

Se espera una correcta modularización entre el código que realiza el ingreso y validación de los datos
respecto del código que hace lo que se solicita en el ejercicio.
El ejercicio debe implementar un mecanismo para seleccionar el ingreso de valores por consola o
generados aleatoriamente.

6) Existe una técnica de cifrado conocida como DES Data Encryption Standard, que recibe un mensaje y una
clave y devuelve el mensaje codificado. Resulta que con las computadoras de hoy en día el DES es bastante
fácil de “romper” o descifrar, entonces lo que conviene utilizar es una técnica conocida como Triple-DES,
que utiliza tres claves; de manera que el mensaje original es cifrado tres veces, una vez con cada clave
haciendo bastante difícil la tarea de “romper” o descifrar el mensaje. Utilizando la técnica descripta en el
ejercicio anterior implemente una versión propia de Triple-DES, de manera que, como en el ejercicio 4,
deberá crear los métodos que permitan Codificar y Decodificar una cadena de caracteres aplicando en este
caso tres claves.

Indicaciones:
Este ejercicio necesita del objeto scanner para ingresar datos por la consola o teclado, se espera que el
código controle los problemas que normalmente ocurren al operar con la consola o teclado.
Se espera una correcta modularización entre el código que realiza el ingreso y validación de los datos
respecto del código que hace lo que se solicita en el ejercicio.
El ejercicio debe implementar un mecanismo para seleccionar el ingreso de valores por consola o
generados aleatoriamente.