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.

***I have the following done but i do not know if my main is working correctly with the queues and stacks.Dont understand how to build the main.Please help.**

#include #include using namespace std; class Node { private: Node *link; char x; public: Node (); Node (string); void set_link(Node *ptr); //mutator function to set next pointer Node*get_link(void);//accessor function return next pointer int compare_data (char ); void process_data(void); }; //Node class end Node::Node()//default constructor { link=NULL; x=0; } Node::Node(string phrase) { link=NULL; phrase=x; } void Node::set_link(Node*ptr) { link=ptr; } Node*Node::get_link(void) { return link; } class Queue //Queue class { private: Node*front; Node*rear; int count; public: Queue(); void enqueue(void);// adds a node to the end of the list bool dequeue(string p);//removes a node from the front of the queue bool get_front(void);//Returns item at the front of the queue bool empty(void);//returns true if queue is empty }; Queue::Queue() { front=NULL; rear=NULL; count=0; } void Queue::enqueue(void)//adds node to end of list { Node*ptr=new Node();//allocates new node if (front==NULL) { front=rear=ptr; } else { rear->set_link(ptr); rear=ptr; }/// count++;//counter } bool Queue::dequeue(string p) { if(front!=NULL) { Node*ptr=front; delete front; front=ptr; } if(front==NULL) { rear=NULL; count--; return true; }else return false; } bool Queue::get_front(void) { if(front!=NULL) return front; else return 0; } bool Queue::empty(void) { if((count=0)||(front==NULL)) return true; else return false; }//end of queue class class Stack //Stack class {private: Node*top;//points to first node in list int count;//counts number of nodes in list public: Stack(); bool push (string);//adds node to top of stack bool pop ();//removes node from top of stack bool empty();//returns true if stack empty }; Stack::Stack() { top = NULL; count = 0; } bool Stack::push (string w) { bool success = false; Node*ptr = new Node(); if (ptr!= NULL) { if (top!= NULL) { ptr->set_link (top); } // Set the top equal to the new Node. top = ptr; count ++; success = true; } return success; } bool Stack::pop () { bool success = false; Node *temp; if (top != NULL) // if (top) works also { // If there is a top, set success to true success = true; count --; temp = top; // Set the top pointer to the next data top = top->get_link(); // Delete the former top delete temp; } return success; }; bool Stack::empty() { if (top != NULL) return false; else return true; }//end of stack int main() { string phrase; Queue q; Stack s; while(true){ if (phrase.compare("-1")==0) { cout << "EXIT"<