Centro de Ciências Exatas
Departamento de Computação
Curso: Bacharelado em Ciência da Computação
Disciplina: 5COP069 - Estrutura de Dados A
Professor: Roberto Vedoato
Lista de Exercícios 02 – Filas
Instruções
• Os exercícios devem ser resolvidos individualmente ou em dupla;
• Documente e idente o código;
• Compacte todos arquivos (projeto, fontes e cabeçalhos, exceto o executável), num arquivo
denominado com nome da dupla (ex: Joao_Maria.rar) e o envie por e-mail com o
assunto: UEL - EDA - Lista 02 para [email protected];
• Ao enviar o e-mail certifique-se de ativar a confirmação de recebimento e o registro de itens
enviados;
• Prazo de entrega: 14/04/2008;
• Não serão aceitos exercícios entregues fora destas especificações.
Exercícios
Considerando que os TDAs de Fila devem prover as operações válidas abaixo, resolva os próximos
exercícios:
Fila(); ou Fila (int tamanho=10);
criar uma fila vazia (no caso de alocação estática deve ser informado o tamanho da fila, caso não
informado, o padrão é 10 elementos do tipo de informação)
~Fila();
destruir a fila
void reinicia();
reiniciar a fila
void enfila(const TipoInfo &elemento);
inserir um nó no topo da fila
bool desenfila(TipoInfo &valor);
excluir o nó do topo de fila
bool buscaInicio(TipoInfo &valor);
consultar nó do início da fila
bool alteraInicio(const TipoInfo &valor);
alterar nó do início da fila
bool testaVazia();
testar se a fila está vazia
bool testaCheia();
testar se a fila está cheia (apenas para alocação estática)
1. Implemente o TDA Fila Estática Simples.
2. Implemente o TDA Fila Estática com Movimentação de Dados na Remoção.
3. Implemente o TDA Fila Estática com Movimentação de Dados na Inserção.
4. Implemente o TDA Fila Estática Circular.
5. Implemente o TDA Fila Dinâmica Simplesmente Encadeada.
6. Implemente o TDA Fila Dinâmica Duplamente Encadeada.
7. Implemente o TDA Fila Dinâmica Circular Duplamente Encadeada.
8. Implemente para um TDA Fila Dinâmica Simplesmente Encadeada uma operação cuja função seja
a concatenação da fila com outra recebida como argumento.
9. Implemente uma aplicação para a fila de um banco. Ao final da simulação devem ser mostrados o
total de clientes atendidos no expediente e fora dele, o tempo médio na fila dos clientes
atendidos no expediente e fora dele, o total de hora extra, o total geral de clientes atendidos e o
tempo médio geral na fila e também qual a maior e menor espera na fila.
Centro de Ciências Exatas
Departamento de Computação
Curso: Bacharelado em Ciência da Computação
Disciplina: 5COP069 - Estrutura de Dados A
Professor: Roberto Vedoato
Para tanto, considere as observações e o algoritmo a seguir.
•
•
•
•
A quantidade de caixas para atendimento aos clientes é M;
A possibilidade de chegar uma pessoa na fila é 1/N;
A unidade total de tempo de funcionamento do banco é T;
O tempo máximo de um atendimento ao cliente é S.
Algoritmo:
#define LIVRE 0
#include <time.h>
...
int clienteChegou()
{
int x;
x = rand() % N;
return (x == 0);
}
...
int main()
{
int caixa[M];
int relogio=0, espera=0, nclientes=0, chegada, i;
...
// inicia semente para geração de números aleatórios
srand((unsigned) time(NULL));
// liberar todos caixas para atendimento
for (i=0; i < M; i++)
caixa[i] = LIVRE;
// Simulação
// expediente
while (relogio < T)
{
if (clienteChegou() )
{
filaBanco.enfila(relogio);
nclientes++;
}
for (i=0; i < M; i++)
{
if (caixa[i]==LIVRE && !filaBanco.testaVazia())
{
filaBanco.desenfila(chegada);
caixa[i] = clienteOperacao();
espera = espera + (relogio - chegada);
nClientesAtendidos++;
}
else
// o i-ésimo caixa executou uma unidade de tempo no atendimento
if (caixa[i] != LIVRE)
caixa[i]--;
}
relogio++;
}
// após o expediente, atender todos os clientes que ainda esperam na fila