estrutura de dados

ESTRUTURAS DE DADOS
UNIDADE II – PILHAS E FILAS
Curso: Bacharelado em Ciência da Computação.
Prof. MsC. Dário Russillo. email: [e-mail]

2.3 Filas


Definição:






É um tipo especial de lista linear em que todas as operações de inserção e remoção são realizadas em extremidades distintas, denominadas de começo e término.
Os elementos são sempre removidos na mesma ordem em que foram inseridos, ou seja, o primeiro elemento que entra é exatamente o primeiro que sai (critério FIFO).

Representações:
Lista seqüencial  vetor ou um registro contendo um vetor e as extremidades começo e termino.
 Lista simplesmente (ou duplamente) encadeada (COM nó descritor) Pode-se também utilizar uma representação CIRCULAR*.


2.3 Filas
f.termino



Operações: inserções 

f.começo

Implementações sobre um vetor:



remoções

consultas

Da mesma forma que as pilhas, as filas também podem crescer ou decrescer durante a execução de um programa.
Quando se pode prever o tamanho máximo até o qual uma fila pode crescer, é possível realizá-la por meio de um registro contendo um vetor de dados e dois números inteiros que indicam o começo e o término das posições ocupadas pela fila no vetor: tipo Fila = registro inteiro: começo, termino; inteiro: elementos[N]; fimregistro Fila: f;

2.3 Filas


Ex: suponha que queremos armazenar as notas de 5 alunos em uma fila. A primeira nota inserida na fila é 3.1 e a última 7.9 como mostra a figura abaixo. As variáveis inteira começo e termino armazenam o índice onde, respectivamente a primeira e a última nota inserida estão localizadas.

tipo Fila = registro inteiro: começo, termino; inteiro: elementos[10]; fimregistro Fila: f;
f.comeco

1
f.termino
5

f.elementos

3.1

8.6

2.4

5.0

7.9

1

2

3

4

5

6

7

8

9

10

2.3 Filas
Suponha que sejam realizadas duas operações consecutivas de remoção na fila anterior e