Write a subclass of Stack with slightly different behavior and use it in a simple program.
Text: 3.1, Java review.
Concepts: inheritance, overriding, polymorphism; interfaces; stacks.
In this A06 assignment, you will practice a number of different Java concepts by building different reusable classes. You will use some of those classes here, and then you will reuse them in a simulation program in A06b.
In lecture, we discussed a generic Node and node-based Stack implementation:
You will need both of these files, but do not change them.
You will now author a special kind of stack called a PyramidStack. A pyramid stack requires that each item pushed onto the stack must be of the same size or smaller than the current top item. (This is not a standard or common data structure, by the way. It will be useful for A06b, though.)
Since most of the behavior is otherwise the same as Stack, you will implement the PyramidStack by sub-classing Stack. You will inherit the peek, pop, and size methods, but you will override the push method. If someone tries to push an item that is larger than the current top element of the stack, the push method should throw an IllegalArgumentException. (This exception is in java.lang, and so it does not need to be imported.) Since the pushed items will need to be comparable to each other, a PyramidStack should only take Comparable items.
Also, it would be handy to print out the contents of a stack. Write a toString() method in PyramidStack to return a representation of the stack's current contents. This String representation should be on one line, showing the stack elements from bottom to top as you read the line left-to-right. Additional formatting, such as commas between elements or [brackets] around the whole string, is up to you.
Write a method named countLessThan that returns the number of items in the stack that are smaller than the given item. This essentially tells you how many pop operations you would need to perform before you could safely push the given item. If the stack is empty, this method should return 0.
Therefore, create the following class:
public class PyramidStack<E extends Comparable<E>> extends Stack<E> {
@Override
public void push(E item) throws IllegalArgumentException { ... }
@Override
public String toString() { ... }
public int countLessThan(E item) { ... }
}
You may write additional methods if you like.
You should now be able to create a PyramidStack and push and pop its contents. You should be able to create a new PyramidStack that handles any specific Comparable: Strings, Integers, Doubles, etc.
Write a main method that prompts the user to enter Strings. For each String, save it if it is "less than or equal to" all the other strings the user has entered so far. Use the normal compareTo behavior to determine String ordering. This is by character-encoding order, which is basically alphabetically with capitals before lowercase. (In other words, just use your PyramidStack to store all of the entered strings that the stack will accept.)
Let the user know whether you saved each input or not. You may explain the rules behind saving a String to the user or not, as you choose. If you explain the rules, you might call countLessThan when you refuse to a save a string in order to explain how many of the saved Strings are smaller than the given value.
If the user enters nothing (that is, just hits enter), end the program and print all the Strings you saved on one line in the order that you saved them.
This program will save some of the strings you enter. Enter a string: hi there String saved. Enter a string: thanks String NOT saved. Enter a string: save all my strings! String NOT saved. Enter a string: Lousy program String saved. Enter a string: I'm leaving String saved. Enter a string: quit String NOT saved. Enter a string: Bye String saved. Enter a string: Saved 4 strings: hi there, Lousy program, I'm leaving, Bye
Create a .jar file named UsernameA06a.jar. This should include:
Upload your UsernameA06a.jar to Tamarin.
Remember to follow the course coding standards on all assignments.
This assignment involves the following concepts.
this.top and the methods in PyramidStack as if they were defined in PyramidStack. This lets you reuse that Stack code in PyramidStack without rewriting it.
You will then change the normal push behavior of Stack by overriding that method. Remember that you can still call the original version of any of the superclass's methods from within PyramidStack, such as by using super.push(item);
The @Override annotations are optional. They just tell the compiler that you are trying to override a method in a superclass or implement a method specified by an interface. This annotation prevents common programmer errors, such as using the wrong signature or misspelling the method name.
In your main method, you can do this:
Stack<String> stack = new PyramidStack<String>();
Although you're using a Stack variable here, the object it contains will still have PyramidStack behavior thanks to polymorphism.
Note that you could easily and significantly change the behavior of your program simply by changing the right side of this line from new PyramidStack<String>(); to new Stack<String>();. The program would then store all entered lines. (It would also break the final output, though, because Stack doesn't provide a useful toString() method.)
PyramidStack<E extends Comparable<E>>? Why is there an extends in the generics part?
If we just used PyramidStack<E> here, a PyramidStack would take any kind of object (like the original Stack<E>). That won't work for us, though, since we need to be able to call compareTo on any pushed element.
If we just used PyramidStack<Comparable<E>>, it would fail to compile for a number of reasons. The main reason is that we have not declared E properly here. But even if this did compile, it means we'd only take Comparable objects. This is a problem for two reasons. First, while we might have Comparable variables, there are no "pure" Comparable objects in the heap. Comparable is an interface, so any implementation must be undertaken by a different class. Any instances of those implementing classes (such as String or Integer) would be something other than Comparable instances. Secondly, even if we could overcome that by creating Comparable instance directly, this signature means we would take only Comparable objects, but not any subclasses, such as Integers, Strings, etc.
So we use PyramidStack<E extends Comparable<E>>, which means we'll take any instance of class Comparable (if there were any) or any class that implements Comparable or any subclass of one of those implementing classes.
left.compareTo(right) <= 0means left is less than or equal to (smaller or same size as) right.
So, with Integers, this would be by value, with 5 being smaller than 8. Strings are sorted alphabetically... sort of. They actually go by character position in the character encoding, so usually capitals come before lowercase letters. So "catastrophe" would be "smaller" ("less than", "come before") than "dog". (I guess that is a little confusing to user "smaller" with Strings, rather than "less than".)
When writing your PyramidStack, just use the compareTo method of whatever item is pushed onto the stack and you'll be fine.
There are a number of different options you might consider here.
One is to use a temporary local data structure, such as ArrayList or a regular Stack. You could pop all the elements off into an extra Stack, then add them to a String as you pop them off the extra stack and push them back into the original stack again. So this is sort of like pouring tennis balls from one tube to another and then back into the original tube again. As they go back into the original tube, they'll go past you in the order you need. And when you're done, the original tube is in the same state you started with.
Or, rather than all that pushing and popping, you could work at a lower level by looping through the Nodes, adding the data elements to a separate array, ArrayList, or stack and then build the String from that other data structure.
That's all rather heavy-handed though. A much more elegant solution would be to use recursion in a private helper method. If you process the linked list of nodes recursively, you could then append their data to a returned string as you return from the calls... which will give you the order you want with only a few lines of code and no extra data structures required.
countLessThan method in main.
Stack<String> st = new PyramidStack<String>();then, thanks to polymorphism, your
st looks like a Stack but it behaves like a PyramidStack. That can be very handy in certain situations.
However, the flip side of this is that you can only call Stack methods on st because it is a Stack variable. countLessThan is not a Stack method. If you want to call PyramidStack methods (behaviors), then you need to use a PyramidStack variable:
PyramidStack<String> st = new PyramidStack<String>();