Linked Stack

In this lab, we'll work with the linked stack implementation, and add some extended operations intended mainly as an exercise with linked structures.

Procedure

1. Download and unpack the starting code
2. The files EmptyCollectionException.java, LinearNode.java, LinkedStack.java and StackADT.java are as described in the online notes (with some trivial tweaks). LinkedStack.java contains a complete linked implementation of the StackADT interface from your text. The StackADTExtended.java contains some extension methods (see below), and there are several testing files.
3. Compile all the files. They should compile without problem.
4. Run the program StackTest. It should report no errors.
5. One important change to the LinkedStack.java, compared to the original, is that implements an extra interface called StackADTExtended. It contains three extensions (additional methods) which must be implemented: an indexed peek allowing any item to be returned, pushother and swaptop. These methods are stubbed in the LinkedStack class so that it will compile, but need to be implemented. That's what we do in this lab. The required behavior of each one is documented in comments in the LinkedStack.java file.

   None of these methods should be implemented using the push and pop calls. Instead, implement them by directly manipulating the linked list structure. (As methods, they have access to private fields.)

6. Implement the indexed peek method. It takes an integer index which specifies which item to peek by giving the distance from the top item. (Calling it with zero is the same as regular peek.) If the index is out of bounds (too large or negative), it throws ElementNotFoundException.

   Implement this by writing a loop that scans through the list until the correct item is found, and return it. If you reach the end, throw the exception.

7. Compile LinkedStack.java and fix any errors. Run the program ExtendedStackTest.java. You will have some errors, since you have not implemented all the methods. But the tester tests each of the extension methods in turn, and gives a message announcing the start of each test section, so you should be able to see the message announcing the testing of indexed peek, and that section should complete without errors. (The next message should be the one announcing the swaptop tests.) Fix any errors found for indexed peek.

8. Implement the swaptop method. This simply exchanges the top two items, if they exist. If the stack is empty or has only one item, the method does nothing. Implement it by rearranging the links in the stack; do not try to use the pop or push methods in your implementation.
   

9. Compile LinkedStack.java and fix any errors. Run the program ExtendedStackTest.java. The tester should complete the swaptop tests without detecting any errors.

10. Implement the pushother method. This takes a stack as argument, and pushes its content on the front, so that the order is not changed. The argument stack is emptied; its contents are added to the stack running the method.

    1. stack1 contains 1 2 3 4 5, where 1 is the top and 5 the bottom.
    2. stack2 contains -10 -9 -8 -7, where -10 is the top and -7 the bottom.
    3. After stack1.pushother(stack2), Stack2 is empty, and stack1 contains -10 -9 -8 -7 1 2 3 4 5, with -10 on top.
    You must implement pushother without using the standard push and pop operations, but by manipulating the pointers. In essence, stack1.pushother(stack2) must make the changes in red:
    
    You must write a loop to scan through stack2 to find its last node, and link it to the head node of stack1. Then change stack1 to point to the head stack2, and empty stack2. You may need to treat specially cases where either list is initially empty. Also, be careful to update the count variable that holds the current size.

    Please note: The argument to pushother is declared ExtendedStackADT. You will need to cast it to LinkedStack before you can operate on it. The Java compiler may issue a warning for this cast. Unfortunately, Java doesn't have any way (that I could find) to declare in the StackADTExtended interface that the parameter needs to be implemented by the same class as the underlying object.

11. Compile LinkedStack.java and fix any errors. Run the program ExtendedStackTest.java. You should not see any error reports for the pushother test.

12. Please submit your LinkedStack.java file, containing the completed stack methods and the extended methods. If not all your methods work, make sure you program compiles anyway, and I can give you credit for what does work.