1. Write an efficient implementation for a class ArrayStack that uses an array to hold the stack elements. To make this a bit more interesting, use an implementation that grows the stack t from the right-hand end of the array stackItems – that is, from stackItems.length-1 “backwards” to the left, as shown in the diagram below (the shaded portion of the array contains the stack items). Before you implement the array-based, carefully consider whether to put the top at beginningIndex or listItems.length-1. (How will each choice affect the time complexities of push and pop?)
2. Write and efficient implementation for a class LinkedListStack that uses a linked list to hold the stack elements. To make this a bit more interesting, use an empty header node before the first content node.
For both the array and linked-list implementations of the stack ADT, make sure that your implementation conforms to the requirements (including pre- and post-conditions) spelled out in the StackInterface that I have provided.
3. Write a class TowersOfHanoiPlayerWithStack that implements the TowersOfHanoiPlayer interface that I have provided. Like the FactorialCalculatorWithStack class, it should contain an inner class ActivationRecord that simulates an activation record for the recursive method in the class RecursiveTowersOfHanoi. Implement the method playTowersOfHanoi non-recursively using a stack of objects in the ActivationRecord class. (I have provided a class BadArrayStack that implements the Stack interface so that you can test your method before you provide your own – more efficient – implementations of the stack ADT.)