Exercício 02.34

(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.

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 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.