Aulafila

Métodos Computacionais

Fila

Definição de Fila
Fila é uma estrutura de dados dinâmica onde: Inserção de elementos se dá no final e a remoção no início
O primeiro elemento que entra é o primeiro que sai (FIFO)
Ex de uso : fila de impressão

2

Funcionamento da Fila
1- insere(a)

3- insere(c)

fim

fim

a

a

início

início

2- insere(b)

b

4- retira( )

fim a início

b

c

fim a b

c

início

3

Interface do tipo Fila
Criar uma fila vazia
Inserir um elemento no fim Retirar o elemento do início Verificar se a fila está vazia Liberar a fila

Em C
/* fila.h */ typedef struct fila Fila;
Fila* fila_cria(); void fila_insere(Fila* f,float v); float fila_retira(Fila* f); int fila_vazia(Fila* f); void fila_libera(Fila* f);

4

Implementando Fila com Vetor
Estrutura que representa fila deve ser composta pelo número de elementos da fila
(n), um vetor que armazena os elementos (vet) e o índice da posição do vetor que armazena o primeiro elemento da fila (ini)

#define N 100 struct fila { int n; int ini; float vet[N];
};

5

Implementando Fila com Vetor
Fila após a inserção de quatro novos elementos
1.4

2.2

0

1

3.5
2

4.0
3

inicio

4

...

fim

Fila após a remoção de dois elementos
1.4

2.2

3.5

0

1

2 inicio ...

4.0
3

4 fim A parte ocupada do vetor pode chegar à última posição e ainda haver espaço antes do início da fila.
6

Implementando Fila com Vetor
Solução: usar uma estratégia circular (se o último elemento da fila ocupa a última posição do vetor, insere-se novos elementos a partir do início do vetor, caso haja espaço)
Utilização do operador módulo (%)
O índice para a posição livre após o último elemento da fila pode ser calculado como: fim = (ini+n)%N
N → tamanho do vetor
Fila após a inserção de dois novos elementos
1.0
0

3.5
1
fim

2 inicio 4.0

6.0

3

4
7

Implementando Fila com Vetor
Função de Criação typedef struct fila Fila;
Fila* fila_cria() {
Fila* f = (Fila*) malloc(sizeof(Fila)); f->n = 0; f->ini = 0; return f;
Inicializa número
}

de