Data Structures using java Chapter 8 Q 5. Implement the palindrome-recognition a

Question

Data Structures using java

Chapter 8 Q 5.

Implement the palindrome-recognition algrithm described in the section "Simple Applications of the ADT Queue"

+isPal(in str:String) : boolean

// Detemaies whether str is a palindrome

// creat an empty queue and anempty stack

aQueue.CreatQueue()

aStack.CreateStack()

// insert each character of the string into both

//the Queue and stack

lenght = the length of str

for ( i=1 through length){

nextChar=i th character of str

aQueue.enqueue(nextChar)

aStack.push(nextchar)

} //end for

// compaer the queue characters with the stack characters

charactersAreEqual = ture

while(aQueue is not empty and charactersAreEqual is ture) {

queueFront = aQueue.dequeue()

stackTop = aStack.pop()

if (queueFront not equal to stackTop){

charactersAreEqual = false

} //end if

} // end while

return charactersAreEqual

Explanation / Answer

Driver class:

import java.util.*;
public class PalindromeRecog
{
   public static void main(String[] args)
   {
       Scanner sc = new Scanner(System.in);
       System.out.print("Enter the string: ");
       String line = sc.nextLine();
       if(isPalindrome(line))
           System.out.println(line+" is a Palindrome");
       else
           System.out.println(line+" is not a Palindrome");
      
   }
   public static boolean isPalindrome(String line)
   {
       Queue<Character> queue = new Queue<>();
       Stack<Character> stack = new Stack<>();
       for(char c:line.toCharArray())
       {
           queue.enqueue(c);
           stack.push(c);
       }
       boolean charactersAreEqual = true;
       while(!queue.isEmpty() && charactersAreEqual)
       {
           char queueFront = queue.dequeue();
           char stackTop = stack.pop();
           if(queueFront != stackTop)charactersAreEqual = false;
       }
       return charactersAreEqual;
   }
}

ADT Queue class:

import java.util.*;

public class Queue<E> {
   private LinkedList<E> list = new LinkedList<E>();

   public void enqueue(E item) {
       list.addLast(item);
   }

   public E dequeue() {
       return list.poll();
   }

   public boolean hasItems() {
       return !list.isEmpty();
   }

   public int size() {
       return list.size();
   }
   public boolean isEmpty()
   {
       return this.size() == 0;
   }
}

ADT Stack class:

import java.util.LinkedList;

public class Stack<E> {
   private LinkedList<E> list = new LinkedList<E>();
  
  

   public void push(E e) {
       list.addFirst(e);
   }

   public E pop() {
       E e = list.get(0);
       list.remove(0);
       return e;
      
   }

   public E peek() {
       return list.get(0);
   }

   public boolean isEmpty() {
       return list.size() == 0;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.