( The codes below do not have to be changed, just write the code for the question that compiles with the codes given below) 

Write a program to check if a piece of text that the user enters is a palindrome. In this case, you add each character to both a stack and a queue as it is read.

After each character has been put onto both the stack and the queue, start removing characters from both the stack and the queue, and comparing them. If the word is a palindrome, the first character popped will be the same as the first character dequeued, and so on for the second and subsequent characters until the stack and queue are empty.

You MUST follow the approach described here to test for palindromes; any other approach not using stacks and queues, will earn you 0 marks.

Palindrome comparisons are normally not case-sensitive, so you could convert all characters to uppercase first. Also, non-alphanumeric characters, such as punctuation and spaces, are usually ignored. For maximum marks, figure out how to use the appropriate method in Javas Character class to do this.

Stack Class

public interface Stack { // most important methods public void push(Object n); // push an object onto top of the stack public Object pop(); // pop an object from top of the stack // others public Object top(); // examine top object on stack without removing it public boolean isEmpty(); // true if stack is empty public boolean isFull(); // true if stack is full (if it has limited storage) } 

ArrayStack Class

import javax.swing.JOptionPane; public class ArrayStack implements Stack { protected int capacity; // The actual capacity of the stack array protected static final int CAPACITY = 1000; // default array capacity protected Object S[]; // array used to implement the stack protected int top = -1; // index for the top of the stack public ArrayStack() { // default constructor: creates stack with default capacity this(CAPACITY); } public ArrayStack(int cap) { // this constructor allows you to specify capacity of stack capacity = (cap > 0) ? cap : CAPACITY; S = new Object[capacity]; } public void push(Object element) { if (isFull()) { JOptionPane.showMessageDialog(null, "ERROR: Stack is full."); return; } top++; S[top] = element; } public Object pop() { Object element; if (isEmpty()) { JOptionPane.showMessageDialog(null, "ERROR: Stack is empty."); return null; } element = S[top]; S[top] = null; top--; return element; } public Object top() { if (isEmpty()) { JOptionPane.showMessageDialog(null, "ERROR: Stack is empty."); return null; } return S[top]; } public boolean isEmpty() { return (top < 0); } public boolean isFull() { return (top == capacity-1); } public int size() { return (top + 1); } } 

Queue Class

public interface Queue { // most important methods public void enqueue(Object n); // add an object at the rear of the queue public Object dequeue(); // remove an object from the front of the queue // others public boolean isEmpty(); // true if queue is empty public boolean isFull(); // true if queue is full (if it has limited storage) public Object front(); // examine front object on queue without removing it } 

ArrayQueue Class

public class ArrayQueue implements Queue { protected Object Q[]; // array used to implement the queue protected int rear = -1; // index for the rear of the queue protected int capacity; // The actual capacity of the queue array public static final int CAPACITY = 1000; // default array capacity public ArrayQueue() { // default constructor: creates queue with default capacity this(CAPACITY); } public ArrayQueue(int cap) { // this constructor allows you to specify capacity capacity = (cap > 0) ? cap : CAPACITY; Q = new Object[capacity]; } public void enqueue(Object n) { if (isFull()) { JOptionPane.showMessageDialog(null, "Cannot enqueue object; queue is full."); return; } rear++; Q[rear] = n; } public Object dequeue() { // Can't do anything if it's empty if (isEmpty()) return null; Object toReturn = Q[0]; // shuffle all other objects towards 0 int i = 1; while (i <= rear) { Q[i-1] = Q[i]; i++; } rear--; return toReturn; } public boolean isEmpty() { return (rear < 0); } public boolean isFull() { return (rear == capacity-1); } public Object front() { if (isEmpty()) return null; return Q[0]; } }