Material didático para conceituar e implementar filas usando alocação estática sequencial

Material didático usado para ensinar o conceito de filas como listas restritas e apresentar possível implementação de filas circulares usando memória estática sequencial em Linguagem Pascal. O material começa conceituando listas lineares, apresenta o modelo conceitual de filas e uma representação gráfica, discute a implementação usando alocação estática sequencial e apresenta ainda algumas aplicações. A implementação é feita com comandos básicos da linguagem Pascal com o objetivo de facilitar a aprendizagem.

1. Estruturas de Dados ► Filas (Linguagem Pascal) Prof. Dr. Marcelo Duduchi Aux. Docente Lucio Nunes

2. 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

3. 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

4. Filas (modelo conceitual) 4 s tore A Novos elementos são armazenados no final da fila

5. B Filas (modelo conceitual) 5 store A Novos elementos são armazenados no final da fila

6. C Filas (modelo conceitual) 6 s tore A B Novos elementos são armazenados no final da fila

7. D Filas (modelo conceitual) 7 store A B C Novos elementos são armazenados no final da fila

8. 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

9. Filas (modelo conceitual) retrieve Os elementos sairão na ordem em que entraram 9 B C D A

10. Filas (modelo conceitual) r etrieve Os elementos sairão na ordem em que entraram 10 C D B

11. Filas (modelo conceitual) r etrieve Os elementos sairão na ordem em que entraram 11 D C

12. Filas (modelo conceitual) r etrieve Os elementos sairão na ordem em que entraram 12 D

13. ─ A ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ D ─ ─ ─ ─ ─ ─ Filas (representação gráfica) 13 s tore (fila, 'D ' ); Rear Front r etrieve (fila); Rear Front s tore (fila, ' A ' ); Rear Front

14. ─ A B ─ ─ ─ ─ ─ A B C ─ ─ ─ ─ ─ B C ─ ─ ─ Filas (representação gráfica) 14 s tore (fila, ' B ' ); Rear Front s tore (fila, ' C ' ); Rear Front r etrieve (fila); Rear Front

15. ─ ─ B C D ─ ─ ─ ─ B C D E ─ ─ ─ ─ C D E ─ Filas (representação gráfica) 15 s tore (fila, ' D ' ); Rear Front store (fila, ' E ' ); Rear Front r etrieve (fila); Rear Front

16. ─ ─ ─ ─ D E ─ ─ ─ ─ ─ ─ E ─ ─ ─ ─ ─ ─ ─ ─ Filas (representação gráfica) 16 r etrieve (fila); Rear Front r etrieve (fila); Rear Front r etrieve (fila); Rear Front

17. Filas (implementação) Implementaremos uma fila circular, pois é mais eficiente do que a quela 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

18. 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');

19. 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);

20. 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

21. Filas (implementação) Consideremos para a nossa implementação um grupo de operações: c reate → inicializa a fila d estroy → esvazia a fila is f ull → verifica se está cheia isempty → verifica se está vazia s tore → insere um elemento r etrieve → retira um elemento n ext → indica a próxima posição 21

22. Filas (definição da estrutura) 22 type TFila = record vet : array [ 1 .. 7 ] of char ; front , rear : integer ; end ; TFila vet front rear 1 2 3 4 5 6 7

23. Filas ( n ext ) 23 function next ( n : integer ): integer ; begin next := ( n mod 7 ) + 1 ; end ; function next ( n : integer ): integer ; begin if n < 7 then next := n + 1 else next := 1 ; end ; A função next será responsável por informar a próxima posição, tanto para rear quanto para front . PRIMEIRA VERSÃO SEGUNDA VERSÃO

24. Filas ( c reate , d estroy , isfull e isempty ) 24 function isfull ( var f : TFila ): boolean ; begin if next ( f . rear ) = f . front then isfull := true else isfull := false ; end ; procedure c reate ( var f : TFila ); begin f . front := 1 ; f . rear := 1 ; end ; procedure d estroy ( var f : TFila ); begin f . front := f . rear ; end ; function isempty ( var f : TFila ): boolean ; begin if f . rear = f . front then isempty := true else isempty := false ; end ;

25. Filas ( isfull e isempty ) 25 function isfull ( var f : TFila ): boolean ; begin isfull := next ( f . rear ) = f . front ; end ; function isempty ( var f : TFila ): boolean ; begin isempty := f . rear = f . front ; end ; SEGUNDA VERSÃO

26. function retrieve ( var f : TFila ): char ; var aux : char ; begin if isempty ( f ) then begin writeln ( ' underflow ' ); halt ; end ; aux := f . vet [ f . front ]; f . front := next ( f . front ); retrieve := aux ; end ; Filas ( s tore e r etrieve ) 26 procedure store ( var f : TFila ; x : char ); begin if isfull ( f ) then begin writeln ( 'overflow' ); halt ; end ; f . vet [ f . rear ] := x ; f . rear := next ( f . rear ); end ;

27. Filas (exemplo de utilização) 27 procedure isolaletra ( var s : string ); var f : TFila ; i , tam : integer ; begin create ( f ); i := 1 ; tam := length ( s ); while not isfull ( f ) and i <= tam do begin store ( f , s [ i ]); i := i + 1 ; end ; s := '' ; while not isempty ( f ) do s := s + '[' + retrieve ( f ) + ']' ; end ; [A][B][ C ][ D ][ E ][F] ABCDEF

28. 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