Aula Fila Sequencial.pdf

Prévia do material em texto

Fila - Alocac¸a˜o Sequencial
Professor:
Silvio Luiz Bragatto Boss
e-mail:
silvioboss@utfpr.edu.br
Universidade Tecnolo´gica Federal do Parana´ - UTFPR
Coordenac¸a˜o de Informa´tica - COINF
Curso de Engenharia de Computac¸a˜o
Disciplina de Estrutura de Dados I
Fila
Suma´rio
1 Fila
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Alocac¸a˜o Sequencial
Fila e´ uma estrutura de dados cujo funcionamento e´
inspirado em uma fila de banco;
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Alocac¸a˜o Sequencial
Fila e´ uma estrutura de dados cujo funcionamento e´
inspirado em uma fila de banco;
Cada vez que uma operac¸a˜o de inserc¸a˜o e´ executada, um
novo elemento e´ colocado no final da fila;
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Alocac¸a˜o Sequencial
Fila e´ uma estrutura de dados cujo funcionamento e´
inspirado em uma fila de banco;
Cada vez que uma operac¸a˜o de inserc¸a˜o e´ executada, um
novo elemento e´ colocado no final da fila;
Na remoc¸a˜o de um item, e´ retornado o elemento que aguarda
ha´ mais tempo na fila, ou seja, aquele posicionado no in´ıcio.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Alocac¸a˜o Sequencial
Fila e´ uma estrutura de dados cujo funcionamento e´
inspirado em uma fila de banco;
Cada vez que uma operac¸a˜o de inserc¸a˜o e´ executada, um
novo elemento e´ colocado no final da fila;
Na remoc¸a˜o de um item, e´ retornado o elemento que aguarda
ha´ mais tempo na fila, ou seja, aquele posicionado no in´ıcio.
A ordem de sa´ıda corresponde a` ordem de chegada:
Itens inseridos no fim da fila.
Itens removidos do in´ıcio da fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Inserc¸a˜o e Exclusa˜o de Elementos em uma Fila
Fila e´ chamada de lista FIFO (first-in, first-out).
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Inserc¸a˜o e Exclusa˜o de Elementos em uma Fila
Fila e´ chamada de lista FIFO (first-in, first-out).
O primeiro a entrar e´ o primeiro a sair.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Inserc¸a˜o e Exclusa˜o de Elementos em uma Fila
Fila e´ chamada de lista FIFO (first-in, first-out).
O primeiro a entrar e´ o primeiro a sair.
Neste tipo de implementac¸a˜o utiliza-se um vetor para guardar
os itens da fila e duas varia´veis para armazenar as posic¸o˜es de
in´ıcio e final (´ındices);
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Inserc¸a˜o e Exclusa˜o de Elementos em uma Fila
Fila e´ chamada de lista FIFO (first-in, first-out).
O primeiro a entrar e´ o primeiro a sair.
Neste tipo de implementac¸a˜o utiliza-se um vetor para guardar
os itens da fila e duas varia´veis para armazenar as posic¸o˜es de
in´ıcio e final (´ındices);
Uma fila pode ser representada por uma estrutura:
Um vetor para guardar os itens da fila;
Um ı´ndice para o in´ıcio da fila;
Um ı´ndice para o final da fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Inserc¸a˜o e Exclusa˜o de Elementos em uma Fila
Os ı´ndices que apontam para o in´ıcio e o final da fila devem
ser inicializados com o valor 0;
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Inserc¸a˜o e Exclusa˜o de Elementos em uma Fila
Os ı´ndices que apontam para o in´ıcio e o final da fila devem
ser inicializados com o valor 0;
Assim, o final da fila aponta para a posic¸a˜o do vetor onde sera´
inserido o pro´ximo item da fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Inserc¸a˜o e Exclusa˜o de Elementos em uma Fila
Os ı´ndices que apontam para o in´ıcio e o final da fila devem
ser inicializados com o valor 0;
Assim, o final da fila aponta para a posic¸a˜o do vetor onde sera´
inserido o pro´ximo item da fila.
A fila estara´ vazia quando os ı´ndices de in´ıcio e final forem
iguais, e
Estara´ cheia quando o final for igual ao nu´mero de elementos
do vetor.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Funcionamento de uma Fila
(a) Fila vazia
(b) Insere 3 itens na fila: A, B, C.
(c) Retira 2 itens da fila. (retira itens do in´ıcio: A, B)
(d) Insere 2 itens na fila: D, E.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Alocac¸a˜o Sequencial
Problema
Tem-se apenas 3 itens na fila, entretanto, na˜o e´ poss´ıvel mais
inserir nenhum item, apesar da fila ter capacidade de
armazenar 5 itens.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Alocac¸a˜o Sequencial
Problema
Tem-se apenas 3 itens na fila, entretanto, na˜o e´ poss´ıvel mais
inserir nenhum item, apesar da fila ter capacidade de
armazenar 5 itens.
Soluc¸a˜o
Imaginar o vetor que armazena a fila como um c´ırculo (Fila
Circular), representando uma a´rea sequencial de memo´ria, de
forma que a primeira posic¸a˜o do vetor estivesse localizada
logo apo´s a u´ltima posic¸a˜o do vetor;
Para implementar a fila circular, sempre que for preciso
incrementar um ı´ndice (in´ıcio ou fim) e seu valor for igual a
MAX-1, restabelecemos seu valor a 0.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Funcionamento de uma Fila Circular
(a) Fila com dois elementos.
(b) Insere 1 item na fila: E.
(c) Retira 2 itens da fila. (retira itens do in´ıcio da FILA: C, D)
(d) Retira 1 item da fila. (retira o item do in´ıcio da FILA: E)
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Fila Circular - Prof. Fa´bio de la Rocha
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Fila Circular - Prof. Fa´bio de la Rocha
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Fila Circular - Prof. Fa´bio de la Rocha
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Fila Circular - Prof. Fa´bio de la Rocha
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Fila Circular - Prof. Fa´bio de la Rocha
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Fila Circular - Prof. Fa´bio de la Rocha
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Fila Circular - Prof. Fa´bio de la Rocha
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Exemplo de Fila Circular - Prof. Fa´bio de la Rocha
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Alocac¸a˜o Sequencial
Problema
Os ı´ndices de in´ıcio e final da fila sa˜o inicializados como 0;
Como verificar quando a fila esta´ vazia?
Quando os valores dos ı´ndices in´ıcio e final sa˜o iguais.
Entretanto, quando a fila esta´ cheia os ı´ndices in´ıcio e final tambe´m sa˜o
iguais.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Alocac¸a˜o Sequencial
Problema
Os ı´ndices de in´ıcio e final da fila sa˜o inicializados como 0;
Como verificar quando a fila esta´ vazia?
Quando os valores dos ı´ndices in´ıcio e final sa˜o iguais.
Entretanto, quando a fila esta´ cheia os ı´ndices in´ıcio e final tambe´m sa˜o
iguais.
Soluc¸a˜o
Utilizar um contador para armazenar o nu´mero de itens armazenados na
fila;
Quando um elemento for inserido na fila o contador deve ser
incrementado;
Quando um elemento for removido o contador deve ser decrementado.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila como um TDA
TDA - Tipo Abstrato de Dado
Um TDA engloba a definic¸a˜o da tipo do dado e das operac¸o˜es
relacionadas com este tipo;
Um TDA para a estrutura fila envolve a declarac¸a˜o do tipo de
dado fila e das operac¸o˜es realizadas sobre a fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Aspecto Estrutural
Uma fila pode ser representada por uma estrutura que conte´m
Um vetor para armazenar as informac¸o˜es da fila;
Um indicador da posic¸a˜o atual do in´ıcio da fila;
Um indicadorda posic¸a˜o atual do final da fila;
Um contador que guarda o nu´mero de itens da fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Fila - Representac¸a˜o Sequencial
Exemplo de Implementac¸a˜o
#define MAX 100
typedef struct{
int item[MAX];
int ini;
int fim;
int cont;
}Fila;
.....
Fila f;
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Aspecto Funcional
Operac¸o˜es da Fila
Inicializar a fila;
Adicionar um item na fila;
Remover um item da fila;
Testar se a fila esta´ vazia;
Testar se a fila esta´ cheia.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo inicializaFila
Procedimentos Realizados
Atribui 0 ao indicador de in´ıcio da fila;
Atribui 0 ao indicador de fim da fila;
Atribui 0 ao contador da fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo inicializaFila
Procedimentos Realizados
Atribui 0 ao indicador de in´ıcio da fila;
Atribui 0 ao indicador de fim da fila;
Atribui 0 ao contador da fila.
Paraˆmetros
A fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo inicializaFila
Exemplo de Implementac¸a˜o
void iniFila(Fila *f) {
f->ini = 0;
f->fim = 0;
f->cont = 0;
}
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo vaziaFila
Procedimentos Realizados
Se contador da fila e´ igual a 0, ent~ao
retorna 1 (verdadeiro)
sen~ao
retorna 0 (falso).
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo vaziaFila
Procedimentos Realizados
Se contador da fila e´ igual a 0, ent~ao
retorna 1 (verdadeiro)
sen~ao
retorna 0 (falso).
Paraˆmetros
A fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo cheiaFila
Procedimentos Realizados
Se contador da fila e´ igual a MAX, ent~ao
retorna 1 (verdadeiro)
sen~ao
retorna 0 (falso)
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo cheiaFila
Procedimentos Realizados
Se contador da fila e´ igual a MAX, ent~ao
retorna 1 (verdadeiro)
sen~ao
retorna 0 (falso)
Paraˆmetros
A fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo insereFila
Procedimentos Realizados
Se fila esta´ cheia, ent~ao
retorna ERROFILACHEIA
sen~ao
Adiciona o novo dado no fim da fila.
Se fim da fila for diferente de MAX-1, ent~ao
incrementa fim da fila.
sen~ao
atribui 0 ao fim da fila
Incrementa o contador da fila.
Retorna fim da fila.
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo insereFila
Paraˆmetros
A fila.
O dado a ser inserido.
Constante Utilizada Pelo Algoritmo
#define ERROFILACHEIA -1
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo retiraFila
Procedimentos Realizados
Se fila esta´ vazia, ENT~AO
retorna ERROFILAVAZIA
sen~ao
Recupera o valor do elemento do inı´cio da fila
se inı´cio da fila for diferente de MAX-1, ent~ao
incrementa inı´cio da fila
sen~ao
atribui 0 ao ı´ndice de inı´cio da fila
Decrementa o contador da fila
Retorna o valor de item retirado
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX
Fila
Algoritmo retiraFila
Paraˆmetros
A fila.
Constante Utilizada Pelo Algoritmo
#define ERROFILAVAZIA -2
Silvio Luiz Bragatto Boss UTFPR
Fila LATEX