3.11. O Tipo Abstrato de Dados Fila¶

O tipo de dados abstrato (abstract data type) da fila é definido pela seguinte estrutura e operações. Uma fila é estruturada, conforme descrito anteriormente, como uma coleção ordenada de itens que são inseridos em uma extremidade, chamada de “fim”, e removidos da outra extremidade, chamada de “início”. As filas mantêm uma ordenação FIFO. As operações da fila são dadas abaixo.

• Queue() cria uma nova fila que está vazia. Não precisa de parâmetros e retorna uma fila vazia.

• enqueue(item) insere um novo item no final da fila. Precisa o item e não retorna nada.

• dequeue() remove o item do início da fila. Não precisa de parâmetros e retorna o item. A fila é modificada.

• isEmpty() testa para ver se a fila está vazia. Não precisa de parâmetros e retorna um valor booleano (bool); True se a fila está vazia e False em caso contrário.

• size() retorna o número de itens na fila. Não precisa de parâmetros e retorna um inteiro (int).

Como exemplo, se supormos que q é uma fila que foi criada e está atualmente vazia, então Tabela 1 mostra o resultados de uma seqüência de operações sobre filas. O conteúdo da fila é mostrado de tal forma que o início está à direita. 4 foi o primeiro item enfileirado (enqueue()) por isso é o primeiro item removido e retornado dequeue().