Lab 19: Stacks of Stuff
Intro
You’ll work in this lab with your lab partners.
The two of you will work as a team to solve problems. At any time, one of you will be the Head and the other will be the Hands. The Head does the thinking and the Hands does the typing. Hands type only what the Head tells them to, but you’re free to discuss any issues that pop up. You should switch off during the lab to make sure each of you get practice problem solving, dealing with syntax, and getting finger exercises on the keyboard.
You can start this lab with this project skeleton.
A Simple Stack
A stack is a simple data structure much like a list. We can push new elements on to the top of the stack and we can pop the top element off of the stack (if it exists). Note that these operations mutate the underlying data structure, so once we’ve popped an element off the stack, it remains off of the stack.
IStackof<String> stack = new Stackof<>(); |
stack.height(); // => 0 |
stack.push("foo"); |
stack.height(); // => 1 |
stack.push("bar"); |
stack.height(); // => 2 |
stack.pop(); // => Optional.of("bar") |
stack.pop(); // => Optional.of("foo") |
stack.pop(); // => Optional.empty() |
stack.height(); // => 0 |
The file Stackof.java has a skeleton of a stack implementation. It also contains a simple Listof implementation which should not need to be modified.
Ex 1: Implement the core, effectful operations push and pop for Stack. Note: some of the tests that confirm the height of the stack will fail until you finish exercises 2 and 3, but the tests that call get and isPresent should pass.
Ex 2: Implement Stackof.foldr. You should delegate this operation to the underlying list.
Ex 3: Implement Stackof.height using Stackof.foldr. All the stack tests should pass.
Stack with Constraints
We can add constraints about what kinds of elements may be pushed on top of the stack. Recall the interface Comparable<T>, which allows data to compare itself to data of the same kind.
Integers implement comparable as <:
1.compareTo(2) // => -1 |
10.compareTo(-1) // => 1 |
42.compareTo(42) // => 0 |
We can make an extension of the stack data structure that only allows elements smaller than the top element (i.e. where the new element compares to the top element as -1). For integers that means smaller values must be pushed on to larger values.
Ex 4: Implement class OrdStackof<X extends Comparable<X>> extends Stackof<X>. You should only need to override the method push from the original stack. It should only allow values smaller than the top to be pushed on top of the stack, and simply not push any other elements.
Ex 5: Implement any non-trivial class that implements Comparable (e.g. a person with a name in alphabetical order). Write a test similar to testOrdPushPop to confirm that the order is respected by OrdStackof.