If you can't read something or need clarification comment blow.

import

java.util.NoSuchElementException;

/

/

This class is parametrized with the type

E

, whose superclass must have implemented

// Comparable.

Fill a wildcard type in the blank below

to make comparison possible

//

between two

objects of type E.

public

class

StackReorder

___________________________

______________________

_>

// 5

pts

{

/**

* Search for all the elements on a stack that are equal to key. Reorder

* the stack such that these elements are on the top while preserving their

* original order. The remaining elements not equal to ke

y must preserve

* their original order as well.

*

*

@param

stk

*

@param

key

*/

public

void

keyOnTop(PureStack stk, E key)

{

// initialize

// a) a stack as an object of the

ArrayBased

Stack class;

// b) a list as an object of

the

inner

SimpleList

class

.

//

//

fill in the blanks

on the right hand sides of the next two assignments.

PureStack tempStk =

______________________________________

_

_

;

//

(

1

pt

)

SimpleList tempList =

__________

___________________________

___

_

;

//

(

1

pt

)

//

perform a loop to

store

// a) elements from the stack

stk

equal to key on the stack tempStk,

// b) other elements from the stack in the list tempList.

//

//

insert code below

(6

pts

)

// merge elements from tempStk and tempList onto the stack

stk

.

//

//

insert code below

(6 pts)

}

// singly

-

li

nked list for temporary storage

private

class

SimpleList

{

private

Node head;

private

int

si

ze;

/**

* default constructor

*/

public

SimpleList()

{

//

insert code below

(3

pts

)

}

/**

* Create a new node to contain a provide item. Insert the node to the

* front of the list.

*

*

@param

item t

o be added

*/

void

add(E item)

{

//

insert code below

(4

pts

)

}

/**

*

Remove the first node.

*

*

@return

data stored in the removed node if the list is not empty

* @throws

IllegalStateException if the list is em

pty

*/

E remove()

throws

IllegalStateException

{

// check if the

list

is empty.

//

fill in the blank below

(1 pt)

if

(

__________________________

)

{

//

insert code below

(2

pts

)

}

// size != 0

//

insert code below

(6

pts

)

}

/**

*

*

@return

true if the list is empty

*/

boolean

isEmpty()

{

//

insert code below

(2

pts

)

}

// fully implemented class

public

class

Node

{

public

E data;

public

Node next;

Node(E data)

{

this

.data = data;

}

}

}

}

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 stkand 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 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 call; 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 "mans 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 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 top man's man S constant reorderkeyOnTopistk, "mams) constant another is man's another variable variable stk stk hefore the call (after 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 stkand 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 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 call; 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 "mans 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 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 top man's man S constant reorderkeyOnTopistk, "mams) constant another is man's another variable variable stk stk hefore the call (after 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