Write a c++ program that has the following features, please use 3 space indentation instead of tabs. I will use this as a reference for future coding exercises. Thank you!

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 another sequence of characters which reads the same backward as forward, such as madam or race car. Sentence-length 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 changed 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 the first Node in list

count keeps track of the 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 the 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 the first Node in list

rear points to the last Node in list

count keeps track of the 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 the queue is empty, false otherwise

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

There is pseudocode written for the queue class and available under Notes on Blackboard.

Requirements for main:

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 Output:

The phrase race car is a palindrome.

The phrase man made is not a palindrome.

Please enter a phrase:

Madam

Madam is a palindrome.