1.2 Implement the method clear() of the class ArrayStack

The class ArrayStack uses an array of fixed size and implements the interface Stack. Since the interface Stack has been modified to have the method clear(), the implementation of the class ArrayStack is faulty. (Try to compile it now without changing anything, what error do you see?).

Since the class ArrayStack implements the interface Stack, it needs to have an implementation for all methods of the interface. Therefore, you will need to write a method void clear(). This method will remove all the elements from this stack (ArrayStack). The stack will be empty after this call. Use the class L6Q1 to test the implementation of the method clear().

Files:

• ArrayStack.java
• L6Q1.java

1.3 Create a new class DynamicArrayStack

Modify the class ArrayStack using the technique known as dynamic array. This new class DynamicArrayStack has a constant DEFAULT_INC, with the value 25. The constructor takes an argument capacity which is the initial size of the array. However, the minimum size of the array is never less that DEFAULT_INC (25). It has a getter, getCapacity(), that returns an integer, which is the length of the array (physical size of the stack). When the array becomes full, a new array is created with DEFAULT_INC more cells than the previous array, and filled with the elements from the previous array. Similarly, when the stack has DEFAULT_INC elements less than the length of the array (physical size of the stack), it needs to be automatically reduced in size. Make the necessary changes, particularly in pop, push and clear, and in the constructor (recall, the minimal size of an array is DEFAULT_INC).

File:

• DynamicArrayStack.java

Here is the Stack Interface:

public interface Stack {

public abstract boolean isEmpty();

public abstract E peek();

public abstract E pop();

public abstract void push( E element);

public void clear();

}

ArrayStack.Java:

public class ArrayStack implements Stack { private E[] elems; // Used to store the elements of this ArrayStack private int top; // Designates the first free cell private int capacity; // Designates the capacity of the Array @SuppressWarnings( "unchecked" ) // Constructor public ArrayStack( int capacity ) { elems = (E[]) new Object[ capacity ]; top = 0; this.capacity = capacity; } // Returns true if this ArrayStack is empty public boolean isEmpty() { // Same as: // if ( top == 0 ) { // return true; // } else { // return false; // } return ( top == 0 ); } // Returns the top element of this ArrayStack without removing it public E peek() { // pre-conditions: ! isEmpty() return elems[ top-1 ]; } // Removes and returns the top element of this stack public E pop() { // pre-conditions: ! isEmpty() // *first* decrements top, then access the value! E saved = elems[ --top ]; elems[ top ] = null; // scrub the memory! return saved; } // Puts the element onto the top of this stack. public void push( E element ) { // Pre-condition: the stack is not full // *first* stores the element at position top, then increments top elems[ top++ ] = element; } // Gets current capacity of the array (for testing purpose) public int getCapacity() { return elems.length; } @SuppressWarnings( "unchecked" ) // Add clear method. }

And finally DynamicArrayStack.java:

public class DynamicArrayStack implements Stack { // Instance variables private E[] elems; // Used to store the elements of this ArrayStack private int top; // Designates the first free cell private static final int DEFAULT_INC = 25; //Used to store default increment / decrement @SuppressWarnings( "unchecked" ) // Constructor public DynamicArrayStack( int capacity ) { // Your code here. } // Gets current capacity of the array public int getCapacity() { return elems.length; } // Returns true if this DynamicArrayStack is empty public boolean isEmpty() { return ( top == 0 ); } // Returns the top element of this ArrayStack without removing it public E peek() { return elems[ top-1 ]; } @SuppressWarnings( "unchecked" ) // Removes and returns the top element of this stack public E pop() { // Your code here. } @SuppressWarnings( "unchecked" ) // Puts the element onto the top of this stack. public void push( E element ) { // Your code here. } @SuppressWarnings( "unchecked" ) public void clear() { // Your code here. } }

Detailed Comments with explanations would be greatly appreciated!