Wiki**3

Este exercício saiu no teste de 2013/02/04.

Problema

Escreva em Java a classe Stack que usa vectores de dimensão fixa (definida no momento da criação) para guardar inteiros e tem 3 métodos: insert(Integer e) (insere o elemento e na pilha), remove() (remove o último elemento inserido na pilha) e exists(Integer e) (devolve true se o elemento e existe na pilha e false em caso contrário). Também deve ser definida outra classe que difere da anterior por não permitir a existência de elementos duplicados na pilha, ou seja, o método insert(Integer e) não insere o elemento e se já existir na pilha. Quando a pilha está vazia e se tenta remover um elemento e quando está cheia e se insere um novo elemento, devem ser lançadas excepções.

Solução

A solução contém quatro classes (2 stacks e 2 excepções). Note-se que a solução é mínima e que algumas opções não são ideais em casos gerais (o uso de vectores fixos, por exemplo). </div>

Ficheiro Stack.java: <java5> public class Stack {

 private int[] _contents;
 private int _last = 0;

 public Stack(int size) {
   _contents = new int[size];
 }

 public void insert(Integer e) throws StackOverflowException {
   if (_last == _contents.length) throw new StackOverflowException();
   _contents[_last++] = e;
 }

 public void remove() throws StackUnderflowException {
   if (_last == 0) throw new StackUnderflowException();
   _last--;  // in fact, it does not change the stack
 }

 public boolean exists(Integer e) {
   for (int i: _contents)
     if (i == (int)e) return true;
   return false;
 }

} </java5>

Ficheiro UStack.java (stack sem repetições): <java5> public class UStack extends Stack {

 public UStack(int size) { super(size); }

 @Override
 public void insert(Integer e) throws StackOverflowException {
   if (!exists(e)) super.insert(e);
 }

} </java5>

Ficheiros StackOverflowException.java e StackUnderflowException.java (excepções):

<java5> public class StackOverflowException extends Exception {} </java5>

<java5> public class StackUnderflowException extends Exception {} </java5>