Java Overview

Chapter 4 - Using Stacks and Queues

This assignment is to utilize the author's stack code and queue code from chapter 4 to determine if a string is a palindrome (or not). Note that an analysis of your two solutions is required to be compared to the algorithm given in this document. A palindrome is a word that is spelled the same forwards and backwards.
Assume that the phrase has been stripped of punctuation and is all the same case. For example, "A man, a plan, a canal. Panama!" is entered as "amanaplanacanalpanama"

Use the scanner class to input the data as a String

Modify the author's code to stack a character instead of a long int

The ONLY changes permitted are to the type of element on the stack
The modified code (StackX class in the file stack.java) must be in a separated class and a separate file

Similarly, modify the Queue code to use a character instead of a long int

The ONLY changes permitted are to the type of element in the queue
The modified code (Queue class in the file queue.java) must be in a separated class and a separate file

Your main program should RESEMBLE this:

public class PalindromeApp {

	public static void main(String[] args) {
	   Scanner kbd = new Scanner(System.in);
	
		System.out.print("Enter a phrase (or 'quit'): ");
		String phrase = kbd.nextLine();
		while (!phrase.equals("quit"))
		{
			System.out.print(phrase);
			if (isPalindromeSTACK(phrase)
				&& isPalindromeQUEUE(phrase))
				System.out.println(" is a palindrome");
			else
				System.out.println(" is NOT a palindrome");
			System.out.print("Enter a phrase (or 'quit'): ");
		  	phrase = kbd.nextLine();
		}
	}
	
	// the input parameter "word" consists of zero or more characters
	// this function determines if the initial word is a palindrome (true)
	// or not (false)
	private static boolean isPalindromeSTACK(String word)
	{
// your code that uses a Stack will go in here
	}
	private static boolean isPalindromeQUEUE(String word)
	{
// your code that uses a Queue will go in here
	}

}

Data Structure Requirements (40%)
1. No arrays are used in main, isPalindromeSTACK, and isPalindromeQUEUE.
2. String data types are permitted
3. Modified and used author's stack code
  Pop, Push, and isEmpty used
4. Modified and used author's queue code
Algorithm Requirements (40%)
1. Works! correctly identifies palindromes
Analysis Requirements (20%)
Use documentation for the lines in isPalindromeSTACK and isPalindromeQUEUE to show the running time of the code
Analyze the following algorithm and compare the running time of the three solutions (i.e, code below, your isPalindromeSTACK and your isPalindromeQUEUE)
```
  for i from 0 to n/2 do
	if a[i] != a[n-i] 
	    exit
  if i != n/2  
   	return false
  else
	return true
```