Linked List Solution:

Class Palindrome:

Sample driver class:

public class Palindrome {

public static void main(String[ ] args) {

Scanner input = new Scanner(System.in); String inputString; System.out.print("Enter Your input string expression : ");

inputString = input.next( ); if (isPalindrome( inputString.toLowerCase())){

System.out.println("That is a palindrome.");else{

System.out.println("That is not a palindrome.");

} }

public static boolean isPalindrome(String input) {

LinkedQueue q = new LinkedQueue( );//TwoPartCircularLinkedQueue q = new TwoPartCircularLinkedQueue( );

LinkedStack s = new LinkedStack( );char letter; int i;

for (i = 0; i < input.length( ); i++) {

 letter = input.charAt(i); q.enqueue(letter); s.push(letter); 

} while (!q.isEmpty( )) {

if (q.dequeue( ) != s.pop( ))return false;

} return true;

} }

public class Palindrome

main(String[ ] args) isPalindrome(String input)

Page | 5

}

? Class LinkedQueue:

public final class LinkedQueue implements QueueInterface

private Node firstNode private Node lastNode

public LinkedQueue() public void enqueue(T newEntry) public T getFront() public T dequeue() public boolean isEmpty() public void clear() private class Node

? Inner class Node

private class Node

private T dataprivate 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 LinkedStack implements StackInterface

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

? Inner class Node

private class Node

private T dataprivate 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)

Page | 6

? Interface QueueInterface:

public interface QueueInterface

public void enqueue(T newEntry) public T dequeue() public T getFront(); public boolean isEmpty();

public void clear();

? Interface StackInterface

public interface StackInterface

public void push(T newEntry); public T pop(); public T peek(); public boolean isEmpty(); public void clear();

? Class EmptyQueueException:

public class EmptyQueueException extends RuntimeException {

public EmptyQueueException() {

this(null); } // end default constructor

public EmptyQueueException(String message) {

super(message); } // end constructor

} // end EmptyQueueException 

public class EmptyQueueException extends RuntimeException

public EmptyQueueException() public EmptyQueueException(String message)

Page | 7

? Class EmptyStackException:

public class EmptyStackException extends RuntimeException

public EmptyStackException () public EmptyStackException (String message)

public class EmptyStackException extends RuntimeException {

public EmptyStackException() {

this(null); } // end default constructor

public EmptyStackException(String message) {

super(message); } // end constructor

} // end EmptyStackException 

? Class Two Part Circular Linked Queue

public final class TwoPartCircularLinkedQueue implements QueueInterface

private Node queueNode private Node freeNode

public TwoPartCircularLinkedQueue()public void enqueue(T newEntry)public T getFront() public T dequeue()

public boolean isEmpty() public void clear() private boolean isChainFull()private class Node

? Inner class Node

private class Node

private T dataprivate 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)

Page | 8