02 Filas C v8

Prévia do material em texto

1
ESTRUTURAS DE DADOS
► Filas
(Linguagem C)
Prof. Dr. Marcelo Duduchi
Aux. Docente Lucio Nunes
Listas Lineares
◼ Vimos anteriormente o conceito de listas lineares e 
mostramos que tanto as pilhas quanto as filas são listas 
lineares restritas;
◼ Vimos que as pilhas caracterizam-se pela dinâmica em 
que o último elemento que entra é o primeiro que sai;
◼ Conheceremos agora as filas.
2
Filas
◼ Uma lista linear onde a entrada é feita por uma 
extremidade e a saída é feita pela outra extremidade é 
conhecida como fila;
◼ Neste caso o primeiro elemento a entrar é o primeiro 
elemento a sair (First In / First Out);
◼ Existem duas funções que se aplicam a todas as filas: 
 STORE: insere um item no final da fila;
 RETRIEVE: remove um item do início da fila.
3
Filas (modelo conceitual)
4
store
A
NOVOS ELEMENTOS SÃO ARMAZENADOS NO
FINAL DA FILA
B
Filas (modelo conceitual)
5
store
A
NOVOS ELEMENTOS SÃO ARMAZENADOS NO
FINAL DA FILA
C
Filas (modelo conceitual)
6
store
A B
NOVOS ELEMENTOS SÃO ARMAZENADOS NO
FINAL DA FILA
1 2
3 4
5 6
2
D
Filas (modelo conceitual)
7
store
A B C
NOVOS ELEMENTOS SÃO ARMAZENADOS NO
FINAL DA FILA
Filas (modelo conceitual)
8
Sequência armazenada 
em fila.
A B C D
NOTE QUE EM NOSSO EXEMPLO O COMEÇO
FOI DEFINIDO NA PONTA ESQUERDA
Filas (modelo conceitual)
retrieve
OS ELEMENTOS SAIRÃO NA ORDEM EM QUE
ENTRARAM
9
B C DA
Filas (modelo conceitual)
retrieve
OS ELEMENTOS SAIRÃO NA ORDEM EM QUE
ENTRARAM
10
C DB
Filas (modelo conceitual)
retrieve
OS ELEMENTOS SAIRÃO NA ORDEM EM QUE
ENTRARAM
11
DC
Filas (modelo conceitual)
retrieve
OS ELEMENTOS SAIRÃO NA ORDEM EM QUE
ENTRARAM
12
D
7 8
9 10
11 12
3
─ A ─ ─ ─ ─ ── ─ ─ ─ ─ ─ ─D ─ ─ ─ ─ ─ ─
Filas (representação gráfica)
13
store(fila, 'D');
Rear
Front
retrieve(fila);
Rear
Front
store(fila, 'A');
Rear
Front
─ A B ─ ─ ─ ─ ─ A B C ─ ─ ─ ─ ─ B C ─ ─ ─
Filas (representação gráfica)
14
store(fila, 'B');
Rear
Front
store(fila, 'C');
Rear
Front
retrieve(fila);
Rear
Front
─ ─ B C D ─ ─ ─ ─ B C D E ─ ─ ─ ─ C D E ─
Filas (representação gráfica)
15
store(fila, 'D');
Rear
Front
store(fila, 'E');
Rear
Front
retrieve(fila);
Rear
Front
─ ─ ─ ─ D E ─ ─ ─ ─ ─ ─ E ─ ─ ─ ─ ─ ─ ─ ─
Filas (representação gráfica)
16
retrieve(fila);
Rear
Front
retrieve(fila);
Rear
Front
retrieve(fila);
Rear
Front
Filas (implementação)
◼ Implementaremos uma fila circular, pois é 
mais eficiente do que aquela onde 
“empurramos” os elementos para as 
posições iniciais do vetor;
◼ Na fila circular tanto o front quanto o rear
caminham em direção ao final do vetor, 
porém, no término do vetor, voltam ao 
seu início, trabalhando de forma circular.
17
Filas (implementação)
◼ Na inclusão colocamos o elemento na posição do rear
que, na sequência, irá para a próxima posição.
18
store(fila, 'B');
13 14
15 16
17 18
4
Filas (implementação)
◼ Na retirada retornamos o elemento que está no front
que, na sequência, irá para a próxima posição.
19
retrieve(fila);
Filas (implementação)
◼ A condição de fila cheia acontece 
quando o “próximo de rear” for igual ao 
front;
◼ A condição de fila vazia acontece 
quando front é igual ao rear;
◼ Essa é uma possível saída para fila cheia 
e vazia serem diferentes. Por conta 
dessa abordagem uma posição do vetor 
é “sacrificada”.
20
Filas (implementação)
◼ Consideremos para a nossa implementação um grupo de 
operações:
➢ create → inicializa a fila
➢ destroy → esvazia a fila
➢ isfull → verifica se está cheia 
➢ isempty → verifica se está vazia
➢ store → insere um elemento
➢ retrieve → retira um elemento
➢ next → indica a próxima posição
21
Filas (definição da estrutura)
22
typedef struct fila {
char vet[7];
int front, rear;
} TFila;
TFila
vet front rear
0 1 2 3 4 5 6
Filas (next)
23
int next(int n) {
return (n + 1) % 7;
}
int next(int n) {
if (n < 6)
return n + 1;
else
return 0;
}
A função next será responsável por informar a próxima 
posição, tanto para rear quanto para front.
Filas (create, destroy, isfull e isempty)
24
int isfull(TFila *f) {
if (next(f->rear) == f->front)
return 1;
else
return 0;
}
void createf(TFila *f) {
f->rear = f->front = 0;
}
void destroy(TFila *f) {
f->front = f->rear;
}
int isempty(TFila *f) {
if (f->rear == f->front)
return 1;
else
return 0;
}
19 20
21 22
23 24
5
Filas (isfull e isempty)
25
int isfull(TFila *f) {
return next(f->rear) == f->front;
}
int isempty(TFila *f) {
return f->rear == f->front;
}
char retrieve(TFila *f) {
if (isempty(f)) {
puts("underflow");
abort();
}
char aux = f->vet[f->front];
f->front = next(f->front);
return aux;
}
Filas (store e retrieve)
26
void store(TFila *f, char x) {
if (isfull(f)) {
puts("overflow");
abort();
}
f->vet[f->rear] = x;
f->rear = next(f->rear);
}
Filas (exemplo de utilização)
27
void isolaletra(char s[]) {
TFila f;
int i = 0, tam = strlen(s);
create(&f);
while (!isfull(&f) && i < tam)
store(&f, s[i++]);
i = 0;
while (!isempty(&f)) {
s[i++] = '[';
s[i++] = retrieve(&f);
s[i++] = ']';
}
s[i] = '\0';
}
[A][B][C][D][E][F]
ABCDEF
Filas (aplicações)
◼ Todo buffer funciona como uma fila, pois os primeiros 
caracteres que vão para o buffer são os primeiros a sair;
◼ Também são bastante utilizadas para a simulação de filas 
de espera do mundo real, como as de atendimento em 
bancos;
◼ Uma aplicação interessante de filas é a coloração de 
regiões (veja o arquivo coloracao_regioes.c).
28
25 26
27 28