(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.
A classe possui os seguintes atributos:
header
- referência para o nodo armazenado no início da fila.tailer
- referência para o nodo armazenado no fim da 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.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.
Goodrich, Michael. (2007). Estrutura de Dados e Algoritmos em Java. 4ª edição. Porto Alegre: Bookman. 600 páginas.