Question

Project Requirements In both cases use the queue classes we have created in class, not the Java API queue options. Be sure to use LinkedQueue<T>for the first program and CircularArrayQueue<T>for the second one 1.) Create a simple interactive program that asks the user to input a string and when they press return, the program uses queue(s) to test whether or not the string is a palindrome (that is, whether the characters read the same both forward and backward). Be sure to test strings that have an even number of characters and an odd number of characters. Also, implement the same test using stack(s). I recommend creating two separate functions, both of which return boolean true/false indicating whether the string provided as an input to the function is a palindrome. Clearly, one function will uses queue(s) and the other stack(s). Here's what a sample run of the program might look like Enter a string: madamimadam According to the queue method that statement IS a palindrome. According to the stack method that statement IS a palindrome. Try another (y/n)? y Enter a string: racecar According to the queue method that statement IS a palindrome. According to the stack method that statement Is a palindrome. Try another (y/n)? y Enter a string: racecars According to the queue method that statement IS NOT a palindrome. According to the stack method that statement IS NOT a palindrome. Try another (y/n)? n

------------------------------------------------------------------------------------------------------------ CODE ALREADY HAVE BELOW---------------------------------------------------------------------------------------

public class LinkedQueue<T> implements QueueADT<T>
{

   private int count;
   private LinearNode<T> head;
   private LinearNode<T> tail;
          
   public LinkedQueue()
   {
       count = 0;
       head = null;
       tail = null;
   }
   @Override
   public void enqueue(T element)
   {
       LinearNode<T> node = new LinearNode<T> (element);
       if(isEmpty())
           head = node;
       else
           tail.setNext(node);
       tail = node;
       ++count;
      
   }

   @Override
   public T dequeue() throws EmptyCollectionException
   {
       if (isEmpty())
       {
           throw new EmptyCollectionException();
       }
          
           T result = head.getElement();
           head = head.getNext();
           --count;
           if(isEmpty())
               tail = null;
           return result;
       }
      
  
  

   @Override
   public T first() throws EmptyCollectionException
   {
       if(isEmpty())
           throw new EmptyCollectionException();
       return head.getElement();
   }

   @Override
   public int size()
   {
       return count;
   }

   @Override
   public boolean isEmpty()
   {
       return count<=0;
   }
  
   public String toString()
   {
       String output = "LinkedQueue -> [ ";
       LinearNode<T> current = head;
       while(current != null)
       {
           output+= current.getElement().toString() + " ";
           current = current.getNext();
       }
       output+= "]";
       return output;
   }

}

public class LinearNode<T>
{
   private LinearNode<T> next;
   private T           element;
  
   public LinearNode()
   {
       next = null;
       element = null;
   }
  
   public LinearNode(T elem)
   {
       next = null;
       element = elem;
   }
  
   public LinearNode<T> getNext()
   {
       return next;
   }
  
  
   public void setNext (LinearNode<T> node)
   {
       next = node;
   }
   public T getElement()
   {
       return element;
   }
  
   public void setElement(T elem)
   {
       element = elem;
   }
}

public interface QueueADT<T>
{
       public void enqueue(T element);
      
       public T dequeue() throws EmptyCollectionException;
      
       public T first() throws EmptyCollectionException;
      
       public int size();
      
       public boolean isEmpty();
}

public class EmptyCollectionException extends Exception
{
  
   private static final long serialVersionUID = 358083002087971606L;

   public EmptyCollectionException()
   {
       super();
   }
  
   public EmptyCollectionException(String msg)
   {
       super(msg);
   }
}

// P 121 Chap 5
public class CircularArrayQueue<T> implements QueueADT<T>
{
   private final static int DEFAULT_CAPACITY = 100; //Static b/c it's only 1 version of it
   private int front, rear, count;
   private T[] queue;
  
   @SuppressWarnings("unchecked")
   public CircularArrayQueue(int initialCapacity)
   {
       front = rear = count = 0;
       queue = (T[]) new Object [ initialCapacity];
   }
     
   public CircularArrayQueue()
   {
       this(DEFAULT_CAPACITY);
   }
  
   public void enqueue(T element)
   {
       if (size() == queue.length)
           expandCapacity();
      
       queue [rear] = element;
       rear = (rear + 1) % queue.length;
       ++count;
   }
  
  

   public T dequeue() throws EmptyCollectionException
   {
       if(isEmpty())
      
           throw new EmptyCollectionException();
      
       T result = queue[front];
       queue [front] = null;
       front = (front + 1) % queue.length;
       --count;
      
       return result;
   }
  
   public T first() throws EmptyCollectionException
   {
       if(isEmpty())
           throw new EmptyCollectionException();
      
       return queue[front];
   }
  
   public int size()
   {
       return count;
   }

   public boolean isEmpty()
   {
       return count <=0;
   }
  
   private void expandCapacity()
   {
       @SuppressWarnings("unchecked")
       T[] larger = (T[]) new Object [queue.length * 2];
       for(int i = 0; i < count; i++)
       {
           larger[i] = queue [front];
           front = (front + 1) % queue.length;
       }
       front = 0;
       rear = count;
      
       queue = larger;
   }
  
   public String toString()
   {
       String output= "CircularArrayQueue -> [ ";
       int pointer = front;
       for(int i =0; i < count; i++)
       {
           output+= queue [pointer] + " ";
           pointer = (pointer + 1) % queue.length;
       }
       output+= "]";
       return output;
   }

  
}

Answer 1

//Here's the code with comments for both the parts of the question 1:

public class Palindrome{
public static void main (String[] args) throws Exception{
checkPalindrome();
}

public static void checkPalindrome() throws Exception{
Scanner sc = new Scanner(System.in);
System.out.print("Enter a string: ");
// taking the input into the variable str
String str = sc.nextLine();
// checking using the queue
boolean queueCheck = checkForPalindromeUsingQueue(str);
// checking using the stack
boolean stackCheck = checkForPalindromeUsingStack(str);
String isNotStringQueue = queueCheck ? "IS" : "IS NOT";
String isNotStringStack = stackCheck ? "IS" : "IS NOT";
// printing the desired output
System.out.println("According to the queue method that statement " + isNotStringQueue + " a palindrome");
System.out.println("According to the queue method that statement " + isNotStringStack + " a palindrome");
System.out.println("Try another (y/n)?");
String input = sc.nextLine();
if (input.equals("y"))
checkPalindrome();
}

public static boolean checkForPalindromeUsingQueue(String str) throws Exception{
LinkedQueue queue = new LinkedQueue();
// storing the string character by character into the queue in reverse order
// because queue follows FIRST IN FIRST OUT logic
for(int i = str.length()-1; i >= 0; i--)
queue.enqueue(str.charAt(i));
// creating the reverse string using the queue created above
// on dequeuing the queue, it will output a new string in the reverse order of the original string
String reverse = "";
while(!queue.isEmpty()){
reverse += queue.dequeue();
}
// if the reverse string is equal to the original string, then str is a palindrom otherwise no.
// same logic is followed in the implementation using the stack except that the stack data structure is
// used to store the string character by character.
return reverse.equals(str);
}

public static boolean checkForPalindromeUsingStack(String str){
Stack stack = new Stack();
for(int i = 0; i < str.length(); i++)
stack.push(str.charAt(i));

String reverse = "";
while(!stack.isEmpty())
reverse+=stack.pop();
return reverse.equals(str);
}
}