/ Fig. 21.3: listnode.h // Template ListNode class definition. #ifndef LISTNODE_H #define LISTNODE_H // forward declaration of class List template class List; template class ListNode { friend class List; // make List a friend public: ListNode( const NODETYPE & ); // constructor NODETYPE getData() const; // return data in node private: NODETYPE data; // data ListNode *nextPtr; // next node in list }; // end class ListNode // constructor template ListNode::ListNode( const NODETYPE &info ) : data( info ), nextPtr( 0 ) { // empty body } // end ListNode constructor // return copy of data in node template NODETYPE ListNode::getData() const { return data; } // end function getData #endif 

/*----------------------------------------------------------------------------------------------- LIST.H ---------------------------------------------------------------------------------------*/

// Fig. 21.4: list.h // Template List class definition. #ifndef LIST_H #define LIST_H #include  using std::cout; #include  #include "listnode.h" // ListNode class definition template class List { public: List(); // constructor ~List(); // destructor void insertAtFront( const NODETYPE & ); void insertAtBack( const NODETYPE & ); bool removeFromFront( NODETYPE & ); bool removeFromBack( NODETYPE & ); bool isEmpty() const; void print() const; private: ListNode *firstPtr; // pointer to first node ListNode *lastPtr; // pointer to last node // utility function to allocate new node ListNode *getNewNode( const NODETYPE & ); }; // end class List // default constructor template List::List() : firstPtr( 0 ), lastPtr( 0 ) { // empty body } // end List constructor // destructor template List::~List() { if ( !isEmpty() ) { // List is not empty // cout  *currentPtr = firstPtr; ListNode *tempPtr; while ( currentPtr != 0 ) // delete remaining nodes { tempPtr = currentPtr; // commented out the output -- no need to print what we are deallocating // cout data nextPtr; delete tempPtr; } } // cout  void List::insertAtFront( const NODETYPE &value ) { ListNode *newPtr = getNewNode( value ); if ( isEmpty() ) // List is empty firstPtr = lastPtr = newPtr; else { // List is not empty newPtr->nextPtr = firstPtr; firstPtr = newPtr; } // end else } // end function insertAtFront // insert node at back of list template void List::insertAtBack( const NODETYPE &value ) { ListNode *newPtr = getNewNode( value ); if ( isEmpty() ) // List is empty firstPtr = lastPtr = newPtr; else { // List is not empty lastPtr->nextPtr = newPtr; lastPtr = newPtr; } // end else } // end function insertAtBack // delete node from front of list template bool List::removeFromFront( NODETYPE &value ) { if ( isEmpty() ) // List is empty return false; // delete unsuccessful else { ListNode *tempPtr = firstPtr; if ( firstPtr == lastPtr ) firstPtr = lastPtr = 0; else firstPtr = firstPtr->nextPtr; value = tempPtr->data; // data being removed delete tempPtr; return true; // delete successful } // end else } // end function removeFromFront // delete node from back of list template bool List::removeFromBack( NODETYPE &value ) { if ( isEmpty() ) return false; // delete unsuccessful else { ListNode *tempPtr = lastPtr; if ( firstPtr == lastPtr ) firstPtr = lastPtr = 0; else { ListNode *currentPtr = firstPtr; // locate second-to-last element while ( currentPtr->nextPtr != lastPtr ) currentPtr = currentPtr->nextPtr; lastPtr = currentPtr; currentPtr->nextPtr = 0; } // end else value = tempPtr->data; delete tempPtr; return true; // delete successful } // end else } // end function removeFromBack // is List empty? template bool List::isEmpty() const { return firstPtr == 0; } // end function isEmpty // return pointer to newly allocated node template ListNode *List::getNewNode( const NODETYPE &value ) { return new ListNode( value ); } // end function getNewNode // display contents of List template void List::print() const { if ( isEmpty() ) { cout  *currentPtr = firstPtr; cout data nextPtr; } // end while cout  
 *---------------------------------------------------------------------------------------------------- STACK.H ---------------------------------------------------------------------------------------*/
 
// Fig. 21.15: Stackcomposition.h // Template Stack class definition with composed List object. #ifndef STACKCOMPOSITION_H #define STACKCOMPOSITION_H #include "list.h" // List class definition template class Stack { public: // no constructor; List constructor does initialization // push calls stackList object's insertAtFront member function void push( const STACKTYPE &data ) { stackList.insertAtFront( data ); } // end function push // pop calls stackList object's removeFromFront member function bool pop( STACKTYPE &data ) { return stackList.removeFromFront( data ); } // end function pop // isStackEmpty calls stackList object's isEmpty member function bool isStackEmpty() const { return stackList.isEmpty(); } // end function isStackEmpty // printStack calls stackList object's print member function void printStack() const { stackList.print(); } // end function printStack private: List stackList; // composed List object }; // end class Stack #endif 
 
  Write a program that uses a stack object to determine if a string is a palindrome (i.e. the string is spelled identically backward and forward). The program should ignore spaces and punctuation. Go ahead and start your program by reading in a C-style string from standard input, using the getline function. You may assume a limit of 100 characters on the string (although this can be written, with a little more effort, to accept any size string). Your algorithm must make use of a stack (of type char). Use the Deitel implementation of the Stack from stack.h" (you don't need to change this file). Ignore spacing and punctuation, as well as special characters and digits (i.e. only count letters as part of a palindrome, and account for upper/lower case. For example, 'B' and 'b' are matching letters) Sample runs: (user input underlined) Please enter a atring: ABCDEPGHGFEDCBA IS a Pa "ABCDEFGHGFEDCBA" IS a palindrome Please entr a tring: The quick brown fox is NOT palindrome Please enter a string: > Cigar? Toss it in a can. It is so tragic "Cigar? Toss it in a can. It is so tragic." IS a palindrome