Filas C v6

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 
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 D A 
Filas (modelo conceitual) 
retrieve 
OS ELEMENTOS SAIRÃO NA ORDEM EM QUE 
ENTRARAM 
10 
C D B 
Filas (modelo conceitual) 
retrieve 
OS ELEMENTOS SAIRÃO NA ORDEM EM QUE 
ENTRARAM 
11 
D C 
Filas (modelo conceitual) 
retrieve 
OS ELEMENTOS SAIRÃO NA ORDEM EM QUE 
ENTRARAM 
12 
D 
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'); 
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; 
} 
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) { 
 char aux; 
 if (isempty(f)) { 
 printf("underflow\n"); 
 abort(); 
 } 
 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)) { 
 printf("overflow\n"); 
 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 (pesquise!). 
28