Palindrome
A palindrome is a string that reads the same front to back as it does back to front, such as "racecar". Solve the palindrome question using a Stack class, implemented as a linked list, (not an array) (you must code it - do not use the library Stack class), and a Queue class implemented as a linked list, (not an array) The Stack class should have a constructor, pop, push, and isEmpty methods. The Queue class should have a constructor, enqueue, dequeue, and isEmpty methods. Each class will have a private embedded Node class. For up to 15 points bonus, rather than using java's linked list class, create your own singly linked list and use it to implement the stack and queue classes.
Read in a string of any size, strip it of any punctuation and blank characters, and then reduce it to all lower case. Then push the string characters one by one into a stack and insert them one by one into a queue. As long as there is data in the stack and queue, pop from the stack and remove from the queue comparing the characters popped and removed. If the characters continue to be equal until the stack and queue are empty, the string is a palindrome. Run the program four times using 2 phrases that are palindromes, two phrases that are not palindromes. Be sure to test Madam, I'm Adam!!! and "abca" as two of your choices.
Turn in the source, output, and UML for the stack and queue classes.
Telephone Lookups
Create a program for telephone lookups. Your tasks are to allow the user find a number that is associated with a name and if given a number, find the name associated with it (normal and reverse lookups).
The data file phoneList.txt is a listing of 1000 names and phone numbers in random order. Each line of the file consists of a last name, a first name and a telephone number with area code structured as follows: Mallanda Adam 770 816-6193. phonelist2 is a list formatted in a similar manner but it has errors built in to the listing. For up to 15 points bonus, use this listing , finding the errors, generating an error list and still building the collection but only with valid data.
You should have a class for the data and an array for holding those 1000 objects. The class should implement the comparable interface, have a toString and any other methods you have a need for. This class should not have sort or search methods. Those can be in other classes of their own.
You must write and use insertion sorts for any sorting performed in this project.
Since we are not adding or removing data once the array is built, and since memory is relatively cheap, build and sort your arrays before doing any searches. Do not re-sort the arrays between searches.
The use of a binary search is required for both searches.
Turn in the client, the classes and output showing that you can find numbers from names, that you can find names from numbers and showing how you handle the cases where the names or numbers are not in the data set.