Estruturas de Dados
Profa. Juliana Pinheiro Campos
ESTRUTURAS DE DADOS

Filas

Estrutura de dados muito utilizada em
computação.

Uma fila (assim como a pilha) pode ser
considerada uma restrição de lista. São casos
particulares de listas.

Possuem regras definidas quanto as operações
de acesso.
ESTRUTURAS DE DADOS

Filas

As filas são baseadas no princípio FIFO (First in,
First out):
O primeiro a entrar na fila, é o primeiro a sair.

Analogia natural com o conceito de fila que
usamos no dia-a-dia.

Ex: Fila de caixa de banco, de atendimento
ambulatorial, filas de modo em geral.
ESTRUTURAS DE DADOS

Filas

Regra das operações.



Inserções: sempre no final;
Exclusões: sempre no início;
Pesquisa: à partir do início;
Início
FIFO
Fim
ESTRUTURAS DE DADOS

Filas

Exemplos práticos de Fila para informática:




Compartilhamento de periféricos;
Gerência de redes;
Algoritmos de processamento de imagens;
Observação quanto à prioridades: todos os
elementos de uma fila são tratados com a mesma
prioridade.
ESTRUTURAS DE DADOS

Filas

Exemplo: Estrutura fila que armazena valores
reais.

Vamos ver duas estratégias de implementação:


Implementação utilizando vetor;
Implementação utilizando uma lista encadeada;
ESTRUTURAS DE DADOS

Interface do tipo fila
Fila* criarFila(void);
Cria uma fila vazia
void inserir(Fila* f, float v);
Insere um elemento no fim
float remover(Fila* f);
Remove elemento do início
int estaVazia(Fila* f);
Verifica se a fila está vazia
void liberarFila(Fila* f);
Libera a fila
ESTRUTURAS DE DADOS

Implementação de fila usando vetor:
Estrutura de fila
1.4
Início


2.2
3.5
4.0
...
Fim
inicio marca a posição do próximo elemento a ser
retirado da fila;
fim marca a posição (vazia) em que será inserido o
próximo elemento.
ESTRUTURAS DE DADOS

Implementação de fila usando vetor:
Estrutura de fila
struct fila{
float info[N];
int n;
int inicio;
// vetor para armazenar os valores reais
// número de elementos existentes na
fila
// representa a posição do primeiro
elemento da fila
};
Tendo o início é possível calcular o fim a partir do número de
elementos armazenados na fila.
ESTRUTURAS DE DADOS

Implementação de fila usando vetor
Observe que o processo de inserção e remoção em
extremidades opostas fará a fila “andar” no vetor.
Ex: Inserção de 1.4, 2.2, 3.5 e 4.0 na fila
1.4
Início
2.2
3.5
4.0
...
Fim
ESTRUTURAS DE DADOS

Implementação de fila usando vetor
1.4
2.2
3.5
4.0
Início
...
Fim
Após remoção de 2 elementos:
3.5
Início
4.0
...
Fim
ESTRUTURAS DE DADOS

Implementação de fila usando vetor


A parte ocupada do vetor pode chegar à última
posição.
Para reaproveitar as primeiras posições do vetor
podemos re-arrumar os elementos ou
incrementar as posições de forma circular.
ESTRUTURAS DE DADOS

Implementação de fila usando vetor

A outra opção é incrementar as posições de
forma circular.
0
21.2
1
49
24.3
...
Fim
Inserimos novos
Elementos a partir do início do vetor
20.0
Início
20.8
ESTRUTURAS DE DADOS

Implementação de fila usando vetor

Podemos definir uma função auxiliar para
incrementar o valor do índice atual e fornecer o
índice incrementado de forma circular:
int incr(int i){
if(i == N - 1)
return 0;
else
return i + 1;
}
OU
int incr(int i) {
return (i+1) % N;
}
Usando o operador módulo (%),
podemos dispensar a função auxiliar
e escrever:
i = (i+1) % N;
ESTRUTURAS DE DADOS

Implementação de fila usando vetor

Exemplo de fila usando vetor – Versão 2: com
incremento circular dos índices.
ESTRUTURAS DE DADOS

Implementação de fila com lista

Para inserir e remover elementos de
extremidades opostas (insere no fim e remove no
início), teremos de usar dois ponteiros:


ini: aponta para o primeiro elemento da lista;
fim: aponta para o último elemento da lista;
ini
Info 1
Info 2
fim
Info 3
ESTRUTURAS DE DADOS

Implementação de fila com lista
typedef struct lista {
float info;
struct lista* prox;
}Lista;
typedef struct fila {
Lista* ini;
Lista* fim;
}Fila;
// Estrutura da lista
// Estrutura da fila
ESTRUTURAS DE DADOS

Implementação de fila com lista

Faça as funções que criam uma fila vazia e que
verifica se a fila está vazia.

Função para inserir um elemento: acrescenta à
lista um sucessor para o último nó. Faz com que
o último nó aponte para o novo.

Atenção: Deve atualizar os ponteiros ini e fim
quando insere o primeiro elemento.
ESTRUTURAS DE DADOS

Implementação de fila com lista
void inserir(Fila* f, float v) {
Lista* n = malloc(sizeof(Lista));
n->info = v;
n->prox = NULL;
if(f->fim != NULL) //verifica se a lista não estava vazia
f->fim->prox = n;
else
f->ini = n;
f->fim = n;
// fila aponta para o novo elemento
}
ESTRUTURAS DE DADOS

Implementação de fila com lista

Faça uma função para imprimir os elementos da
fila.

Função para retirar um elemento: após a
remoção, ini aponta para o sucessor do nó
retirado.

Atenção: Deve atualizar os ponteiros ini e fim
quando a fila se tornar vazia.
ESTRUTURAS DE DADOS

Implementação de fila com lista
float remover(Fila* f) {
Lista* t;
float valor;
if(estaVazia(f)){
printf("Fila vazia!");
exit(1);
}
t = f->ini;
valor = t->info;
f->ini = t->prox;
if(f->ini == NULL)
//Verifica se a lista ficou vazia
f->fim = NULL;
free(t);
return valor;
}
ESTRUTURAS DE DADOS

Implementação de fila com lista
Faça uma função para liberar a fila.
Exercício: Implemente as seguintes funções:
a) Faça uma função para retornar o primeiro elemento
da fila.
b) Implemente uma função furaFila. Ela deve receber a
fila e um valor real que deve ser procurado e, se
encontrado na fila, deve ser inserido na primeira
posição. Observe que neste caso, estaremos
desrespeitando a regra de acesso a FILA.