(Goodrich, 2007) Desenvolva uma classe chamada Stack
para representar o tipo abstrato de dados pilha. Uma pilha é uma estrutura de dados baseada no princípio LIFO, no qual o último 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 um único atributo denominado header
, que representa a referência para o nodo armazenado no topo da pilha. Os métodos especificados para o tipo abstrato de dados pilha são:
empty
- verifica se a pilha está vazia.peek
- recupera o elemento do topo da pilha, ou retorna zero caso a pilha esteja vazia.pop
- recupera e remove o elemento do topo da pilha, ou retorna zero caso a pilha esteja vazia.push
- insere um novo elemento no topo da pilha.size
- retorna a quantidade de elementos armazenados na pilha.
Goodrich, Michael. (2007). Estrutura de Dados e Algoritmos em Java. 4ª edição. Porto Alegre: Bookman. 600 páginas.