It is often the case that new data structures are written using other existing data structures as an underlying model. In this practice exercise we will be creating a Stack class using Java’s ArrayList as a basis for our new class.
A Stack data structure behaves similarly to a stack of papers. There are restrictions on adding or removing papers from the stack:
1. You may only add papers to the top of a stack, referred to as a “push” operation.
2. You may only remove papers from the top of a stack, referred to as a “pop” operation.
3. You may also view the paper on top of the stack, referred to as a “peek” operation. This does not remove the top paper.
4. You cannot access papers below the top paper on your stack
Because of these restrictions, a Stack data type is referred to as a LIFO structure (last-in-first-out).
Note: because we only allow access to elements at the top of a Stack, this removes the index-based access of structures such as Arrays and ArrayLists
Write a new Stack class using an ArrayList as the underlying storage structure (in other words, a private instance field). You can simulate the behavior described above by adding/removing items from one side of your ArrayList. Which side to use is up to you, but I would suggest analyzing which side of an ArrayList is best to use.
Use the following class diagram as a basis for your class:
– data : ArrayList<T>
+ pop() : T
+ push(newElement : T) : void
+ peek() : T
+ isEmpty() : boolean
+ size() : int
Note: your Stack<T> class should throw an appropriate exception when pop() is called on an empty Stack.
Write a driver class to show that your Stack class is working correctly.
Challenge: create a new class called BoundedStack that enforces a maximum number of elements in your stack.
1. Use the code from your Stack class as a starting point in your new BoundedStack class
2. Include only a parameterized constructor that takes a positive integer that specifies the maximum number of elements in your bounded stack
3. Throw an appropriate exception if you stack size exceeds the bounds given