MAC0122  Princípios de Desenvolvimento de Algoritmos
Home  |   Administração  |   Fórum  |   Livros  |   WWW  |   Diário  |   Tarefas  |   Alunos

 

Filas

Esta página foi extraída (com várias modificações) do capítulo 10 (Linear Structures) do livro de Eric Roberts. 

Diz-se que uma das extremidades de uma fila é o início ou cabeça (= head) e a outra extremidade é o fim ou cauda (= tail) da fila. Objetos são inseridos no fim da fila e são removidos do início da fila.

 

Implementação de uma fila em lista encadeada

Segue uma implementação de uma fila de objetos do tipo elementT.  A fila será implementada em uma lista encadeada. As células da lista serão do tipo cellT. 

typedef struct cellT {
   elementT     *element;
   struct cellT *link;
} cellT;


//////////////////////////////////////////////////////////
// Implementação de uma fila (= queue)
// A fila será representada por um registro do tipo queueT 
// que tem dois campos: o endereço do início da fila e o 
// endereço do fim da fila. Uma fila q será considerada 
// vazia se q->head == NULL. A fila propriamente dita será 
// uma lista encadeada com células do tipo cellT.
//////////////////////////////////////////////////////////

typedef struct {
   cellT *head;
   cellT *tail;
} queueT;


// Operação de inserção: coloca element na fila q.

void Enqueue( queueT *q, elementT *element) {
   cellT *cp;
   cp = malloc( sizeof (cellT));
   if (cp == NULL) exit( EXIT_FAILURE);
   cp->element = element;
   cp->link = NULL;
   if (q->head == NULL) q->head = cp;
   else q->tail->link= cp;
   q->tail = cp;
}

// Operação de remoção: retira um objeto da fila q e
// devolve o valor desse objeto. 

elementT *Dequeue( queueT *q) {
   elementT *result;
   cellT *cp;
   cp = q->head;
   if (cp == NULL) {
      printf( "Erro: a fila está vazia");
      exit( EXIT_FAILURE);
   }
   result = cp->element;
   q->head = cp->link;
   free( cp);
   return result;
}

Além das funções de inserção e remoção, é bom que o pacote de manipulação de filas tenha algumas funções "auxiliares": 



// Cria uma fila vazia e devolve o endereço da nova fila.

queueT *NewQueue( void) {
   queueT *q;
   q = malloc( sizeof (queueT));
   if (q == NULL) exit( EXIT_FAILURE);
   q->head = NULL;
   return q;
}

// Libera o espaço ocupado pela fila q. A função supõe que
// o espaço apontado pelo campo element de cada célula da
// lista tenha sido alocado por malloc.

void FreeQueue( queueT *q) {
   cellT *cp, *next;
   cp = q->head;
   while (cp != NULL) {
      next = cp->link;
      free( cp->element);
      free( cp);
      cp = next;
   }
   free( q);
}

// Devolve 1 se a fila q está vazia e 0 em caso contrário.

int QueueIsEmpty( queueT *q) {
   return q->head == NULL;
}

// Devolve o comprimento da fila q.

int QueueLength( queueT *q) {
   int n;
   cellT *cp;
   n = 0;
   for (cp = q->head; cp != NULL; cp = cp->link) n++;
   return n;
}

 

Exercícios

  1. Descreva os detalhes da implementação de uma fila em um vetor. Escreva as funções de inserção (Enqueue) e remoção (Dequeue). Escreva também uma função que verifique se a fila está vazia e outra que verifique se a fila está cheia. 

 

Simulação de uma fila de supermercado

Vamos usar a implementação de fila descrita acima, apenas trocando elementT por clienteT e portanto a definição de cellT por 

typedef struct cellT {
   clienteT     *element;
   struct cellT *link;
} cellT;

Observe que o programa de simulação faz questão de manipular a fila apenas através das funções Enqueue, Dequeue, NewQueue, FreeQueue, QueueIsEmpty e QueueLength.  O programa de simulação faz questão de não se referir diretamente as campos head, tail, link da estrutura da fila. 

// Programa checkout.c
// -------------------
// Este programa simula a fila diante de um caixa de supermercado.
// Clientes chegam e entram na fila. Cada cliente espera na fila 
// até que o caixa esteja livre. Quando isso acontece, o caixa 
// tira o primeiro cliente da fila e passa a atendê-lo durante um 
// certo tempo, escolhido aleatoriamente entre os parâmetros 
// TempoMinAtendimento e TempoMaxAtendimento. Quando tiver 
// terminado o atendimento, o caixa dispensa o cliente e chama o 
// próximo da fila. 
//
// Em cada unidade de tempo, começando na unidade 0 e terminando 
// na unidade DuracaoDaSimulacao, o programa executa as seguintes 
// operações:
// 1. Verifica se um novo cliente chegou. Novos clientes chegam
//    aleatoriamente com probabilidade determinada pelo parâmetro 
//    ProbabilidadeDeEntrada.
// 2. Se o tempo de atendimento do cliente ativo (ou seja, do 
//    cliente que está sendo atendido) já estiver esgotado, o 
//    cliente ativo é dispensado. Senão, uma unidade é subtraída 
//    do tempo de atendimento do cliente ativo.
// 3. Se o caixa estiver livre, o programa chama o próximo cliente
//    da fila.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef enum {FALSE, TRUE} bool;



