Homework: Stack Implementation with Singly-Linked List

This homework is necessary preparation for the lab. Make sure you type your answers in files you bring to the lab so that you will not have to waste time entering your code during the lab.

1. Carefully review the Queue2 implementation of Queue kernel represented as a singly-linked list of Nodes. In particular, look at the representation fields (and the convention and correspondence) and the code in createNewRep and the constructor, and draw a picture (in the style used in the Linked Data Structures slides) of the Queue2 representation right after the constructor is executed.

2. Carefully review the Stack2 skeleton of Stack kernel represented as a singly-linked list of Nodes. In particular, look at the representation fields and the convention and correspondence, and draw a picture (in the style used in the Linked Data Structures slides) of the representation a Stack2 object should have right after the constructor is executed.

3. Complete the implementation of the Stack kernel represented as a singly-linked list of Nodes in the skeleton provided, Stack2. You need to write bodies for the private method createNewRep and for the kernel methods push, pop, and length.

   Note that although the Stack2 implementation is similar to the Queue2 implementation, there are two significant differences: (1) the Queue2 representation has three fields (instance variables): preFront, rear, and length, while Stack2 only has two fields: top and length; (2) the singly-linked list representing Queue2 has one extra "smart" node at the front of the list, while the singly-linked list representing Stack2 does not include this extra node.

4. Develop a complete test plan for the Stack2 constructor and kernel methods you implemented and enter them in StackTest.

For the homework, turn in the pictures (can be hand-drawn) and the printouts of the completed Stack2.java and StackTest.java files.