Description: You are going to write a program that checks to see if a string is a palindrome. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward, such as madam or race car. Sentencelength palindromes may be written when allowances are made for adjustments of capital letters, punctuation, or word dividers, such as A man, a plan, a canal Panama!. (Wikipedia) You will use a stack and a queue to determine if a phrase is a palindrome. You will ignore spaces and punctuation. You may use either a c-string or a c++ string. (Hint: You should store characters on the stack and queue to make this easy.)

The stack class is written for you, but will need to be modified to use the correct type. You will need to write the queue class. The Node class will need to be modified to work with the stack and queue classes.

The code to check to see if the string is a palindrome should be in the main function. You should have 2 test cases that you test in main one that is palindrome and one that isnt. Then you should ask the user for a phrase until the user wishes to terminate.

Specific information for classes:

Stack class data

top points to first Node in list

count keeps track of number of Nodes in list

Stack class functions

Any needed constructors

push adds a Node to the top of the stack

pop Removes a Node from the top of the stack

stack_top Returns the item at the top of the stack without affecting the stack

empty returns true if stack is empty, false otherwise

Note: Remember that a stack is created in static (automatic memory) and a Node is in dynamic memory.

Queue class data

front points to first Node in list

rear points to the last Node in list

count keeps track of number of Nodes in list Stack class functions

Any needed constructors enqueue adds a Node to the end of the list

dequeue Removes a Node from the front of the queue

get_front Returns the item at the front of the queue without affecting the queue

empty returns true if queue is empty, false otherwise

Note: Remember that a queue is created in static (automatic memory) and a Node is in dynamic memory.

In the main program, you will test 2 cases; one that is a palindrome and one that isnt. Then you will ask the user for a phrase and indicate whether or not the phrase is a palindrome. You will loop until the user wishes to exit. Sample: The phrase race car is a palindrome. The phrase man made is not a palindrome. Please enter a phrase: Madam Madam is a palindrome.