1

Curso Superior de Tecnologia em TelemticaProgramao e Estruturas de Dados

Filas Fundamentos e Implementaes

Copyright2010Prof. Csar Rocha

cesarocha@ifpb.edu.br

2

Objetivos

Explorar os conceitos fundamentais acerca do uso de filasfilas utilizando a linguagem C Organizao e implementao, caractersticas,

vantagens, desvantagens, regras de utilizao, operaes bsicas e algoritmos de implementao

Neste mdulo, sero abordadas ainda as seguintes implementaes de filas: seqencial, encadeada seqencial, encadeada e circulare circular Este mdulo ser utilizado como referncia na

entrega dos futuros projetos Implementao das estruturas e algoritmos, criao

das bibliotecasbibliotecas e prticas de laboratrio

3

Motivao

Uma das estruturas de dados mais utilizadas em programao a filafila Um exemplo de utilizao em computao a

implementao de uma fila de impresso

Assim como na pilha, os acessos aos elementos em uma fila tambm seguem uma regra : Lembre-se da pilha, onde: LLast IIn FFirst OOut Porm, uma fila : FFirst IIn FFirst OOut

A idia fundamentalA idia fundamental S podemos inserir um novo n no final da fila S podemos retirar a partir do incio da fila

4

Estratgia

Pode-se fazer uma analogia com uma fila de clientes em um banco qualquer: o primeiro a entrar na fila, ser o primeiro a sair e ser

atendido (retiramos ele do incio ou frente da fila) o ltimo cliente deve entrar no final da fila e, portanto,

ser o ltimo a sair (ou ser atendido) na fila

Portanto: No podemos retirar qualquer cliente da fila! Apenas clientes que esto na frente da fila

No podemos inserir um cliente na fila de tal forma que ele no seja o ltimo no conjunto de clientes

5

Propriedades

Propriedades de uma fila: Existem nn elementos enfileirados; E1E1 o elemento no incio (ou frente) da fila; EnEn o ltimo elemento da fila;

A insero de um primeiro elemento E1E1 em uma fila vazia, torna-o o primeiro a sair da estrutura No se pode consultar qualquer elemento A insero sempre feita depois do elemento EnEn A retirada sempre feita no elemento E1E1

6

Neste estgio, estaremos trabalhando com trs tipos de filas: seqenciaisseqenciais, encadeadas encadeadas e circularescirculares Seqencial: neste TAD, os elementos da fila so

armazenados em endereos seqenciais. Materializada na forma de um vetorvetor (arranjo ou matriz).

Tipos de filas

v[ ]

preciso controlar o incio e o final da fila. Note os campos frente e fim.

Como poderamos adaptar uma lista seqencial uma fila?

preciso controlar preciso controlar o incio e o final da o incio e o final da fila. Note os campos fila. Note os campos frente e fim.frente e fim.

Como poderamos Como poderamos adaptar uma lista adaptar uma lista seqencial uma seqencial uma fila?fila?

?...???

?...??A

Fila Vazia

Insere A

?...?BAInsere B

?...CBAInsere C

Frente= 0 e Fim= -1

Frente= 0 e Fim= 0

Frente= 0 e Fim= 1

Frente= 0 e Fim= 2

?...CB?Retira Frente= 1 e Fim= 2

7

(Continuao.) Encadeada: neste TAD, os elementos da fila so

elementos encadeados por ponteirosponteiros

Circular: caso particular de filas. Iremos levantar e comentar a necessidade da implementao circular mais frente

Importante:Importante: so apenas diferentes maneiras de se implementar o TAD, porm todas as trs formas seguem a mesma filosofia FFirst IIn FFirst OOut

Tipos de filas

TFilaEnc f* 12 09

8

Filas seqenciais

Pense um pouco...Pense um pouco... O que voc acha que seria necessrio para

implementar uma biblioteca de um novo TAD que representasse uma fila seqencial? um vetor de elementos (tamanho pr-definido) duas variveis que controlem a frente e o fim da fila

/* filaseq.h */void criarFila(TFila *fila);int filaVazia(TFila *fila);int filaCheia(TFila *fila);int enfileirar(TFila *fila, int dado);int desenfileirar(TFila *fila, int *d);void imprimir(TFila *fila);

/* filaseq.h */void criarFila(TFila *fila);int filaVazia(TFila *fila);int filaCheia(TFila *fila);int enfileirar(TFila *fila, int dado);int desenfileirar(TFila *fila, int *d);void imprimir(TFila *fila);

/* estruturao */typedef struct fila {

int elementos[MAX];int frente;int fim;

}TFila;

/* estruturao */typedef struct fila {

int elementos[MAX];int frente;int fim;

}TFila;

