Description
In this part the TA will solve the following questions. The students need not hand anything for this part.
Question 1
The class DynamicArrayStack below increases or decreases its physical size according to the needs of the application.
• DynamicArrayStack uses an array to store the elements of this stack;
• The interface Stack and its implementation, DynamicArrayStack, have a formal parameter type (in other words, the implementation uses the concept of generics types, introduced in Java 1.5);
• The initial capacity of this array is given by the first parameter of the constructor;
• The physical size of the array is increased by a fixed amount (increment) when the method void push( E elem ) is called and the array is full;
• The physical size of the array is decreased by a fixed amount (increment) during a call to the method E pop() if the number of free cells becomes increment or more;
• The increment is given by the second parameter of the constructor;
• The instance variable top designates the top element (i.e. the cell where the last element was inserted, or -1 if the stack is empty).
A. Correct at least 5 mistakes (compile-time or runtime errors) in the partial
implementation (see next two pages) by marking the error with a circle and writing down the correction.(10 marks)
B. Complete the partial implementation of the class DynamicArrayStack given the above information. (10 marks)
// Instance variables
private static E[] elems; // Stores the elements of this stack
private static int top = -1; // Designates the top element
private final int capacity; // Memorizes the initial capacity
private final int increment; // Used to increase/decrease the size
public DynamicArrayStack( int capacity, int increment ) {
E[] elems = new Object[ capacity ];
this.capacity = capacity;
this.increment = increment;
}
// Returns true if this stack is empty;
public boolean isEmpty() {
return top == 0;
}
public void push( E element ) {
if ( ___________________________ ) {
increaseSize();
}
elems[ top ] = element;
top++;
}
private void increaseSize() {
E[] newElems;
int newSize;
newSize= elems.length + increment;
newElems = ___________________________;
for ( int i=0; i
