Design classes with the given specification in each problem, along with the appropriate test suite. Each method in a class, excluding mutators, accessors, and constructors, must include proper Javadoc comments describing the (1) purpose of the method, (2) parameters, and (3) return value.
Do not round your solutions. For example, do not use
Math.round or float your output to, e.g.,
2 decimal places, unless specified.
You may not use anything beyond Chapter 4.2. This includes but is not limited to:
getClass() methodObjects.equalsSystem.arraycopy, Arrays.copyOf.Any violation results in a score of 0 on the lab.
Please contact a staff member if you are unsure as to whether you're allowed to use something.
You do not need to write tests for any hashCode implementations. We will check these manually.
Important Warning 1: You must write the method headers for all methods that we list below in order for your code to compile in the autograder. We will not award partial points for non-compiling code. So, we strongly recommend that, before you implement the methods, you first write the method headers and Javadocs.
In this question you will implement the MiniStack data structure. This is similar to the MiniArrayList class from the chapter, but, of course, is a stack and not an array list.
Unlike many stack implementations, however, we will use an array-backed stack. This means that, instead of using a collection of private and static Node classes, the stack will use an array to store its elements. When the array runs out of space, a new one is allocated and the elements are copied over.
If you use a node-based stack implementation, you will automatically receive a 0.
(10 points)
First, design the generic MiniStack class.
Its constructor should receive no arguments, and instantiate two instance variables: T[] elements and size to a new array and zero respectively.
Remember that you cannot instantiate a generic array, so how do we do that?
The initial capacity of the array should be set to INITIAL_CAPACITY, which is a private static final variable declared in the class as 10.
Hint: Remember how we did this during lecture!
Warning: Do not use System.arraycopy, even if IntelliJ prompts you to use it. You must do the copying yourself.
If you use System.arraycopy or any other means of copying the array that is built-in, you will receive an automatic 0.
(40 points) Second, design the void add(T t) method, which adds an element onto the top of the stack.
The "top of the stack," when using an array, is the right-most element, i.e., the element with the highest index.
It might be a good idea to design a helper method that resizes the underlying array when it runs out of space.
Your resize factor, i.e., by what factor you resize the underlying array, is up to you to decide.
(10 points) Design the Optional<T> peek() method, which returns the top element of the stack, wrapped in an Optional, without removing it. If the stack is empty, return an empty Optional.
(10 points) Design the Optional<T> pop() method, which removes and returns the top element of the stack, wrapped in an Optional. If the stack is empty, return an empty Optional.
(10 points) Design the int size() method, which returns the number of logical elements in the stack.
(20 points) Override the public String toString() method to return a sring containing the elements of the stack from top-to-bottom, separated by commas and a space. For example, if the stack contains, from bottom-to-top, 10, 20, 30, 40, and 50, then toString() returns "50, 40, 30, 20, 10.".
Hint: Remember that your stack contains generic objects of type T, so how can you get that type's toString() implementation?
Warning: In this problem, you should use StringBuilder to avoid a timeout in the autograder when repeatedly concatenating strings.
Files to Submit:
MiniStack.java, MiniStackTest.java