Question

(Using Java) create a class that can identify a palindrome.

A palindrome is defined as
- A string of characters that reads the same from left to right as its does from right to left
- Example: Anna, Civic, Kayak, Level, Madam
- To recognize a palindrome, a queue can be used in conjunction with a stack
o A stack can be used to reverse the order of occurrences
o A queue can be used to preserve the order of occurrences
Hints: Use Stack class in JAVA library： https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
Regard linked list in JAVA Library as queue：http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

Answer 1

A palindrome is defined as
- A string of characters that reads the same from left to right as its does from right to left.

To recognize a palindrome, a queue can be used in conjunction with a stack.
o A stack can be used to reverse the order of occurrences
o A queue can be used to preserve the order of occurrences

A nonrecursive recognition algorithm for palindromes:

As you traverse the character string from left to right, insert each character into both a queue and a stack.

Compare the characters at the front of the queue and the top of the stack.(LIFO)

stack operations:

push(object o): inserts element o

pop(): removes and returns the last inserted element

isEmpty(): returns a Boolean value indicating whether no elements are stored.

a(top)

b

c

b

Queue Operations:

A queue is a list from which items are deleted from one end (front) and into which items are inserted at the other end (rear, or back).

Queue is referred to as a first-in-first-out (FIFO) data structure.

The first item inserted into a queue is the first item to leave.

isEmpty():boolean – Determine whether a queue is empty.

a(front)

b

c

b

d(back)

Programming code:

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

import java.util.Scanner;

public class Palindrome

{

   public static void main(String[ ] args)

   {

        Scanner input = new Scanner(System.in);

        String inputString;     

      System.out.print("Enter the input string: ");

        inputString = input.next( );

        if (isPalindrome( inputString )){

               System.out.println("the string is a palindrome.");

        }

        else{

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

      }

   }

   public static boolean isPalindrome(String input)

   {  

      Queue<Character> q = new LinkedList<Character>( );

      Stack<Character> s = new Stack<Character>( );

      char letter;

      int i;

     

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

      {

        letter = input.charAt(i);

         q.add(letter);

         s.push(letter);

      }   

      while (!q.isEmpty( ))

      {

         if (q.remove( ) != s.pop( ))

           return false;

      }

      return true;

   }

   

}

Image of coding:

Image of output1:

imge of output2:Image of output3: