Please use JAVA solve this problem. Array is not allow to use in this assignment.

The purpose of this assignment is to familiarize you with stacks and queues. The assignment is split into 2 tasks.

The first part of the assignment is to take the Node, Stack, and Queue files and implement them (IE fill in the methods). Do not extend your class. References are to be singly linked.

Part two requires you to create another class to implement a Palindrome detector that uses a Stack and a Queue. It must fulfill the following requirements: 1. The program must loop to take input from the user. The input is a single word. If the word is quit, go to step 4. Otherwise we look to see if the input is an Palindrome (lowercase and uppercase are considered the same letter) 2. It must use both the Stack and the Queue you just wrote to detect Palindromes. 3. Output whether or not the inputed string is an Palindrome. 4. Once the user types quit, print out all the detected Palindromes in reverse order, then terminate. Use the proper data structure. 5. You cannot use array

Rather than detecting if a word is a palindrome, instead tell me if an entire String is a palindrome. An entire String is a palindrome iff the string reads the same backwards to forwards, ignoring capitalization and punctuation. , the following line should be detected as a Palindrome.

"Go hang a salami, Im a lasagna hog"