Write four methods that will return a LinkedList, Stack, Queue, and PriorityQueue containing the following poem. Each word is an element in the LinkedList, Stack, Queue, and PriorityQueue.

Hickory, dickory, dock. The mouse ran up the clock. The clock struck one and down he runs. Hickory, dickory, dock.

The header of each method is:

public static LinkedList createLLPoem() public static Stack createStackPoem() public static Queue createQueuePoem() public static PriorityQueue createPriorityQueuePoem() Inside of the above methods, you can hard code the values being inserted into each of the structures.

Then, write 4 methods that will return an int with the number of times that a word occurred in the linked list, queue, and stack. Before leaving each method, restore the structure that was passed, if it was destroyed in the process of reading it. The headers of these methods are:

public static int count(LinkedList theList, String word)

public static int count(Stack theStack, String word) public static int count(Queue theQueue, String word)

public static int count(PriorityQueue thePriorityQueue, String word)

The above methods will sometimes destroy the structure as they are searching for the word.Therefore, you should recreate the structure programmatically (not hard coding the values as you did in the create- method).

Within main:

Call the following 4 methods:

LinkedList theList = createLLPoem(); Stack theStack = createStackPoem(); Queue theQueue = createQueuePoem();

PriorityQueue thePriorityQueue = createPriorityQueuePoem();

Print theList, theStack, theQueue, thePriorityQueue: System.out.println(Before..);

System.out.println(theStack);

Ask the user to enter any word in the poem, and store it in a String variable named aWord.

Call each of the following methods:

int countLL = count(theList, aWord);

int countStack = count(theStack, aWord);

int countQueue = count(theQueue, aWord);

int countPriorityQueue = count(thePriorityQueue, aWord);

Display a message of how many times aWord occurred in theList, theStack, theQueue, & the PriorityQueue.

Repeat step b.) re-print the list, stack, queue, and priorityQueue, preceded by the title After.

Extra Credit: 25 points:

Pass each of the 4 data structures to a method that will print each structure according to how you would iterate through it, in that order.You should get the poem exactly in the correct order, except for the Priority Queue which will order the words in alphabetical order.