Java- Data Structures question

Using stacks (LinkedStack and ArrayStack data structures) and queues (LinkedQueue and ArrayQueue 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.

ex.

Mom

Madam

Data Abstraction and Structure – CIS 22C
Midterm
Using stacks (LinkedStack and ArrayStack data structures) and queues (LinkedQueue and
ArrayQueue 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.
ex.
Mom
Madam
Solutions:
1- Array List Solution
a. Array Queue (Circular Array with One Unused Location)
b. Array Stack
2- Linked List Solution
a. Linked Queue
i. Simple Linked Queue
ii. Two Part Circular Linked Queue (Extra credit)
b. Linked Stack
Page | 1
1- Array List Solution:
 Class Palindrome:
public class Palindrome
main(String[ ] args)
isPalindrome(String input)
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 )){
System.out.println(“That is a palindrome.”);
}
else{
System.out.println(“That is not a palindrome.”);
}
}
public static boolean isPalindrome(String input)
{
ArrayQueue q = new ArrayQueue( );
ArrayStack s = new ArrayStack( );
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; } } Page | 2  Class ArrayQueue: public final class ArrayQueue implements QueueInterface private T[] queue private int frontIndex private int backIndex private boolean initialized private static final int DEFAULT_CAPACITY private static final int MAX_CAPACITY public ArrayQueue() public ArrayQueue(int initialCapacity) public void enqueue(T newEntry) public T getFront() public T dequeue() public boolean isEmpty() public void clear() private void checkInitialization() private void checkCapacity(int capacity) private void ensureCapacity()  Class ArrayStack: public final class ArrayStack implements StackInterface private T[] stack private int topIndex private boolean initialized private static final int DEFAULT_CAPACITY private static final int MAX_CAPACITY public ArrayStack() public ArrayStack(int initialCapacity) public void push(T newEntry) public T peek() public T pop() public boolean isEmpty() public void clear() private void checkInitialization() private void checkCapacity(int capacity) private void ensureCapacity()  Interface QueueInterface: public interface QueueInterface public void enqueue(T newEntry) public T dequeue() public T getFront(); public boolean isEmpty(); public void clear(); Page | 3  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() public EmptyQueueException(String message) public class EmptyQueueException extends RuntimeException { public EmptyQueueException() { this(null); } // end default constructor public EmptyQueueException(String message) { super(message); } // end constructor } // end EmptyQueueException Page | 4 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(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; } } Page | 5  Class Linked Queue: 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 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 Linked Stack: 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 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) Page | 6  Interface Queue Interface: public interface QueueInterface public void enqueue(T newEntry) public T dequeue() public T getFront(); public boolean isEmpty(); public void clear();  Interface Stack Interface public interface StackInterface public void push(T newEntry); public T pop(); public T peek(); public boolean isEmpty(); public void clear();  Class Empty Queue Exception: public class EmptyQueueException extends RuntimeException public EmptyQueueException() public EmptyQueueException(String message) public class EmptyQueueException extends RuntimeException { public EmptyQueueException() { this(null); } // end default constructor public EmptyQueueException(String message) { super(message); } // end constructor } // end EmptyQueueException Page | 7  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 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) Page | 8 Midterm .settings bin src ArrayListSolution Array Queue.java DArrayStack.java EmptyQueueException.java EmptyStackException.java D Palindrome.java QueueInterface.java Stackinterface.java LinkedListSolution EmptyQueueException.java D EmptyStackException.java LinkedQueue.java LinkedStack.java D Palindrome.java QueueInterface.java StackInterface.java TwoPartCircularLinkedQueue_extraCredit.java