Recall that a stack is an abstract data type (ADT) that allows only a limited number of operations on a collection of data. Elements are stored and removed in Last-in First-out (LIFO) order. In Part 1, you will implement a classIntStack using an integer array in theIntStack.java file.

In addition to the basic operations that Stack ADT has (e.g. push, pop, peek), theIntStack will have several special features which will be explained below. Make sure you understand howIntStack works before going into the implementation details.

• Size: The size of IntStack represents the number of elements within it.
• Capacity: The capacity of IntStack represents the maximum number of elements that the current IntStack can contain. In other words, it is the size of the integer array used by IntStack.
• Resizing: The capacity of the IntStack should be able to expand/shrink depending on the number of elements. (The reason behind this is that we want to push an arbitrary number of integers into the stack, but we cannot initialize an infinitely large array and we do not want to have too much memory taken up by unused array slots. That is why we want to have a dynamically resizing feature.)
  • Expanding - Load factor: The load factor is a decimal (0.67 <= LF <= 1 for this PA) which measures how full the array is allowed to get before its capacity is automatically increased. Whensize/capacity >= load factor, the capacity should be doubled.

new capacity = old capacity * 2

• Shrinking - Shrink factor: The shrink factor is a decimal (0 < SF <= 0.33 for this PA) which measures how empty the array is allowed to get before its capacity is automatically decreased. Whensize/capacity <= shrink factor, the capacity should be halved.

new capacity = old capacity / 2

However, you should make sure that your capacity will never become less than the initial array capacity. For example, if you initialized the stack with the capacity of 5, and your current capacity is 5 before shrinking, then the capacity should stay as 5.

• Exceptions: YourIntStack will need to throw certain exceptions under several circumstances (as described in the implementation details). You would also need to import the specified exceptions. Do not includethrowsin the method headers because the thrown exceptions are Runtime Exceptions. (Recall the difference betweenchecked vsunchecked exceptions). However, you should include the exceptions in the comments (/** .. */) with descriptions of when they will be thrown. You can refer to the format we used below in Part 1.2 when listing each method.

Part 1.2 Implementation

(Starter code below)

IMPORT EVERYTIHN NECESSARY

AND DONT CHANGE VARIABLE NAMES

import java.util.EmptyStackException;

public class IntStack {

private int[] data;

private int nElems;

private double loadFactor;

private double shrinkFactor;

public IntStack(int capacity, double loadF, double shrinkF) {

/* TODO */

}

public IntStack(int capacity, double loadF) {

/* TODO */

}

public IntStack(int capacity {

/* TODO */

}

public boolean isEmpty() {

/* TODO */

return false;

}

public void clear() {

/* TODO */

}

public void size() {

/* TODO */

}

public int capacity() {

/* TODO */

return 0;

}

public int peek() {

/* TODO */

return 0;

}

public void push(int element) {

/* TODO */

}

public int pop() {

/* TODO */

return 0;

}

public void multiPush(int [] elements) {

/* TODO */

}

public int[] multiPop (int amount ) {

/* TODO */

return null;

}

}

Constructors and methods to implement in IntStack.java

public IntStack(int capacity, double loadF, double shrinkF)

Constructor that initializes a stack with the given capacity, load factor and shrink factor. The valid range of capacity is (CAP >= 5), that of load factor is (0.67 <= LF <= 1), and that of shrink factor is (0 < SF <= 0.33).

@throws IllegalArgumentException

ifcapacity,loadF orshrinkF is out of valid range

public IntStack(int capacity, double loadF)

Constructor that initializes a stack with the given initial capacity, the given load factor, and the default shrink factor (0.25).

Hint:

Do not repeat yourself! You might find "this()" useful.

@throws IllegalArgumentException

ifcapacity orloadF is out of valid range

public IntStack(int capacity)

Constructor that initializes a stack with the given initial capacity, the default load factor (0.75), and the default shrink factor (0.25).

Hint:

Do not repeat yourself! You might find "this()" useful.

@throws IllegalArgumentException

ifcapacity is out of valid range

public boolean isEmpty()

Checks if the stack is empty. Returns true if it is empty, false otherwise.

public void clear()

Clears all elements in the stack. After clearing, the capacity of your stack should be reset to the initial capacity.

public int size()

Returns the number of elements currently stored in the stack.

public int capacity()

Returns the maximum number of elements the stack currently can store. In other words, the length of the backed data array.

public int peek()

Returns the top element of the stack.

@throws EmptyStackException

if the stack is empty

public void push(int element)

Pushes the givenelement to the stack. Double the capacity of the stackbefore pushing theelement if the condition meets.

public int pop()

Returns and removes the top element of the stack. Half the capacity of the stackafter popping the element if the condition meets. Note that if after shrinking, the stack will be smaller than the initial capacity, resize it to the initial capacity.

@throws EmptyStackException

if the stack is empty

public void multiPush(int[] elements)

Pushes all numbers in the arrayelementsto the stack. Elements in the front of the arrayelements(at index 0) should be pushed to the stack first.

@throws IllegalArgumentException

ifelementsis null

public int[] multiPop(int amount)

Pops the givenamount of elements from the stack. If the stack does not have the givenamount of elements, pop all elements from the stack. Returns an int array that contains all popped elements. Elements popped first should be placed in the front of the output array. The length of the returned array should be identical to the number of elements you popped.

@throws IllegalArgumentException

ifamount is not a positive number

Part 1.3 JUnit Testing

For this part, you must use JUnit to test your code. Create aJUnit 4 test file calledIntStackTest.java, and include at least3 assertions (tests) for each constructor and methods. In addition to that, you should test all possible cases that throw an exception. For test files, we will not grade on style, so you don't need to worry about style requirements like magic numbers, comments and headers. This test file will be a part of your submission.

To test the exception, you can use the following piece of code:

@Test (expected =IllegalArgumentException.class) // or any exception you expect

public void testExceptionExample() {

// code that is expected to throw the exception

}

This method will pass when the specified exception is thrown, and will fail otherwise. Note that a test method like this can only test one throw. Thus, for each exception case, you need to make a separate test method.