Using stacks (LinkedStack and ArrayStack data structures) and queues (LinkedQueueandArrayQueue da... 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. Also, don't copy the answer from another chegg question cause i already look at it and I Will know(they are different)!!!

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.") public static boolean isPalindrome(String input) LinkedQueue Character q new LinkedQueue( ); = / /TwoPartcircularLinkedQueue q-new TwoPartcircularLinkedQueue 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 Stack!nterfaceT> 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 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.") public static boolean isPalindrome(String input) LinkedQueue Character q new LinkedQueue( ); = / /TwoPartcircularLinkedQueue q-new TwoPartcircularLinkedQueue 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 Stack!nterfaceT> 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