Homework Soursetwo additional files are attached EmptyCollectionExceptionja
two additional files are attached: EmptyCollectionException.java, and StackADT.java. These files will need to be added to your Java project. They provide data structure functionality that you will build over.
Q1: There is a data structure called a drop-out stack that behaves like a stack in every way except that the stack has a maximum capacity n. If the stack contains n elements, when the n+1 element is pushed, the bottom element is lost. For example, if the stack has a maximum capacity of 3, and contains the values (1, 2, 3), with 3 being the top element, then pushing a 4 would give the stack (2, 3, 4), with 4 being the top element. Implement a drop-out stack using an array. Follow the StackADT interface. See Base_A05Q2.java for a starting place. Hint: Can any of the ArrayStack code be reused?
StackADT.Java
EmptyCollectionException.java
Sample Output
DROP-OUT STACK T STING The stack contains: 5 3 2 The atack contains: 7 3Solution
import java.util.Arrays;
public class Base_A05Q2 {
public static void main(String[] args) { ArrayDropOutStack<Integer> stack = new ArrayDropOutStack<Integer>(3);
System.out.println(\"DROP-OUT STACK TESTING\");
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(\"The size of the stack is: \" + stack.size());
if(!stack.isEmpty())
System.out.println(\"The stack contains:\ \" + stack.toString());
stack.pop(4); stack.push(5); stack.push(6);
System.out.println(\"The size of the stack is: \" + stack.size());
if(!stack.isEmpty())
System.out.println(\"The stack contains:\ \" + stack.toString());
}
public static class ArrayDropOutStack<T> implements StackADT<T>
{
private final static int DEFAULT_CAPACITY = 100;
private int top; private int bottomElem = 0; private T[] stack;
/** * Creates an empty stack using the default capacity. */ public ArrayDropOutStack() { this(DEFAULT_CAPACITY);
}
/** * Creates an empty stack using the specified capacity. * @param initialCapacity the initial size of the array */ @SuppressWarnings(\"unchecked\")
public ArrayDropOutStack(int initialCapacity)
{
top = -1; stack = (T[])(new Object[initialCapacity]);
}
/** * Adds the specified element to the top of this stack, expanding * the capacity of the array if necessary. * @param element generic element to be pushed onto stack */ public void push(T element) { if (size() == stack.length) top = 0;
stack[top] = element; top++; }
/** * Removes the element at the top of this stack and returns a * reference to it. * @return element removed from top of stack * @throws EmptyCollectionException if stack is empty */ public T pop() throws EmptyCollectionException {
if (isEmpty()) throw new EmptyCollectionException(\"stack\");
T result = stack[top]; stack[top] = null;
if (top == 0) top = size()-1;
top--;
return result;
} /
** * Returns a reference to the element at the top of this stack. * The element is not removed from the stack. * @return element on top of stack * @throws EmptyCollectionException if stack is empty */ public T peek() throws EmptyCollectionException
{
if (isEmpty()) throw new EmptyCollectionException(\"stack\");
return stack[top];
}
/** * Returns true if this stack is empty and false otherwise. * @return true if this stack is empty */
public boolean isEmpty() { if(stack.length == 0) { return true; } else { return false; } } /** * Returns the number of elements in this stack. * @return the number of elements in the stack */
public int size() { int counter = 0;
for (int i = 0; i < stack.length; i++) {
if (stack[i] != null) { //counter ++; } }
return counter;
}
/** * Returns a string representation of this stack. The string has the * form of each element printed on its own line, with the top most * element displayed first, and the bottom most element displayed last. * If the list is empty, returns the word \"empty\". * @return a string representation of the stack */
public String toString()
{
String result = \"\";
for (int scan = top-1; scan >= 0; scan--)
result = result + stack[scan].toString() + \"\ \";
return result;
}
}
}
