Implement the ADT stack (named Stack274) using an array to stores the entries. T
ID: 3874631 • Letter: I
Question
Implement the ADT stack (named Stack274) using an array to stores the entries. This class must implement the textbook’s StackInterface. Expand the array dynamically by 2X (i.e., a resizable array) when a push is called and the array is full.Also, reduce the size of the array (cut the array size in half) when a pop results in less than 25% of the array being used; the size of the array should always be at least 20. Maintain the stack’s bottom entry in stack[stack.length-1].
public interface StackInterface<T> {
/**
* Adds a new entry to the top of this stack.
*
* @param newEntry An object to be added to the stack.
*/
public void push(T newEntry);
/**
* Removes and returns this stack's top entry.
*
* @return The object at the top of the stack.
* @throws EmptyStackException if the stack is empty before the operation.
*/
public T pop();
/**
* Retrieves this stack's top entry.
*
* @return The object at the top of the stack.
* @throws EmptyStackException if the stack is empty.
*/
public T peek();
/**
* Detects whether this stack is empty.
*
* @return True if the stack is empty.
*/
public boolean isEmpty();
/** Removes all entries from this stack. */
public void clear();
public int size();
} // end StackInterface
Explanation / Answer
interface StackInterface {
public void push(Object item) throws StackOverflowException;
// Effect: Adds item to the top of this stack.
// Postcondition: If (this stack is full)
// an unchecked exception that communicates
// 'push on stack full' is thrown
// else
// item is at the top of this stack.
public void pop() throws StackUnderflowException;
// Effect: Removes top item from this stack
// Postconditions: If (this stack is empty)
// an unchecked exception that communicates
// 'pop on stack empty' is thrown
// else
// top element has been removed from this stack.
public Object top() throws StackUnderflowException;
// Effect: Returns a reference to the element on top of this stack
// Postconditions: If (this stack is empty)
// an unchecked exception that communicates
// 'top on stack empty' is thrown
// else
// return value = (top element of this stack).
public boolean isEmpty();
// Effect: Determines whether this stack is empty.
// Postcondition: Return value = (this stack is empty)
public boolean isFull();
// Effect: Determines whether this stack is full.
// Postcondition: Return value = (stack is full)
}
class StackOverflowException extends RuntimeException {
public StackOverflowException() {
}
public StackOverflowException(String message) {
super(message);
}
}
class StackUnderflowException extends RuntimeException {
public StackUnderflowException() {
}
public StackUnderflowException(String message) {
super(message);
}
}
public class ArrayStack implements StackInterface {
private Object[] stack; // Array that holds stack elements
private int topIndex = -1; // index of top element in stack
// Constructors
public ArrayStack() {
stack = new Object[100];
}
public ArrayStack(int maxSize) {
stack = new Object[maxSize];
}
public void push(Object item)
// Adds an element to the top of this stack
{
if (!isFull()) {
topIndex++;
stack[topIndex] = item;
} else
throw new StackOverflowException("Push attempted on a full stack.");
}
public void pop()
// Removes an element from the top of this stack
{
if (!isEmpty()) {
stack[topIndex] = null;
topIndex--;
} else
throw new StackUnderflowException("Pop attempted on an empty stack.");
}
public Object top()
// Returns the element on top of this stack
{
Object topOfStack = null;
if (!isEmpty())
topOfStack = stack[topIndex];
else
throw new StackUnderflowException("Top attempted on an empty stack.");
return topOfStack;
}
public boolean isEmpty()
// Checks if this stack is empty
{
if (topIndex == -1)
return true;
else
return false;
}
public boolean isFull()
// Checks if this stack is full
{
if (topIndex == (stack.length - 1))
return true;
else
return false;
}
}