//////////////////////////////////////////////////////////////
// Seção 1: Parametros da simulação e o tipo-de-dados clienteT
//////////////////////////////////////////////////////////////

// DuracaoDaSimulacao: quantas unidades de tempo vai durar a 
//    simulação
// ProbabilidadeDeEntrada: probabilidade de que um novo cliente 
//    entre na fila durante a unidade de tempo
// TempoMinAtendimento: duração mínima de permanência do cliente 
//    no caixa
// TempoMaxAtendimento: duração máxima de permanência do cliente 
//    no caixa

#define DuracaoDaSimulacao       200
#define ProbabilidadeDeEntrada     0.2
#define TempoMinAtendimento        5
#define TempoMaxAtendimento       20

// Tipo clienteT: Cada cliente é um struct que contém 
//  . número do cliente
//  . instante de entrada na fila
//  . tempo que o cliente ficará no caixa (um número aleatório
//      entre TempoMinAtendimento and TempoMaxAtendimento)

typedef struct {
   int numeroCliente;
   int instanteEntrada;
   int tempoDeAtendimento;
} clienteT;



////////////////////////////////////////////////////////////
// Seção 3: Demais tipos-de-dados da simulação e protótipos
//          de funções
////////////////////////////////////////////////////////////

// Tipo dadosDaSimulacaoT: Esse tipo-de-dados armazena os dados
// da simulação. Eis alguns dos campos:
// . clienteAtivo: vale NULL ou aponta para o cliente que está 
//       sendo atendido
// . fila: aponta para a fila de clients (o cliente ativo não
//       está mais na fila)
// . somaComprimentos: é a soma dos comprimentos da fila em
//       todos os instantes da simulação

typedef struct {
   queueT   *fila;
   clienteT *clienteAtivo;
   int       tempo;
   int       numeroDeClientes;
   int       numeroDeAtendidos;
   int       somaTemposDeEspera;
   int       somaComprimentos;
} dadosDaSimulacaoT;



//////////////////////////////////////////////////
// Seção 4: Programa principal
// ---------------------------
// Digite "-t" se deseja que o programa imprima um 
// histórico da simulação.
//////////////////////////////////////////////////

void   ExecutaSimulacao( dadosDaSimulacaoT *sim);
void   ColocaClienteNaFila( dadosDaSimulacaoT *sim);
void   ProcessaFila( dadosDaSimulacaoT *sim);
void   AtendeCliente( dadosDaSimulacaoT *sim);
void   DispensaCliente( dadosDaSimulacaoT *sim);
void   Randomize( void);
int    RandomInteger( int low, int high);
double RandomReal( double low, double high);
bool   RandomChance( double p);

bool traceFlag; 
// se TRUE, programa imprime histórico da simulação

int main( int argc, char *argv[]) {
   dadosDaSimulacaoT dados;

   if (argc >= 2 && strcmp( argv[1], "-t") == 0) traceFlag = TRUE; 
   else traceFlag = FALSE;

   Randomize();
   ExecutaSimulacao( &dados);

   printf( "\n");
   printf( "Resultados da simulação, dados os seguintes parâmetros:\n");
   printf( "   DuracaoDaSimulacao:     %4d\n",      
          (int) DuracaoDaSimulacao);
   printf( "   ProbabilidadeDeEntrada: %7.2f\n", 
          (double) ProbabilidadeDeEntrada);
   printf( "   TempoMinAtendimento:    %4d\n",      
          (int) TempoMinAtendimento);
   printf( "   TempoMaxAtendimento:    %4d\n",
          (int) TempoMaxAtendimento);
   printf( "\n");
   printf( "Clientes atendidos:        %4d\n", 
          dados.numeroDeAtendidos);
   printf( "Tempo médio de espera:     %7.2f\n", 
          (double) dados.somaTemposDeEspera / dados.numeroDeAtendidos);
   printf( "Comprimento médio da fila: %7.2f\n", 
          (double) dados.somaComprimentos / DuracaoDaSimulacao);
   return 0;
}

// Esta função recebe o endereço sim do struct que contém os 
// dados da simulação e faz a simulação.

void ExecutaSimulacao( dadosDaSimulacaoT *sim) {
   sim->fila = NewQueue();
   sim->clienteAtivo = NULL;
   sim->numeroDeClientes = 0; // Roberts esqueceu?
   sim->numeroDeAtendidos = 0;
   sim->somaTemposDeEspera = 0;
   sim->somaComprimentos = 0;
   for (sim->tempo = 0; sim->tempo < DuracaoDaSimulacao; sim->tempo++) {
      if (RandomChance( ProbabilidadeDeEntrada)) 
         ColocaClienteNaFila( sim);
      ProcessaFila( sim);
   }
   FreeQueue( sim->fila);
}

// Esta função simula a chegada de um novo cliente.

