43 - Estructuras dinámicas en C: Listas tipo Cola - Problemas de aplicación

Listas tipo Cola - Problemas de aplicación

 Planteo del problema:

Este práctico tiene por objetivo mostrar la importancia de las colas en las Ciencias de la Computación y más precisamente en las simulaciones.
Las simulaciones permiten analizar situaciones de la realidad sin la necesidad de ejecutarlas realmente. Tiene el beneficio que su costo es muy inferior a hacer pruebas en la realidad.

Desarrollar un programa para la simulación de un cajero automático.
Se cuenta con la siguiente información:
- Llegan clientes a la puerta del cajero cada 2 ó 3 minutos.
- Cada cliente tarda entre 2 y 4 minutos para ser atendido.

Obtener la siguiente información:
1 - Cantidad de clientes que se atienden en 10 horas.
2 - Cantidad de clientes que hay en cola después de 10 horas.
3 - Hora de llegada del primer cliente que no es atendido luego de 10 horas (es decir la persona que está primera en la cola cuando se cumplen 10 horas)

Programa: programa165.c

Ver video

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include <time.h>

struct nodo {
    int info;
    struct nodo *sig;
};

struct nodo *raiz=NULL;
struct nodo *fondo=NULL;

int vacia()
{
    if (raiz == NULL)
        return 1;
    else
        return 0;
}

void insertar(int x)
{
    struct nodo *nuevo;
    nuevo=malloc(sizeof(struct nodo));
    nuevo->info=x;
    nuevo->sig=NULL;
    if (vacia())
    {
        raiz = nuevo;
        fondo = nuevo;
    }
    else
    {
        fondo->sig = nuevo;
        fondo = nuevo;
    }
}

int extraer()
{
    if (!vacia())
    {
        int informacion = raiz->info;
        struct nodo *bor = raiz;
        if (raiz == fondo)
        {
            raiz = NULL;
            fondo = NULL;
        }
        else
        {
            raiz = raiz->sig;
        }
        free(bor);
        return informacion;
    }
    else
        return -1;
}

void liberar()
{
    struct nodo *reco = raiz;
    struct nodo *bor;
    while (reco != NULL)
    {
        bor = reco;
        reco = reco->sig;
        free(bor);
    }
}

int cantidad()
{
    struct nodo *reco = raiz;
    int cant = 0;
    while (reco != NULL)
    {
        cant++;
        reco = reco->sig;
    }
    return cant;
}

void simulacion()
{
    srand(time(NULL));
    int estado = 0;
    int llegada = rand() % 2 + 2;
    int salida = -1;
    int cantAtendidas = 0;
    int minuto;
    for (minuto = 0; minuto < 600; minuto++)
    {
        if (llegada == minuto)
        {
            if (estado == 0)
            {
                estado = 1;
                salida = minuto + 2 + rand() % 3;
            }
            else
            {
                insertar(minuto);
            }
            llegada = minuto + 2 + rand() % 2;
        }
        if (salida == minuto)
        {
            estado = 0;
            cantAtendidas++;
            if (!vacia())
            {
                extraer();
                estado = 1;
                salida = minuto + 2 + rand() % 3;
            }
        }
    }
    printf("Atendidos:%i\n" ,cantAtendidas);
    printf("En cola:%i\n",cantidad());
    printf("Minuto llegada:%i",extraer());
}


int main()
{
    simulacion();
    liberar();
    getch();
    return 0;
}

Par administrar la estructura cola definimos las funciones de insertar, extraer, vacía, cantidad y liberar.

La función donde implementamos la lógica es en la función de simulacion, veamos las distintas partes:

    srand(time(NULL));
    int estado = 0;
    int llegada = rand() % 2 + 2;
    int salida = -1;
    int cantAtendidas = 0;
    int minuto;

Iniciamos la semilla de valores aleatorios llamando a srand y pasando el valor devuelto por la función time que se encuentra en el archivo de inclusión time.h.

La variable estado almacena un cero si el cajero está libre y un uno cuando está ocupado.
La variable llegada almacena en que minuto llegará el próximo cliente (debemos generar un valor entre 2 y 3)

La variable salida almacenará en que minuto terminará el cliente de ser atendido (como al principio el cajero está vacío inicializamos esta variable con -1)

Llevamos un contador para saber la cantidad de personas atendidas (cantAtendidas)

Disponemos un for que se repita 600 veces (600 minutos o lo que es lo mismo 10 horas)

    for (minuto = 0; minuto < 600; minuto++)

Dentro del for hay dos if fundamentales que verifican que sucede cuando llega una persona o cuando una persona se retira:

        if (llegada == minuto)
        {
            ............
        }
        if (salida == minuto)
        {
            ............
        }

Cuando llega una persona al cajero primero verificamos si el cajero está desocupado:

        if (llegada == minuto)
        {
            if (estado==0) {

Si está desocupado lo ocupamos cambiando el valor de la variable estado y generando en que minuto esta persona dejará el cajero (un valor aleatorio entre 2 y 4 minutos):

                estado = 1;
                salida = minuto + 2 + rand() % 3;

Si el cajero está ocupado procedemos a cargar dicha persona en la cola (insertamos el minuto que llega):

            else
            {
                insertar(minuto);
            }

Luego generamos el próximo minuto que llegará otra persona:

            llegada = minuto + 2 + rand() % 2;

El otro if importante es ver que sucede cuando sale la persona del cajero:

if (salida == minuto) {

Si sale una persona del cajero cambiamos el valor de la variable estado, incrementamos en uno el contador cantAtendidos y si la cola no está vacía extraemos una persona, cambiamos a uno la variable estado y generamos en que minuto dejará esta persona el cajero:

            estado = 0;
            cantAtendidas++;
            if (!vacia())
            {
                extraer();
                estado = 1;
                salida = minuto + 2 + rand() % 3;
            }

Fuera del for mostramos los tres resultados:

    printf("Atendidos:%i\n" ,cantAtendidas);
    printf("En cola:%i\n",cantidad());
    printf("Minuto llegada:%i",extraer());