9

Mas... h problemas!Mas... h problemas!

Voc deve ter percebido que a parte ocupada do vetor pode chegar ultima posio Ou seja, a fila seqencial vai se deslocando da

esquerda (frente) para direita (fim) em cada retirada

Existem dois elementos vazios na fila, mas nenhum outro elemento pode mais ser inserido! fila.fim chegou condio de limite (MAX -1)

??DC?Fila

Insere E e F

Retira C

Insere G

Frente= 1 e Fim= 2

Frente= 1 e Fim= 4

Frente= 2 e Fim= 4

Frente= 2 e Fim= 4

FEDC?

FED??

FED??

10

Mas... h problemas!Mas... h problemas!

E agora?E agora? Do jeito que est, pode-se chegar a uma situao

(absurda) em que a fila estar vazia, mas nenhum elemento novo poder mais ser inserido! Concluso: a representao seqencial, descrita

anteriormente, parece no ser muito boa!

Poderamos mudar a funo desenfileirar() E fazer o deslocamento esquerda de todos os

elementos a cada retirada na frente da fila, mas... ...e se a fila tivesse 100 elementos?

Havamos criticado o deslocamento da lista seqencial!

11

SoluoSoluo

O que se quer reaproveitar as primeiras posieslivres do vetor sem implementar um re-arranjo (trabalhoso) de todos os elementos a cada retirada Para isso, pode-se incrementar as posies do vetor de

maneira circular Ou seja, se o ltimo elemento da fila ocupar a ltima

posio do vetor, inserimos os novos elementos a partir do incio do vetor!

Graficamente:Graficamente:

Insere G Frente= 2 e Fim= 0FEDG

12

Filas encadeadas

O que fazer quando o nmero mximo de elementos na fila no conhecido? Devemos implementar a fila usando uma estrutura de

dados dinmica (com alocaoalocao dinmicadinmica) Podemos empregar os conceitos vistos nas listas

simplesmente (ou duplamente) encadeadas

Entretanto, as regras de insero/remoo, agora, iro mudar! Algumas funes da lista encadeada (inserir ou remover

mediante uma posio qualquer, entre outras) devero ser eliminadas neste novo TAD

13

Filas encadeadas - modus operandi

O primeiro elemento (incio) da lista encadeada poder representar a frente atual da fila Assim, cada novo elemento ser inserido no final da lista.

Conseqentemente e, sempre que solicitado, retiramos o elemento a partir do incio da lista

Desta forma, vamos precisar de apenas duas funes auxiliares na lista: uma para inserir no fim (enfileirar) outra para remover do incio (desenfileirar)

H apenas uma desvantagem: Para cada elemento a ser inserido na fila, teremos que

percorrer todos os nodos at encontrar o ltimo.

14

Fila encadeada com n descritor

Vamos utilizar os conhecimentos auferidos em tcnicas de encadeamento! Neste caso em particular, iremos alocar um n

cabea para que possamos ter acesso direto ao final da fila (promover performance)

100 110 120

TFilaEncCab f

03Vantagens

Acesso direto aoprimeiro nodo;

Acesso direto aoltimo nodo;

Informao sobre o tamanho da lista.

VantagensVantagens

AcessoAcesso diretodireto aoaoprimeiroprimeiro nodonodo;;

AcessoAcesso diretodireto aoaoltimoltimo nodonodo;;

InformaoInformao sobresobre o o tamanhotamanho dada listalista..

Cabea

15

Algoritmos em C

O que dever ser feito pelo aluno: Escolha e instalao do ambiente a ser trabalhado no

laboratrio Modelagem deste TAD (dados e operaes) Implementao dos algoritmos de operaes bsicas

vistos em sala de aula na linguagem C Utilizao das regras de modelagem vistas no mdulo

anterior (criao de bibliotecas) e modularizao Implantao de cdigo legvel e bem documentado Nomes de variveis condizentes com o problema Prtica de laboratrio

16

Para um bom aproveitamento:Para um bom aproveitamento:

O aluno deve identificar a relao entre TAD (biblioteca e modularizao) com a implementao da fila no cdigo! Resolva todas as questes da prprtica de tica de

laboratlaboratrio de filas circular e encadeadario de filas circular e encadeada Procure o professor ou monitor da disciplina e

questione conceitos, listas, etc. No deixe para codificar tudo e acumular assunto

para a primeira avaliao. Este apenas um dos assuntos abordados na prova!

ObjetivosMotivaoEstratgiaPropriedadesTipos de filasTipos de filasFilas seqenciaisFilas encadeadasFilas encadeadas - modus operandiFila encadeada com n descritorAlgoritmos em C