PRÁCTICA Nş 5: 1 sesión

(del 9 de Abril al 27 de Abril de 2001)

Estructuras de datos lineales. Colas Estáticas y Dinámicas

0. Objetivo

El objetivo de esta práctica es la realización de dos clases en C++ que implementen el tipo abstracto de datos COLA (estática y dinámica), así como su utilización en un programa que simula el comportamiento simplificado de un ascensor.

1. EL tipo Abstracto de Datos COLA

Las Colas son otro tipo de estructuras lineales, cuyo funcionamiento se basa en una estrategia FIFO (First In, First Out), es decir, los elementos salen por orden de llegada a la cola, el primero en llegar es también el primero en salir.

Las operaciones de las que consta el TAD COLA son las siguientes

Que inicializa la cola como una cola vacía

Que devuelve true en caso de que la cola esté vacía

Que inserta un elemento, si es posible, en la última posición de la cola.

Que desencola, si es posible, el elemento situado en el inicio de la cola.

Que devuelve, si es posible, el valor situado en el inicio de la cola.

2. IMPLEMENTACIÓN DE LAS CLASES: COLA estática y dinámica

Se trata de implementar dos clases en C++ que implementen el tipo abstracto de datos Cola, de forma estática (vector con acceso circular) y dinámica (punteros). Ambas clases tendrán el mismo nombre, de forma que después pueda ser utilizada una clase u otra en el programa simulador, sin necesidad de cambio alguno en el código.

Las operaciones de manipulación de la cola, tanto en el caso estático, como en el dinámico, serán:

Cola (void);

Constructor de la clase. Inicia la cola a vacía.

bool ColaVacia (void);

Comprobación de si hay o no elementos en la cola

bool Encolar (char ch);

Encolará, si se puede, el carácter ch al final de la cola y devolverá true. Si no se puede, devolverá false.

bool Desencolar (void);

Si hay elementos en la cola, eliminará el primero y devolverá true. Si no hay elementos en la cola, devolverá false.

bool PrimeroCola (char & ch);

Si hay elementos en la cola, pondrá en ch el que esté en primera posición y devolverá true. Si no hay elementos en la cola devolverá false.

Además, es conveniente incluir una función que permita visualizar por pantalla la información que contiene una cola. Así se puede controlar en todo momento si las llamadas se almacenan correctamente y cuál es la secuencia de tareas que tiene que realizar el ascensor (se permitirá en este caso, y sólo en este caso, la utilización de la función ‘gotoxy’ para situar el cursor en un punto determinado de la pantalla y escribir en el. La función ‘gotoxy’ está en la ‘librería’ conio.h)

  1. programa simulador de un ascensor

El programa a realizar consiste en utilizar las clases implementadas en la simulación del funcionamiento de un ascensor. Obviamente, no se pretende que sea una simulación realista del comportamiento de este dispositivo, se tratará de una versión muy simplificada del mismo. El planteamiento del problema es el siguiente:

El ascensor está situado en un edificio de 4 plantas (añadir a éstas la planta baja, nivel 0).

Este ascensor responde a dos tipos de peticiones de funcionamiento:

Además, se utilizará el carácter 'f ' para finalizar el programa.

Los dos tipos de peticiones se gestionan independientemente y responden a criterios de temporalidad, de manera que las llamadas van siendo atendidas según el orden de solicitud. Esto implica que la información sobre las peticiones interiores y exteriores se almacenará en dos Colas independientes.

Con este planteamiento, hay que escribir un programa que simule el funcionamiento del ascensor de forma que las peticiones se realicen mediante pulsaciones del teclado en cualquier instante del proceso y, "al mismo tiempo", mover el ascensor a los pisos que se van solicitando.

La visualización del proceso se puede realizar utilizando la clase Ascensor, proporcionada por el profesor, que se encuentra implementada y ya compilada dentro del fichero "Ascensor.o". El fichero de cabecera será Ascensor.h, y también lo proporcionará el profesor.

Esta clase tiene un constructor que limpia la pantalla y proporciona un fondo y un método que responde al prototipo que se muestra a continuación y muestra por pantalla el movimiento del ascensor:

void Mover_Ascensor (int planta_destino);

planta_destino es el piso al que debe ir el ascensor.

El esquema algorítmico básico de la simulación debe ser el siguiente:

Mientras no sea el final (tecla pulsada 'f') hacer:

- Almacenar en las colas todas las peticiones que haya en el buffer de teclado.

- Visualizar el estado actual de peticiones.

- Determinar el próximo piso al que debe ir el ascensor.

- Mover el ascensor desde el piso actual al piso determinado en el paso anterior.

Fin_mientras

En ningún caso se pide la utilización de menús ni opciones en estos programas.

4. Entrega de programas

Al finalizar la siguiente sesión de prácticas se entregarán al profesor los archivos ‘cola_v.h’, ‘cola_v.cpp’, ‘cola_p.h’, ‘cola_p.cpp’ correspondientes al TAD cola con vectores y con punteros, y el programa principal ‘simula.cpp’.