(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 simplesmente encadeada de inteiros para o armazenamento dos elementos.
Uma lista simplesmente encadeada (Singly 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 uma referência, chamada next
, para o próximo nodo, conforme apresentado na Figura 01.
A classe possui os seguintes atributos:
capacity
- capacidade máxima de elementos armazenados na pilha.header
- referência para o nodo armazenado no topo da pilha.A classe possui dois construtores: o primeiro configura a capacidade máxima de elementos armazenados na pilha com o valor padrão 100
, e o segundo recebe como parâmetro a capacidade máxima de elementos armazenados na 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, retornando true
caso o novo elemento seja inserido no topo da pilha, ou false
caso a pilha esteja cheia.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.