Create a class called ArrayBasedStack and have it implement the StackADT interface. Make sure you include the generic type argument T in the class declaration:

public class ArrayBasedStack implements StackADT

Let Eclipse add stubs for all the unimplemented methods of StackADT by clicking on the hint next to the class signature and selecting Add Unimplemented Methods. You will be implementing these methods later.

Now create three fields.

• One will be an array, which is the base of the stack you are implementing. Match the type of the array to the type indicated by your class.

  private T[] stackArray;

• The second field will represent the size, which is the number of elements in the stack.
• The third will represent the capacity, which should match the length of the array.

Create a constructor with a single parameter which specifies the initial capacity of your array. Within the constructor, initialize all the three fields you just created. For initializing your stackArray field, refer to the next section on how to create generic arrays. Initialize your size field to 0 (Remember that your textbook represents size as topIndex and initializes it with -1. But in this lab instead of topIndex, use size and initialize it with 0). Initialize your capacity field with the parameter value.

Now create the default constructor and have it call the non-default constructor with an initial capacity of 100. Calling another constructor of the same class is called constructor chaining and is a good practice. Note that you go create a chain from the most generic constructor (in this case the default constructor) to the most specific constructor (in this case, the one-parameter constructor) by providing default values for parameters. (Hint: you should use this() method)

Aside: Creating generic arrays

When creating an array of a generic type, you have to cast an Object[] to the generic type:

@SuppressWarnings(unchecked) stackArray = (T[]) new Object[capacity];

Note: @SuppressWarnings("unchecked") annotation should be placed above the constructor.

The @SuppressWarnings("unchecked") annotation prevents Eclipse from displaying a warning about the type cast being potentially unsafe. We know that our cast is safe since Object is the root type of the Java class hierarchy, and any Object[] can be used to store instances of any other class. The@SuppressWarnings("unchecked") annotation can be placed above types, fields, constructors, methods, parameters, and local variables.

ArrayBasedStackTest

Create a class called ArrayBasedStackTest and implement your test cases. Set up the class by adding any fields you need and creating your setUp() method. Now copy and paste the methods you wrote for the Pre-Lab into the test class. Run them and make sure they compile. The tests should fail until you have implemented the methods.

Reference: How to write JUnit tests

ArrayBasedStack

Now you will implement the methods in the ArrayBasedStack class. The implementation for four methods is provided for you below.

When you are implementing your methods, be sure to consider which methods should throw an Exception and the type of Exception to throw. To throw an exception in a method, use the following:

throw new EmptyStackException();

To use the exception shown above, you will need to import the following:

import java.util.EmptyStackException;

Important: Make sure your tests catch any exceptions thrown!

Provided methods:

Copy and paste the following four methods in your ArrayBasedStack class.

toArray()

@Override public T[] toArray() { @SuppressWarnings("unchecked") T[] copy = (T[]) new Object[this.size()]; for (int i = 0; i < this.size(); i++) { copy[i] = this.stackArray[i]; } return copy; }

expandCapacity() (this method should help with your push() method):

/** * Expands the capacity of the stack by doubling its current capacity. */ private void expandCapacity() { @SuppressWarnings("unchecked") T[] newArray = (T[]) new Object[this.capacity * 2]; for (int i = 0; i < this.capacity; i++) { newArray[i] = this.stackArray[i]; } this.stackArray = newArray; this.capacity *= 2; }

toString()

