Colas Pilas

Actividad de AEDI

Curso 2009/2010

Actividad 5. Uso de TADs
Objetivo: Implementar los ejercicios que se incluyen en esta actividad haciendo uso de los TADs lineales vistos en clase (Pilas, colas y secuencias). Para ello se proporciona el fichero aedi.jar (explicado en el anexo) con los TADs implementados y listos para usar. 6 Se hará una prueba evaluable sobre uso de TADs lineales en lasclases de prácticas en la semana del 16-20 de Noviembre

Núm. de horas: Fecha entrega:

Ejercicios sobre Pilas
1. Haciendo uso del TAD Pila, escribe: i) un método que reciba dos pilas como parámetro y devuelva el entero 1 si ambas pilas son iguales y 0 en caso contrario.
public static int iguales (Pila p1, Pila p2)

ii) un método que devuelva cierto si todos los elementos de una pila sonpositivos, suponiendo que la pila almacena valores del tipo Integer.
public static boolean positivos (Pila p)

iii) Escribe un algoritmo iterativo y otro recursivo que copie una pila. Los elementos de la pila resultante deben quedar en el mismo orden que los de la pila original:
public static Pila copia (Pila p)

2. Los datos se almacenan en la memoria de la computadora utilizando unarepresentación binaria. Esto significa que la representación de los enteros en base 10 que se utiliza en los programas debe convertirse a la representación en base 2. Uno de los algoritmos que realiza esta conversión consiste en dividir repetidamente el entero entre 2, siendo los restos de dichas divisiones los dígitos del número en la representación en base 2. Escribe un algoritmo que, haciendo uso deuna pila, convierta un entero positivo en base 10 a base 2 y muestre el resultado. 3. Escribe un método que lea una frase introducida por teclado y haciendo uso de una pila, presente esa frase invirtiendo los caracteres de cada palabra.

1

Actividad de AEDI

Curso 2009/2010

Ejercicios sobre Colas
1. El agente 009 ha inventado un nuevo método de codificación de mensajes secretos. Elmensaje original se codifica reemplazando cada sucesión de caracteres consecutivos que no sean vocales por su imagen especular. Por ejemplo: Mensaje original: "Bond, James Bond” Mensaje codificado: "BoJ ,dnameB sodn" Construye el algoritmo de codificación de mensajes, utilizando pilas y colas. Supón que el mensaje inicial viene dado como una cola de caracteres y la salida se devuelve también como unacola de caracteres.
public static Cola codificar (Cola mensaje)

2. En Correos un funcionario ha cerrado una ventanilla y la gente de la cola tiene que juntarse con la gente en la cola de otra ventanilla. Esta situación motiva la introducción de dos nuevas operaciones para colas:
public static void concatenar(Cola q1,Cola q2)
// Modifica: q1 // Produce: añade q2 a q1

public static Colabarajar (Cola q1, Cola q2)
// Produce: mezcla los elementos de q1 con los elementos de q2, de manera que los elementos de q2 ocupen posiciones impares y los elementos de q1 ocupen las

posiciones pares.

3. Una aplicación interesante de las colas es el concepto de ordenación raíz. Cualquier ordenación está basada en algún valor concreto, denominado clave de ordenación. En la ordenación raíz,lo que hacemos es crear colas separadas para cada valor posible de la clave de ordenación. El número de colas o el número de posibles valores, se denomina raíz o base. Por ejemplo, si estuviéramos ordenando números decimales, entonces la raíz sería diez, debiendo utilizar una cola para cada uno de los dígitos que van de 0 a 9. Por ejemplo, supongamos que queremos ordenar 10 números de 3 dígitos.Para simplificar las cosas, vamos a restringir los dígitos a los números comprendidos entre 0 y 5, lo que significa que solo utilizaremos 6 colas. Cada número de tres dígitos que hay que ordenar tiene una posición correspondiente a las unidades, otra a las decenas y otra correspondiente a las centenas. La ordenación raíz hará tres pasadas a través del conjunto de valores, una para cada posición de...