Estrutura de Dados - Aula 07

Prévia do material em texto

ESTRUTURA DE DADOS
Aula 7 – FILA
ESTRUTURA DE DADOS
FILA – Aula7
Atenção aos Temas Principais dessa Aula
ESTRUTURA DE DADOS
FILA – Aula7
Conteúdo Programático desta aula





ESTRUTURA DE DADOS
FILA – Aula7
Direto ao Assunto
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
“Uma fila é um tipo especial de Lista Linear em que as
inserções são realizadas num extremo, ficando as
remoções restritas ao outro. O extremo onde os
elementos são inseridos é denominado final da fila, e
aquele de onde são removidos é denominado começo da
fila.”(PEREIRA, Silvio. L., 2004, p. 57)
Conceito de Fila
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
Considerações sobre a FILA
ESTRUTURA DE DADOS
FILA – Aula7
A inserção de um elemento acontece em uma extremidade
e a remoção , em outra.
Considerações sobre a FILA
ESTRUTURA DE DADOS
FILA – Aula7
Insere na Fila
ESTRUTURA DE DADOS
FILA – Aula7
Insere na Fila
ESTRUTURA DE DADOS
FILA – Aula7
Remove da Fila
ESTRUTURA DE DADOS
FILA – Aula7
Remove da Fila
ESTRUTURA DE DADOS
FILA – Aula7
Não existe movimentação na fila quando inserimos, ou
removemos um elemento dela.
Inserção de um elemento acontece em uma extremidade e
a remoção , em outra.
Considerações sobre a FILA
ESTRUTURA DE DADOS
FILA – Aula7
Podemos usar matrizes homogêneas ou heterogêneas,
alocação sequencial, e duas variáveis sendo que uma serve
para controlar o início e a outra, o fim da fila.
Não existe movimentação na fila quando inserimos, ou
removemos um elemento dela.
Inserção de um elemento acontece em uma extremidade e
a remoção , em outra.
Considerações sobre a FILA
ESTRUTURA DE DADOS
FILA – Aula7
Um dos fatores que limita o crescimento da fila é a
quantidade de memória alocada quando usamos matrizes.
Considerações sobre a FILA
ESTRUTURA DE DADOS
FILA – Aula7
Quando formos enfileirar um elemento, é preciso verificar
se a fila não está cheia. Isso evita overflow. Além disso,
incrementar a variável que controla o fim da fila.
Um dos fatores que limita o crescimento da fila é a
quantidade de memória alocada quando usamos matrizes.
Considerações sobre a FILA
ESTRUTURA DE DADOS
FILA – Aula7
Quando formos desenfileirar um elemento, é preciso
verificar se a fila não está vazia. Isso evita underflow.
Além disso, incrementar a variável que controla o início da
fila.
Quando formos enfileirar um elemento, é preciso verificar
se a fila não está cheia. Isso evita overflow. Além disso,
incrementar a variável que controla o fim da fila.
Um dos fatores que limita o crescimento da fila é a
quantidade de memória alocada quando usamos matrizes.
Considerações sobre a FILA
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
ATENDIMENTO DE PROCESSOS REQUISITADOS
A UM SISTEMA OPERACIONAL
FILA DE ARQUIVOS PARA IMPRESSÃO
Buffer para gravação de dados em mídia
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
1) Inicializa() ou Init()
2) Enfileira() ou Enqueue()
3) Desenfileira() ou Dequeue()
4) elemPrimeiro () ou firstElem()
5) verificaFilaCheia() ou isFull()
6) verificaFilaVazia() ou isEmpty()
ESTRUTURA DE DADOS
FILA – Aula7
0 PROBLEMA
Em uma pequena cidade do interior de Pernambuco,
cada médico tem que atender a 20 pacientes por dia.
A Dra Angela pediu que fosse desenvolvido um programa
que armazenasse, por ordem de chegada, o nome do
paciente e sua identificação dentro do posto.
Para facilitar o manuseio desse programa, usei o
tamanho da constante como 5.
Além disso, não se exibe todos os elementos de uma fila
logo, só para entendimento que foi criada a função.
ESTRUTURA DE DADOS
FILA – Aula7
A struct
ESTRUTURA DE DADOS
FILA – Aula7
Inicialização
ESTRUTURA DE DADOS
FILA – Aula7
Protótipos
Inicialização
ESTRUTURA DE DADOS
FILA – Aula7
#include <iostream>
#include <cstdlib>
#include <cstring>
#define TAM 5
using namespace std;
struct atende
{
char paciente[TAM][35], identificacao[TAM][20];
int inicio,fim;
};
void agenda(atende &fil);
void consulta(atende &fil);
void elemPrimeiro(atende &fil);
void lista(atende &fil);
Código
1
ESTRUTURA DE DADOS
FILA – Aula7
int main()
{
char resp[10]; int op;
atende fila; fila.inicio = 0; fila.fim = -1;
do
{ system("cls");
cout<<"\nFILA( FIFO - First In - First Out )\n\n";
cout<<"\n1- Inserir paciente";
cout<<"\n2- Atender paciente";
cout<<"\n3- Exibe nome do primeiro paciente a ser
atendido";
cout<<"\n4- listar - QUESTAO DIDATICA. Remova depois que
testar";
cout<<"\n5- Sai";
cout<<"\nOpcao: ";
cin>>resp;op=atoi(resp);
system("cls");
Código
2
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
switch(op)
{ case 1: agenda(fila); break;
case 2: consulta(fila); break;
case 3: elemPrimeiro(fila); break;
case 4: lista(fila); break;
case 5: cout<<"\nPrograma com FILA. n"; break;
default: cout<<"\nOPCAO INVALIDA\n";
}
cout<<"\n\n";system("pause");
}while(op!=5);
}
Código
3
ESTRUTURA DE DADOS
FILA – Aula7
void agenda(atende &fil)
{
char n[35], id[20];
if (fil.fim == TAM - 1) // testando se a fila cheia está cheia
cout<<"\nATENCAO. Fila Cheia\n";
else
{ cin.get();cout<<"\nEntre com nome: ";
cin.getline(n,35);
strupr(n);//Faça um trecho com for e toupper
cout<<"\nEntre com a identificacao: ";
cin.getline(id,20);
strupr(id);
fil.fim++; //atualiza o final da fila
strcpy(fil.paciente[fil.fim],n);
strcpy(fil.identificacao[fil.fim],id);
}
}
Código
4
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
Insere na fila até que aparece a mensagem
ESTRUTURA DE DADOS
FILA – Aula7
void consulta(atende &fil)
{
if (fil.inicio > fil.fim) // testando se a fila está vazia
cout<<"\nATENCAO. Fila Vazia\n";
else
{
cout<<"\nPaciente Atendido: "<<fil.paciente[fil.inicio];
cout<<"\nIdentificacao: "<<fil.identificacao[fil.inicio];
fil.inicio++; //atualiza o início da fila
}
}
Código
5
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
void elemPrimeiro(atende &fil)
{
if(fil.inicio > fil.fim)
cout<<"\nATENCAO. Fila Vazia\n";
else
{
cout<<"\nProximo paciente a ser atendido: “:
cout<<fil.paciente[fil.inicio];//*
}
}
//* MELHORAR O ENTENDIMENTO.
Código
6
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
void lista(atende &fil)
{
int ordem=1;
if(fil.inicio > fil.fim)
cout<<"\nATENCAO. Fila Vazia\n";
else
{
cout<<"\nOrdem de Atendimento\n";
for(int x=fil.inicio; x<=fil.fim; x++)
{
cout<<"\n\n"<<ordem++<<"o paciente";
cout<<"\nNome do Paciente: "<<fil.paciente[x];
cout<<"\nIdentificacao: "<<fil.identificacao[x];
}
}
}
Código
7
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
Um problema a resolver
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
Insere
Total = 3
Total = 4
Total = 5
ESTRUTURA DE DADOS
FILA – Aula7
Remove
Total = 4 Total = 3
ESTRUTURA DE DADOS
FILA – Aula7
Resolve
Total =4
ESTRUTURA DE DADOS
FILA – Aula7
Problema resolvido com o acréscimo de uma variável
que sinaliza o total de elementos presentes na fila,
retornando a 0 quando se iguala ao tamanho da fila.
ESTRUTURA DE DADOS
FILA – Aula7
ESTRUTURA DE DADOS
FILA – Aula7
A struct
ESTRUTURA DE DADOS
FILA – Aula7Inicialização
ESTRUTURA DE DADOS
FILA – Aula7
Inicialização
Protótipos
ESTRUTURA DE DADOS
FILA – Aula7
#include <iostream>
#include <cstring>
#include <cctype>
#define MAX 5
using namespace std;
struct queue
{
float circular[MAX];
int total, inicio, final;
};
void entra(queue &fil);
void deleta(queue &fil);
void elementoPrimeiro(queue &fil) ;
Código
1
ESTRUTURA DE DADOS
FILA – Aula7
int main()
{ int x; char s; queue fila;
fila.inicio = 0; fila.total = 0; fila.final=0;
for(;;)
{ system("cls");
system("color f1");
cout<<"\n *************";
cout<<"\n * I - Inserir *";
cout<<"\n * L - Listar *";
cout<<"\n * R - Remover *";
cout<<"\n * S - Sair *";
cout<<"\n *************\n";
cin>>s;cin.get();
s= toupper(s);
system("cls");
Código
2
ESTRUTURA DE DADOS
FILA – Aula7
switch(s)
{
case 'I': entra(fila); break;
case 'L': elementoPrimeiro(fila); break;
case 'R': deleta(fila); break;
case 'S': system("pause"); exit(0);
}
cout<<"\n\n";system("pause");
}
}
Código
3
ESTRUTURA DE DADOS
FILA – Aula7
void entra(queue &fil)
{ float valor;
if(fil.total==MAX)
cout<<"\nAtencao. Fila Cheia\n";
else
{
cout<<"\nDigite valor: "; cin>>valor;
fil.circular[fil.final]=valor;
fil.final++;
if(fil.final==MAX) fil.final=0;
fil.total++;
}
}
Código
4
ESTRUTURA DE DADOS
FILA – Aula7
void deleta(queue &fil)
{
if(fil.total==0)
cout<<"\nAtencao. Fila Vazia\n";
else
{
cout<<"\nRemovido: "<<fil.circular[fil.inicio];
fil.inicio++;
// fil.circular[fil.inicio-1]=-999;
if(fil.inicio==MAX)fil.inicio=0;
fil.total--;
}
}
Código
5
ESTRUTURA DE DADOS
FILA – Aula7
void elementoPrimeiro(queue &fil) //lista
{ if(fil.total==0)
cout<<"\nAtencao. Fila Vazia\n";
else
{ /*cout<<"\nProximo a ser removido na posicao: "<< fil.inicio;
cout<<"\nValor\tPosicao\n";
if(fil.inicio<fil.final)
{ for(int x=fil.inicio; x<fil.final; x++) cout<<"\n"<<fil.circular[x]<<"\t"<<x; }
else
{ for(int x=0; x<MAX; x++)
if(fil.circular[x]!= -999) cout<<"\n"<<fil.circular[x]<<"\t"<<x;
}*/
cout<<"\nProximo a ser removido na posicao: “;
cout<< fil.inicio<<"\n"<<fil.circular[fil.inicio];
}
}
Código
6
ESTRUTURA DE DADOS
FILA – Aula7
A análise a seguir está baseada nas funções da aula on-line 
onde trechos estão presentes dentro de comentários.
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que insere
Após inserir mais quatro números, teremos a seguinte
saída, obtida pela função que deve ser deletada.
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que exibe
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que remove
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que exibe
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que insere
Após inserir esse valor, teremos a seguinte saída.
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que exibe
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que insere
Após inserir esse valor, teremos a seguinte saída.
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que exibe
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que remove
Após essa remoção, a fila ficará assim.
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que exibe
Início: 3 Fim: 2 Total: 4
ESTRUTURA DE DADOS
FILA – Aula7
Análise do programa com as funções básicas para a fila circular
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que insere
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que exibe o primeiro da fila
ESTRUTURA DE DADOS
FILA – Aula7
Trecho que remove
ESTRUTURA DE DADOS
FILA – Aula7
Resumindo