void ColocaClienteNaFila( dadosDaSimulacaoT *sim) {
   clienteT *c;
   sim->numeroDeClientes++;
   c = malloc( sizeof (clienteT));
   c->numeroCliente = sim->numeroDeClientes;
   c->instanteEntrada = sim->tempo;
   c->tempoDeAtendimento = 
      RandomInteger( TempoMinAtendimento, TempoMaxAtendimento);
   Enqueue( sim->fila, c);
   if (traceFlag) 
      printf( "%4d: Cliente %d entra na fila\n",
             sim->tempo, sim->numeroDeClientes);
}

// Esta função processa os eventos em uma unidade de tempo
// da simulação da fila.

void ProcessaFila( dadosDaSimulacaoT *sim) {
   if (sim->clienteAtivo == NULL) {
      if (!QueueIsEmpty( sim->fila)) 
         AtendeCliente( sim);
   } else {
      if (sim->clienteAtivo->tempoDeAtendimento == 0) 
         DispensaCliente( sim);
      else
         sim->clienteAtivo->tempoDeAtendimento--;
   }
   sim->somaComprimentos += QueueLength( sim->fila);
}

// Esta função é invocada quando o caixa está livre e há um 
// cliente esperando para ser atendido. O caixa tira o primeiro 
// cliente da fila e começa a atendê-lo.

void AtendeCliente( dadosDaSimulacaoT *sim) {
   clienteT *cli;
   cli = Dequeue( sim->fila);
   sim->clienteAtivo = cli;
   sim->numeroDeAtendidos++;
   sim->somaTemposDeEspera += (sim->tempo - cli->instanteEntrada);
   if (traceFlag) 
      printf( "%4d: Cliente %d chega ao caixa\n",
             sim->tempo, cli->numeroCliente);
}

// Esta função é invocada quando a contagem regressiva do 
// atendimento do cliente ativo atinge zero. O cliente vai embora
// e o caixa fica livre.

void DispensaCliente( dadosDaSimulacaoT *sim) {
   if (traceFlag) 
      printf( "%4d: Cliente %d deixa o caixa\n",
             sim->tempo, sim->clienteAtivo->numeroCliente);
   free( sim->clienteAtivo);
   sim->clienteAtivo = NULL;
}



/////////////////////////////////////////////////
// Seção 5: Gerador de números (pseudo)aleatórios
/////////////////////////////////////////////////

// A função Randomize inicializa o gerador de números aletórios
// de modo que os resultados das chamadas a RandomInteger e 
// RandomReal sejam imprevisíveis. Se essa função não for chamada,
// as outras funções produzirão sempre a mesma seqüência de 
// valores.

void Randomize( void) {
    srand( (int) time( NULL));
}

// A função RandomReal devolve um inteiro aleatório no intervalo 
// fechado [low..high].

double RandomReal( double low, double high) {
    double d;
    d = (double) rand() / ((double) RAND_MAX + 1);
    return low + d * (high - low);
}

// A função RandomInteger devolve um número real aleatório no 
// intervalo semi-aberto [low..high).

int RandomInteger( int low, int high) {
    int k;
    double d;
    d = (double) rand() / ((double) RAND_MAX + 1);
    k = d * (high - low + 1);
    return low + k;
}

// A função RandomChance recebe um número real p no intervalo
// fechado [0..1] e devolve TRUE com probabilidade p e FALSE com 
// probabilidade 1 - p.

bool RandomChance( double p) {
    return RandomReal( 0, 1) < p;
}

Resultados de um teste: 
   5: Cliente 1 entra na fila
   5: Cliente 1 chega ao caixa
  16: Cliente 1 deixa o caixa
  17: Cliente 2 entra na fila
  17: Cliente 2 chega ao caixa
  18: Cliente 3 entra na fila
  19: Cliente 4 entra na fila
  20: Cliente 5 entra na fila
  21: Cliente 6 entra na fila
  32: Cliente 2 deixa o caixa
   .
   .
   .
 180: Cliente 13 deixa o caixa
 181: Cliente 14 chega ao caixa
 185: Cliente 34 entra na fila
 191: Cliente 14 deixa o caixa
 192: Cliente 15 chega ao caixa
 193: Cliente 35 entra na fila
                                                              
Resultados da simulação, dados os seguintes parâmetros:           
   DuracaoDaSimulacao:      200
   ProbabilidadeDeEntrada:    0.20
   TempoMinAtendimento:       5
   TempoMaxAtendimento:      20

Clientes atendidos:          15
Tempo médio de espera:       50.60
Comprimento médio da fila:    9.53

 

Exercícios

  1. [Roberts exr.6, p.452]  Escreva uma nova versão do programa de simulação de fila de supermercado em que há dois ou mais caixas. Cada novo cliente entra na fila mais curta.

  2. [Roberts exr.7, p.452]  Escreva uma nova versão do programa de simulação de fila de supermercado em que há uma só fila de clientes mas diversos caixas.

 

Veja minhas anotações sobre filas.
URL of this site: www.ime.usp.br/~pf/mac0122-2002/
Last modified: Mon Oct 9 07:14:52 BRT 2017
Paulo Feofiloff
IME-USP