Due Tuesday, 25 September
What to hand in: We expect to ask you to submit this program electronically, so there will be no need to print out anything. We will give details later.
Purpose of assignment: Give you practice with interfaces and exceptions. Also, deal with stacks and queues.
Interface List211. File List211.java (get this file from the course website) is an interface for dealing with lists --sequences of Objects. It defines methods for making a list empty, adding an item to the list, deleting an item from the list, obtaining the number of items in the list, and obtaining the first item on the list. However, the method for adding an item does not say WHERE to add it, the method for deleting an item does not say WHICH item to delete, and the method for obtaining an item does not say WHICH item to obtain.
Task A. Your first task is to implement a class, named StackArray, that implements interface List211. Each instance of StackArray is a list that acts like a stack. A stack has a top and a bottom, and
1. An instance of StackArray should maintain the stack in an array of base type Object. This means that there will be a limit on the number of items that can be in the stack at any one time. Declare in the class a public, static, final, int variable that will contain the maximum number of items in the list. Initialize it to 10. Use this variable as the size of the array when creating the array. (All nonstatic variables of the class should be private.)
2. A user may attempt to put too many elements in the stack. If this happens, method add should throw a FullListException. This class is given in file FullListException.java (get it from the course website).
3. A user may attempt to delete an item from an empty list or obtain an item from an empty list. In either case, an EmptyListException should be thrown. You write this class; use class FullListException as an example. The message in such a thrown exception can should indicate what the problem was --deleting from an empty list or obtaining an item from an empty list.
4. Class StackArray should have a constructor with no parameters; which initializes the stack to contain 0 items.
5. Class StackArray should define method toString, which should produce a String that contains the items of this stack, with the top item first and the bottom item last, and with "\n" between adjacent items.
6. The class and each method MUST have an accompanying specification in the form of a javadoc comment. We will use javadoc to extract the specification, and we MUST be able to understand clearly what each method does from this specification. Before you submit your assignment, you should get your javadoc specification and study it to make sure that all methods can be understood from just the specification. For example, they should not mention private variables of the class, since they are not part of the specification.
7. Important. Before proceeding to the next task, test class StackArray throughly!!! Exercise each method in the class with enough test cases tsos that you KNOW the method is correct. We will run a program that tests this class throughly, including testing the throwing of exceptions. We expect it to be 100% correct. It is not difficult to get this right; it just takes careful thinking and good testing.
To test throwing a FullListException in method add, your main program can include a try statement that has as its body a loop that attempts to add too many items to the stack; the catch clause should simply print the exception. This will let you see how exceptions are printed. You can also, if you wish, print the call stack that is in the exception, using method printStackTrace of the exception.
Task B. Implementing a stack in an array limits the size of the stack to some value that is fixed when the array is first created. We can get around this problem by implementing the stack in a Vector --this class is defined in package java.util. At the end of this assignment, we briefly describe useful methods of class Vector.
Write a class StackVector that does this, still implementing interface List211. One way to create this class is to make a copy of file StackArray.java, name it StackVector.java, and modify StackVector.java. You won't need the static variable. Method add will not have to throw an exception, but methods getItem and delete will still have to test for an empty stack and throw an exception if necessary.
Test this class exhaustively, as you did the class StackArray. You can probably run exactly the same test cases; instead of creating an instance of StackArray to play with, make it an instance of StackVector.
Important. Before proceeding to the next task, test this class throughly!!!
Task C. A queue is a list of items with a front end and a back end; items can be deleted from the front and added to the back, and the only item that can be accessed (obtained) is the item at the front. The British stand in queues; Americans stand in lines. You stood in a queue at Barton Hall during registration a few weeks ago.
Write a class QueueVector whose instances are queues --it should still implement interface List211. Probably, the best way to do this is to make a copy of file StackVector.java, name it QueueVector.java, and then modify it. Don't forget to modify all comments. As to the code, you probably have to change only methods add, delete, and getItem.
Test this class exhaustively, as you did the other two. You can probably run exactly the same test cases; instead of creating an instance of StackVector to play with, make it an instance of QueueVector.
Discussion. This assignment created three classes, but didn't require you to use them (except to test them). The nice thing about having interface List211 is that we can now write methods like the one below, which process or use ANY object of this interface. Try calling this method with instances of the three classes that you wrote.
// Use list l in doing some task
public static void process(List211 l) {
l.makeEmpty();
for (int i= 1; i != 6; i=
i+1) {
l.add(new Integer(i));
}
System.out.println(l);
}
Class java.util.Vector. An instance of this class contains an array of variable size. There is no maximum size. Vector has more methods than the ones defined below; these are the only ones that you need for this assignment.
public Vector(): Constructor: a Vector with 0 elements
public String toString(): = a String representation of this Vector (try it and see what you get)
public int size(): = the number of elements in this Vector
public boolean isEmpty(): = "This Vector has no elements"
public Object elementAt(int i): = Element i. If !(0 < i < size()), throw a ArrayIndexOutOfBoundsException.
public Object firstElement(): = First element in this Vector. If it has no elements, throw a NoSuchElementException.
public Object lastElement(): = Last element in this Vector. If it has no elements, throw a NoSuchElementException.
public void setElementAt(Object obj, int i): Set element i to obj. If !(0 < i < size()), throw a ArrayIndexOutOfBoundsException.
public void addElement(Object obj): Append obj: obj becomes element number size() and size() is increased by 1.
public void removeElementAt(int i): Remove element i. The elements previously numbered i+1, i+2, ..., are now numbered i, i+1, ..., and size() is 1 less. If !(0 < i < size()), exception ArrayIndexOutOfBoundsException is thrown.
public void removeAllElements(): Throw away all elements, so that size()
= 0