/** * Returns the string representation of the stack. * * [] (if the stack is empty) * [bottom, item, ..., item, top] (if the stack contains items) * * @return the string representation of the stack. */ @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append('['); boolean firstItem = true; for (int i = 0; i < this.size(); i++) { if (!firstItem) { builder.append(", "); } else { firstItem = false; } // String.valueOf will print null or the toString of the item builder.append(String.valueOf(this.stackArray[i])); } builder.append(']'); return builder.toString(); }

@Override public boolean equals(Object other) { if (this == other) { return true; } if (other == null) { return false; } if (this.getClass().equals(other.getClass())) { ArrayBasedStack otherStack = (ArrayBasedStack) other; if (this.size() != otherStack.size()) { return false; } Object[] otherArray = otherStack.toArray(); for (int i = 0; i < this.size(); i++) { if (!(this.stackArray[i].equals(otherArray[i]))) { return false; } } return true; } return false; }

Implement other methods

Implement all the remaining methods in your ArrayBasedStack class. Run all the test cases and make sure all test cases are correct before submitting to web-cat.

Note: Remember that your peek() and pop() method need to throw EmptyStackExceptionwhen the stack is empty. Also, when implementing push() method, you need to check if stack is full. If stack is full, call expandCapacity() method to expand the capacity of the stack and then add the element in the stack.

Create a class called ArrayBasedStack and have it implement the StackADT interface. Make sure you include the generic type argument T in the class declaration:

public class ArrayBasedStack implements StackADT

Let Eclipse add stubs for all the unimplemented methods of StackADT by clicking on the hint next to the class signature and selecting Add Unimplemented Methods. You will be implementing these methods later.

Now create three fields.

• One will be an array, which is the base of the stack you are implementing. Match the type of the array to the type indicated by your class.

  private T[] stackArray;

• The second field will represent the size, which is the number of elements in the stack.
• The third will represent the capacity, which should match the length of the array.

Create a constructor with a single parameter which specifies the initial capacity of your array. Within the constructor, initialize all the three fields you just created. For initializing your stackArray field, refer to the next section on how to create generic arrays. Initialize your size field to 0 (Remember that your textbook represents size as topIndex and initializes it with -1. But in this lab instead of topIndex, use size and initialize it with 0). Initialize your capacity field with the parameter value.

Now create the default constructor and have it call the non-default constructor with an initial capacity of 100. Calling another constructor of the same class is called constructor chaining and is a good practice. Note that you go create a chain from the most generic constructor (in this case the default constructor) to the most specific constructor (in this case, the one-parameter constructor) by providing default values for parameters. (Hint: you should use this() method)

Aside: Creating generic arrays

When creating an array of a generic type, you have to cast an Object[] to the generic type:

@SuppressWarnings(unchecked) stackArray = (T[]) new Object[capacity];

ArrayBasedStackTest

Create a class called ArrayBasedStackTest and implement your test cases.

ArrayBasedStack

Now you will implement the methods in the ArrayBasedStack class. The implementation for four methods is provided for you below.

When you are implementing your methods, be sure to consider which methods should throw an Exception and the type of Exception to throw. To throw an exception in a method, use the following:

throw new EmptyStackException();

To use the exception shown above, you will need to import the following:

import java.util.EmptyStackException;

Important: Make sure your tests catch any exceptions thrown!

Provided methods:

Copy and paste the following four methods in your ArrayBasedStack class.

toArray()

@Override public T[] toArray() { @SuppressWarnings("unchecked") T[] copy = (T[]) new Object[this.size()]; for (int i = 0; i < this.size(); i++) { copy[i] = this.stackArray[i]; } return copy; }

expandCapacity() (this method should help with your push() method):

/** * Expands the capacity of the stack by doubling its current capacity. */ private void expandCapacity() { @SuppressWarnings("unchecked") T[] newArray = (T[]) new Object[this.capacity * 2]; for (int i = 0; i < this.capacity; i++) { newArray[i] = this.stackArray[i]; } this.stackArray = newArray; this.capacity *= 2; }

toString()

@Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append('['); boolean firstItem = true; for (int i = 0; i < this.size(); i++) { if (!firstItem) { builder.append(", "); } else { firstItem = false; } // String.valueOf will print null or the toString of the item builder.append(String.valueOf(this.stackArray[i])); } builder.append(']'); return builder.toString(); }

equals(Object other)

/** * Two stacks are equal iff they both have the same size and contain the * same elements in the same order. * * @param other * the other object to compare to this * * @return {@code true}, if the stacks are equal; {@code false} otherwise. */ @Override public boolean equals(Object other) { if (this == other) { return true; } if (other == null) { return false; } if (this.getClass().equals(other.getClass())) { ArrayBasedStack otherStack = (ArrayBasedStack) other; if (this.size() != otherStack.size()) { return false; } Object[] otherArray = otherStack.toArray(); for (int i = 0; i < this.size(); i++) { if (!(this.stackArray[i].equals(otherArray[i]))) { return false; } } return true; } return false; }

I

Note: Remember that your peek() and pop() method need to throw EmptyStackExceptionwhen the stack is empty. Also, when implementing push() method, you need to check if stack is full. If stack is full, call expandCapacity() method to expand the capacity of the stack and then add the element in the stack.

public interface StackADT { /** * Checks if the stack is empty. * @return Returns true if the stack is empty. */ public boolean isEmpty(); /** * Checks the item at the top of the * stack without removing it. * @return Item at the top of the stack. */ public T peek(); /** * Removes the item at the top of * the stack. * @return The item that was removed. */ public T pop(); /** * Pushes an item onto the stack. * @param item Item to be pushed * onto the stack. */ public void push(T item); /** * Checks if an item is in the stack. * @param item Item to be looked for. * @return Returns true if the item is * somewhere in the stack. */ public boolean contains(T item); /** * Number of items in the stack. * @return The number of items in * the stack. */ public int size(); /** * Clears the stack (removes all of * the items from the stack). */ public void clear(); /** * Returns an array with a copy of each element in the stack with the top of * the stack being the last element * * @return the array representation of the stack */ public Object[] toArray(); }