Using stacks (LinkedStack and ArrayStack data structures) and queues (LinkedQueueandArrayQueue data structures), write a program that will tell if an input string is a palindrome.A palindrome is a phrase that reads the same from both ends. (Write this in java) Please Followed the structure below and use Java to write the program.

ex.Mom

Madam

2- Linked List Solution: Class Palindrome: public class Palindrome main(String ] args) isPalindrome(String input) Sample driver class: public class Palindrome public static void main(Stringl args) scanner input new scanner(System.in); String inputstring; System.out.print("Enter Your input string expression:") inputstring-input.next): if (isPalindrome( inputString.toLowerCase())) else( System.out.println("That is a palindrome.") System.out.printin("That is not a palindrome.") Class LinkedQueue: public final class LinkedQueue implements Queuelnterface private Node firstNode private Node lastNode public LinkedQueue() public void enqueue(T newEntry) public T getFront() public T dequeue() public boolean isEmpty0) public void clear() private class Node o Inner class Node private class Node private T data private Node next private Node(T dataPortion) private Node(T dataPortion, Node linkPortion) private T getData() private void setData(T newData) private Node getNextNode() private void setNextNode(Node nextNode) Class LinkedStack: public final class LinkedStackT> implements StackInterfaceT> private Node topNode public LinkedStack() public void push(T newEntry) public T peek() public T pop() public boolean isEmpty() public void clear() private class Node o Inner class Node private class Node private T data private Node next private Node(T dataPortion) private Node(T dataPortion, Node linkPortion) private T getData() private void setData(T newData) private Node getNextNode() private void setNextNode(Node nextNode) Interface Queuelnterface: public interface Queuelnterface public void enqueue(T newEntry) public T dequeue() public T getFront(); public boolean isEmpty(); public void clear(); Interface Stacklnterface public interface Stacklnterface public void push(T newEntry); public T pop0 public T peek(); public boolean isEmpty); public void clear(); . Class EmptyQueueException: public class EmptyQueueException extends RuntimeException public EmptyQueueException() public EmptyQueueException/(String message) public class EmptyQueueException extends RuntimeException public EmptyQueueException() this(nul1); // end default constructor public EmptyQueueException (String message) super (message); } // end constructor I/ end EmptyQueueException