4. (37 pts) Implement a generic class StackReorder to reorder the contents of an existing stack. The class provides a method keyOnTop(), which takes as input a stack stk and a value key. The value key and the elements on the stack stk are objects of the class E, whose superclass (possibly itself) implements the Comparable interface. After execution, the stack stk will have been reorganized to satisfy the following conditions a) all the elements on stk that are equal to key (as determined according to the implementation of Comparable) will appear above those elements that are not equal to key; b) all the elements equal to key will preserve their relative order on the stack before the method cal; c) all the elements not equal to key will also preserve their relative order before the call. On the left of the figure below shows that the input stack stk stores seven String objects. Two of the objects "man' s" are equal, but displayed in different font sizes for distinguishing purpose. An object named reorder of the class StackReorder invokes the call keyOnTop (stk, "man' s"). The post- call contents of the stack are displayed on the right below, with the two man's" on the top (and the one displayed in a larger font still above the other in a smaller font) and the remaining String objects below them with their original order unaltered top man' s one man's man's one reorder.keyOnTop(stk, "man's" is constant another 1s man s another variable variable stk stk (after the call) (before the call) If the value of key does not appear on the stack, then the stack is not changed after the call For the same stack stk on the left of the above figure, a call reorder.keyOnTop(stk, "procedure") would result in no change to stk. You are asked to implement the class StackReorder, which makes use of the classes PureStack and ArrayBasedStack discussed in class and implemented in Appendix B. The method keyOnTop) will make use of a stack and a singly linked list, which is an object of the private class SimpleList that you also need to implement. Please carefully read the javadocs before each method and between the lines, and follow their instructions in your implementation. 4. (37 pts) Implement a generic class StackReorder to reorder the contents of an existing stack. The class provides a method keyOnTop(), which takes as input a stack stk and a value key. The value key and the elements on the stack stk are objects of the class E, whose superclass (possibly itself) implements the Comparable interface. After execution, the stack stk will have been reorganized to satisfy the following conditions a) all the elements on stk that are equal to key (as determined according to the implementation of Comparable) will appear above those elements that are not equal to key; b) all the elements equal to key will preserve their relative order on the stack before the method cal; c) all the elements not equal to key will also preserve their relative order before the call. On the left of the figure below shows that the input stack stk stores seven String objects. Two of the objects "man' s" are equal, but displayed in different font sizes for distinguishing purpose. An object named reorder of the class StackReorder invokes the call keyOnTop (stk, "man' s"). The post- call contents of the stack are displayed on the right below, with the two man's" on the top (and the one displayed in a larger font still above the other in a smaller font) and the remaining String objects below them with their original order unaltered top man' s one man's man's one reorder.keyOnTop(stk, "man's" is constant another 1s man s another variable variable stk stk (after the call) (before the call) If the value of key does not appear on the stack, then the stack is not changed after the call For the same stack stk on the left of the above figure, a call reorder.keyOnTop(stk, "procedure") would result in no change to stk. You are asked to implement the class StackReorder, which makes use of the classes PureStack and ArrayBasedStack discussed in class and implemented in Appendix B. The method keyOnTop) will make use of a stack and a singly linked list, which is an object of the private class SimpleList that you also need to implement. Please carefully read the javadocs before each method and between the lines, and follow their instructions in your implementation
