AEDS COLTEC aula4 filas

Prévia do material em texto

Aula 4: Filas
Professor(a): Virgínia Fernandes Mota
http://www.dcc.ufmg.br/⇠virginiaferm
ALGORITMOS E ESTRUTURAS DE DADOS - SETOR DE INFORMÁTICA
Virgínia Fernandes Mota Aula 4: Filas
Filas
Uma estrutura de dados bastante usada em computação é a
fila.
Enquanto na pilha "o último que entra é o primeiro que sai"na
fila tempos "o primeiro que entra é o primeiro que sai".
FIFO - first in first out.
Exemplo de uso: Fila de impressão.
Virgínia Fernandes Mota Aula 4: Filas
Filas
Consideraremos duas estratégias para implementação: com
vetor ou com lista encadeada.
Uma estrutura de fila pode ser composta pelas seguintes
operações:
criar uma fila vazia;
inserir um elemento no fim;
retirar o elemento do início;
verificar se a fila está vazia;
liberar a fila.
Virgínia Fernandes Mota Aula 4: Filas
Filas
O arquivo fila.h pode conter o seguinte código.
1 t yp ed e f s t r u c t f i l a F i l a ;
2
3 F i l a ⇤ f i l a _ c r i a ( ) ;
4 vo i d f i l a _ i n s e r e ( F i l a ⇤ f , f l o a t v ) ;
5 f l o a t f i l a _ r e t i r a ( F i l a ⇤ f ) ;
6 i n t f i l a_ v a z i a ( F i l a ⇤ f ) ;
7 vo i d f i l a _ l i b e r a ( F i l a ⇤ f ) ;
O tipo fila criado pode ser implementado usando vetor ou
lista encadeada
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor
Assim como na pilha, devemos fixar o número máximo N de
elementos na fila.
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor
É fácil observar que, em um dado instante, a parte ocupada do
vetor pode chegar à última posição.
Para reaproveitar as primeiras posições livres do vetor sem
implementar uma re-arrumação complicada dos elementos,
podemos incrementar as posições do vetor de forma "circular".
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor
Podemos definir uma função auxiliar responsável por
incrementar o valor de um índice em uma unidade.
Com o uso do operado módulo, em geral optamos por
dispensar a função auxiliar.
1 s t a t i c i n t i n c r ( i n t i ) {
2 i f ( i == N � 1)
3 r e t u r n 0 ;
4 e l s e
5 r e t u r n i +1;
6 }
1 s t a t i c i n t i n c r ( i n t i ) {
2 r e t u r n ( i +1) % N
3 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor
Podemos declarar o tipo fila como sendo uma estrutura com
três componentes:
um vetor vet de tamanho N;
um inteiro n que representa o número de elementos
armazenados na fila; e,
um índice ini para o início da fila.
ini marca a posição do próximo elemento a ser retirado da fila
e fim marca a posição (vazia) em que será inserido o próximo
elemento.
Podemos calcular o índice fim incrementando ini de n
unidades:
fim = (ini + n)%N
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor
A estrutura de fila é então:
1 #d e f i n e N 100
2
3 s t r u c t f i l a {
4 i n t n ;
5 i n t i n i ;
6 f l o a t v e t [N ] ;
7 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor - Função Cria
1 F i l a ⇤ f i l a _ c r i a ( ) {
2 F i l a ⇤ f = ( F i l a ⇤) ma l l o c ( s i z e o f ( F i l a ) ) ;
3 f�>n = 0 ;
4 f�>i n i = 0 ;
5 r e t u r n f ;
6 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor - Função Insere
1 vo i d f i l a _ i n s e r e ( F i l a ⇤ f , f l o a t v ) {
2 i n t f im ;
3 i f ( f�>n == N){
4 p r i n t f ( " Capac idade da f i l a e s t ou r ou \n" ) ;
5 e x i t (1 ) ;
6 }
7 f im = ( f�>i n i + f�>n) % N;
8 f�>vet [ f im ] = v ;
9 f�>n++;
10 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor - Função Retira
1 f l o a t f i l a _ r e t i r a ( F i l a ⇤ f ) {
2 f l o a t v ;
3 i f ( f i l a_ v a z i a ( f ) ) {
4 p r i n t f ( " F i l a v a z i a \n" ) ;
5 e x i t (1 ) ;
6 }
7 v = f�>vet [ f�>i n i ] ;
8 f�>i n i = ( f�>i n i + 1) % N;
9 f�>n��;
10 r e t u r n v ;
11 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor - Função Vazia
1 i n t f i l a_ v a z i a ( F i l a ⇤ f ) {
2 r e t u r n ( f�>n == 0) ;
3 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com vetor - Função Libera
1 vo i d f i l a _ l i b e r a ( F i l a ⇤ f ) {
2 f r e e ( f ) ;
3 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com lista
Vamos agora ver como implementar uma fila usando lista
encadeada!
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com lista
A estrutura de fila usando lista encadeada é então:
1 s t r u c t l i s t a {
2 f l o a t i n f o ;
3 s t r u c t l i s t a ⇤prox ;
4 } ;
5
6 s t r u c t f i l a {
7 L i s t a ⇤ i n i ;
8 L i s t a ⇤ f im ;
9 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com lista - Função Cria
1 F i l a ⇤ f i l a _ c r i a ( ) {
2 F i l a ⇤ f = ( F i l a ⇤) ma l l o c ( s i z e o f ( F i l a ) ) ;
3 f�>i n i = f�>fim = NULL ;
4 r e t u r n f ;
5 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com lista - Função Insere
1 vo i d f i l a _ i n s e r e ( F i l a ⇤ f , f l o a t v ) {
2 L i s t a ⇤n = ( L i s t a ⇤) ma l l o c ( s i z e o f ( L i s t a ) ) ;
3 n�>i n f o = v ;
4 n�>prox = NULL ; // novo nó pas sa a s e r o ú l t imo
5 i f ( f�>fim != NULL) // v e r i f i c a se a f i l a não e s t á v a z i a
6 f�>fim�>prox = n ;
7 e l s e
8 f�>i n i = n ;
9 f�>fim = n ;
10 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com lista - Função Retira
1 f l o a t f i l a _ r e t i r a ( F i l a ⇤ f ) {
2 L i s t a ⇤ t ;
3 f l o a t v ;
4 i f ( f i l a_ v a z i a ( f ) ) {
5 p r i n t f ( " F i l a v a z i a \n" ) ;
6 e x i t (1 ) ;
7 }
8 t = f�>i n i ;
9 v = t�>i n f o ;
10 f�>i n i = t�>prox ;
11 i f ( f�>i n i == NULL) // v e r i f i c a se a f i l a f i c o u v a z i a
12 f�>fim = NULL ;
13 f r e e ( t ) ;
14 r e t u r n v ;
15 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com lista - Função Vazia
1 i n t f i l a_ v a z i a ( F i l a ⇤ f ) {
2 r e t u r n ( f�>i n i == NULL) ;
3 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila com lista - Função Libera
1 vo i d f i l a _ l i b e r a ( F i l a ⇤ f ) {
2 L i s t a ⇤q = f�>i n i ;
3 wh i l e ( q != NULL) {
4 L i s t a ⇤ t = q�>prox ;
5 f r e e ( q ) ;
6 q = t ;
7 }
8 f r e e ( f ) ;
9 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila - Impressão
1 // impr ime : v e r s ã o com ve t o r
2 vo i d f i l a_ impr ime_vet ( F i l a ⇤ f ) {
3 i n t i ;
4 f o r ( i = 0 ; i < f�>n ; i++)
5 p r i n t f ( "%f \n" , f�>vet [ ( f�>i n i + i )%N] ) ;
6 }
1 // impr ime : v e r s ã o com l i s t a
2 vo i d f i l a_ imp r im e_ l i s t a ( F i l a ⇤ f ) {
3 L i s t a ⇤q ;
4 f o r ( q = f�>i n i ; q != NULL ; q = q�> prox )
5 p r i n t f ( "%f \n" , q�>i n f o ) ;
6 }
Virgínia Fernandes Mota Aula 4: Filas
Implementação de fila
1 #i n c l u d e <s t d i o . h>
2 #i n c l u d e " f i l a . h"
3
4 i n t main ( ) {
5 F i l a ⇤ f = f i l a _ c r i a ( ) ;
6 f i l a _ i n s e r e ( f , 2 0 . 0 ) ;
7 f i l a _ i n s e r e ( f , 4 2 . 0 ) ;
8 f i l a _ i n s e r e ( f , 1 3 . 0 ) ;
9 p r i n t f ( " P r ime i r o e lemento : %f " , f i l a _ r e t i r a ( f ) ) ;
10 f i l a_ imp r ime ( f ) ;
11 f i l a _ l i b e r a ( f ) ;
12 r e t u r n 0 ;
13 }
Virgínia Fernandes Mota Aula 4: Filas
Fila dupla
A estrutura de dados que chamamos de fila dupla consiste em
uma fila na qual é possível inserir novos elementos nas duas
extremidades (início e fim).
Da mesma forma, na fila dupla é possível retirar elementos dos
dois extremos.
Uma estrutura de fila dupla pode ser composta pelas seguintes
operações:
criar uma estrutura de fila dupla;
inserir um novo elemento no início;
inserir um novo elemento no fim;
retiraro elemento do início;
retirar o elemento do fim;
verificar se a fila está vazia;
liberar a fila.
Virgínia Fernandes Mota Aula 4: Filas
Fila dupla
O arquivo fila2.h pode conter o seguinte código.
1 t yp ed e f s t r u c t f i l a 2 F i l a 2 ;
2
3 F i l a 2 ⇤ f i l a 2_ c r i a ( ) ;
4 vo i d f i l a 2_ i n s e r e_ i n i ( F i l a 2 ⇤ f , f l o a t v ) ;
5 vo i d f i l a 2_ i n s e r e_ f im ( F i l a 2 ⇤ f , f l o a t v ) ;
6 f l o a t f i l a 2_ r e t i r a _ i n i ( F i l a 2 ⇤ f ) ;
7 f l o a t f i l a 2_ r e t i r a_ f im ( F i l a 2 ⇤ f ) ;
8 i n t f i l a 2_ v a z i a ( F i l a 2 ⇤ f ) ;
9 vo i d f i l a 2 _ l i b e r a ( F i l a 2 ⇤ f ) ;
Virgínia Fernandes Mota Aula 4: Filas
Fila dupla com vetor
Vamos analisar as duas novas funções: insere_ini e retira_fim.
1 vo i d f i l a 2_ i n s e r e_ i n i ( F i l a ⇤ f , f l o a t v ) {
2 i n t p r e c ;
3 i f ( f�>n == N){
4 p r i n t f ( " Capac idade da f i l a e s t ou r ou . \n" ) ;
5 e x i t (1 ) ;
6 }
7 // i n s e r e e lemento na po s i ç ã o p r e c eden t e ao i n í c i o
8 p r ec = ( f�>i n i � 1 + N) % N;
9 f�>vet [ p r e c ] = v ;
10 f�>i n i = prec ;
11 f�>n++;
12 }
Virgínia Fernandes Mota Aula 4: Filas
Fila dupla com vetor
1 f l o a t f i l a 2_ r e t i r a_ f im ( F i l a ⇤ f ) {
2 i n t u l t ;
3 f l o a t v ;
4 i f ( f i l a 2_ v a z i a ( f ) ) {
5 p r i n t f ( " F i l a v a z i a . \n" ) ;
6 e x i t (1 ) ;
7 }
8 u l t = ( f�>i n i + f�>n � 1) % N;
9 v = f�>vet [ u l t ] ;
10 f�>n��;
11 r e t u r n v ;
12 }
Virgínia Fernandes Mota Aula 4: Filas
Exercícios
1. Implementar as funções/procedimentos apresentados em sala
para a manipulação de filas. Crie filas.c e filas.h para a
manipulação das filas (com vetor e com lista) e main.c para testes.
Crie um makefile para compilar o código.
2. Implementar as funções/procedimentos apresentados em sala
para a manipulação de filas duplas. Crie filas2.c e filas2.h para a
manipulação das filas (com vetor e com lista) e main.c para testes.
Crie um makefile para compilar o código.
Virgínia Fernandes Mota Aula 4: Filas
Exercícios
3. Vamos montar um estacionamento! Compramos um terreno que
possui uma entrada e uma saída. Quando chega um novo carro,
este é estacionado no terreno, um atrás do outro. Quando um
carro precisa sair, os carros do terreno são retirados pela saída, dão
uma volta na quadra e são colocados no final da fila pela entrada
do estacionamento. Faça um programa que inclua carros no
estacionamento informando o número da placa e retire carros
usando o identificador (placa). Depois de ter informado a placa,
exiba o estado do estacionamento.
Virgínia Fernandes Mota Aula 4: Filas
Na próxima aula...
Prova
Virgínia Fernandes Mota Aula 4: Filas