Exercício 02.45

(Goodrich, 2007) Desenvolva uma classe chamada Queue para representar o tipo abstrato de dados fila. Uma fila é uma estrutura de dados baseada no princípio FIFO, no qual o primeiro elemento inserido é o primeiro elemento retirado. A classe utiliza uma lista duplamente encadeada de inteiros para o armazenamento dos elementos.

Uma lista duplamente encadeada (Doubly Linked List) é uma coleção de nodos (Node) que juntos formam uma ordem linear, no qual cada nodo é um objeto que armazena um elemento e duas referências, chamadas previous e next, para o nodo anterior e posterior ao presente nodo, respectivamente, conforme apresentado na Figura 01.

Representação de uma lista simplesmente encadeada — Figura 01: representação de uma lista simplesmente encadeada

A classe possui os seguintes atributos:

capacity - capacidade máxima de elementos armazenados na fila.
header - referência para o nodo armazenado no início da fila.
tailer - referência para o nodo armazenado no fim da fila.

A classe possui dois construtores: o primeiro configura a capacidade máxima de elementos armazenados na fila com o valor padrão 100, e o segundo recebe como parâmetro a capacidade máxima de elementos armazenados na fila. Os métodos especificados para o tipo abstrato de dados fila são:

empty - verifica se a fila está vazia.
offer - insere um novo elemento no fim da fila, retornando true caso o novo elemento seja inserido no início da fila, ou false caso a fila esteja cheia.
peek - recupera o elemento do início da fila, ou retorna zero caso a fila esteja vazia.
poll - recupera e remove o elemento do início da fila, ou retorna zero caso a fila esteja vazia.
size - retorna a quantidade de elementos armazenados na fila.