Homework SourseImplement the ADT stack by using an array stack to contain i
Implement the ADT stack by using an array stack to contain its entries. Expand the array dynamically, as necessary. Maintain the stack’s bottom entry in stack[stack.length – 1].
Your Stack class must implement StackInterface (provided). You may use ArrayStack.java (provided) as the starting point for your implementation.
You must implement a comprehensive set of unit tests using the main() method (and private utility methods) in ArrayStack.java.
ArrayStack.java
public class ArrayStack<T> implements StackInterface<T>
{
private T[] stack; // Array of stack entries
private int topIndex; // Index of top entry
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 50;
private static final int MAX_CAPACITY = 10000;
public ArrayStack()
{
this(DEFAULT_CAPACITY);
} // end default constructor
public ArrayStack(int initialCapacity)
{
checkCapacity(initialCapacity);
// The cast is safe because the new array contains null entries
@SuppressWarnings(\"unchecked\")
T[] tempStack = (T[])new Object[initialCapacity];
stack = tempStack;
topIndex = -1;
initialized = true;
} // end constructor
// < Implementations of the stack operations go here. >
// < Implementations of the private methods go here; checkCapacity and
// checkInitialization are analogous to those in Chapter 2. >
// . . .
} // end ArrayStack
StackInterface.java
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();
} // end StackInterface
Solution
StackTester.java
public class StackTester
{
public static void main(String[] args)
{
ArrayStack<Integer> aS = new ArrayStack<Integer>();
aS.push(3);
aS.push(5);
aS.push(10);
aS.push(11);
System.out.println(\"\"+ aS.peek() + \", \" + aS.pop() + \", \" + aS.peek2());
aS.remove(1);
}
}
ArrayStack.java
import java.util.Arrays;
public class ArrayStack<T> implements StackInterface<T>
{
private T[] stack;
private int topIndex;
private boolean initialized = false;
private static final int DEFAULT_CAPACITY = 50;
private static final int MAX_CAPACITY = 10000;
public ArrayStack()
{
this(DEFAULT_CAPACITY);
}
public ArrayStack(int initialCapacity)
{
checkCapacity(initialCapacity);
@SuppressWarnings(\"unchecked\")
T[] tempStack = (T[])new Object[initialCapacity];
stack = tempStack;
topIndex = -1;
initialized = true;
}
public boolean isEmpty()
{
return topIndex < 0;
}
private void ensureCapacity()
{
if(topIndex == stack.length - 1)
{
int newLength = 2*stack.length;
checkCapacity(newLength);
stack = Arrays.copyOf(stack, newLength);
}
}
private void ensureCapacity(int n)
{
// add n slots to the array
if(topIndex == stack.length - 1){
int newLength = 2*stack.length + n;
checkCapacity(newLength);
stack = Arrays.copyOf(stack, newLength);
}
}
private boolean checkCapacity(int capacity)
{
boolean bool = true;
if(capacity > MAX_CAPACITY)
bool = false;
return bool;
}
private boolean checkInitialized()
{
return initialized;
}
public void push(T newEntry)
{
checkInitialized();
ensureCapacity();
stack[topIndex+1] = newEntry;
topIndex++;
}
public T pop()
{
checkInitialized();
if(!isEmpty())
{
T top = stack[topIndex];
stack[topIndex]= null;
topIndex --;
return top;
} else
{
throw new ArrayIndexOutOfBoundsException(\"Stack is empty\");
}
}
public T peek()
{
checkInitialized();
if(isEmpty())
{
throw new ArrayIndexOutOfBoundsException(\"Stack is empty\");
} else
return stack[topIndex];
}
public void clear()
{
stack = (T[]) new Object[DEFAULT_CAPACITY];
topIndex = -1;
}
public T peek2()
{
checkInitialized();
if(isEmpty())
{
throw new ArrayIndexOutOfBoundsException(\"Stack is empty\");
} else
return stack[topIndex-1];
}
public String toString()
{
String s = \"\";
for(int i = 0; i < stack.length; i++)
{
s += stack[i] + \",\";
}
return s;
}
public void remove(int n)
{
checkInitialized();
if(n <= topIndex)
{
for(int i = n; i < (topIndex - 1); i++)
{
stack[i] = stack[i+1];
}
}
}
public void pushAll(T[] a)
{
checkInitialized();
checkCapacity(topIndex + a.length);
ensureCapacity(a.length);
for(int i = 0; i < a.length; i ++)
{
stack[topIndex + 1] = a[i];
topIndex ++;
}
}
}
StackInterface.java
public interface StackInterface<T>
{
/** Adds a new entry to the top of this stack. */
public void push(T newEntry);
/** Removes and returns this stack\'s top entry.*/
public T pop();
/** Retrieves this stack\'s top entry. */
public T peek();
/** Detects whether this stack is empty. */
public boolean isEmpty();
/** Removes all entries from this stack. */
public void clear();
public T peek2(); // Returns the element below the top element, or throw an exception if there are less than two elements
public String toString(); // Returns a string that shows all of the elements on the stack. You can choose the format.
public void remove(int n); // removes the top n entries from the stack. Stops as soon as the stack is empty.
public void pushAll(T[] a); // pushes each element in the array , beginning with index 0.
}
