Data Structures Using Java

Problem 1 (25 points)

Implement the method

public void display()

which displays the entries in a stack starting from the top. If the stack is empty, print The stack is empty.

Add the method to ArrrayStack2.java. You do not need to modify StackInterface.java.

Problem 2 (25 points)

Implement a method

public int remove(int n)

The method removes the n top most entries for a stack . If the stack contains less than n items, the stack becomes empty. The method returns the number of items removed.

Add the method to ArrrayStack2.java. You do not need to modify StackInterface.java.

Problem 3 (50 points)

Suppose that in the array-based stack, the array doubles in size after multiple push operations. But later on, fewer than half of the arrays locations might actually be used by the stack due to pop operations.

Revise the implementation so that its array also can shrink in size as objects are removed from the stack. Accomplishing this task will require two new private methods, as follows:

The first new method checks whether we should reduce the size of the array:

private boolean isTooBig()

This method returns true if the number of entries in the stack is less than half the size of the array and the size of the array is greater than 20.

The second new method creates a new array that is three quarters the size of the current array and then copies the objects in the bag to the new array:

private void reduceArray()

Implement each of these two methods, and then use them in the definition of pop()

For a programming question, submit a .java file (for source code and test cases) and program output.