Please Need hellp with Data Structures C++ problem.

The objective of this problem is to reinforce stack concepts in C++.

Specifically, the exercise is to do the problem below. Use the stack4 and node2 files provided.

//main.cpp file

//was also given this file but complier kept having issues.

#include #include #include "stack4.h"

using namespace std; using namespace main_savitch_7B;

int main(int argc, char **argv) { stack s, s1; s.push(1); s.push(2); s.push(3); s1=s; while(!s.empty()) { cout

/////////////////////////////////////////////////////////////////////////////////////

// FILE: stack4.h (part of the namespace main_savitch_7B) // TEMPLATE CLASS PROVIDED: stack (a stack of items) // The template parameter, Item, is the data type of the items in the stack, // also defined as stack::value_type. // It may be any of the C++ built-in types (int, char, etc.), or a class // with a default constructor, a copy constructor, and an assignment // operator. The definition stack::size_type is the data type of // any variable that keeps track of how many items are in a stack. // // CONSTRUCTOR for the stack template class: // stack( ) // Postcondition: The stack has been initialized as an empty stack. // // MODIFICATION MEMBER FUNCTIONS for the stack class: // void push(const Item& entry) // Precondition: size( ) 0. // Postcondition: The top item of the stack has been removed. // // Item& top( ) // Precondition: size( ) > 0. // Postcondition: The return value is a reference to the top item of // the stack (but the stack is unchanged). // // CONSTANT MEMBER FUNCTIONS for the stack class: // bool empty( ) const // Postcondition: Return value is true if the stack is empty. // // size_type size( ) const // Postcondition: Return value is the total number of items in the stack. // // const Item& top( ) const // Precondition: size( ) > 0. // Postcondition: The return value is a const reference to the top item of // the stack (but the stack is unchanged). // // VALUE SEMANTICS for the stack class: // Assignments and the copy constructor may be used with stack // objects. // // DYNAMIC MEMORY USAGE by the stack template class: // If there is insufficient dynamic memory, then the following functions // throw bad_alloc: // the copy constructor, push, and the assignment operator.

#ifndef MAIN_SAVITCH_STACK4_H #define MAIN_SAVITCH_STACK4_H #include // Provides NULL and size_t #include "node2.h" // Node template class from Figure 6.5 on page 308

namespace main_savitch_7B { template class stack { public: // TYPEDEFS typedef std::size_t size_type; typedef Item value_type; // CONSTRUCTORS and DESTRUCTOR stack( ) { top_ptr = NULL; } stack(const stack& source); ~stack( ) { list_clear(top_ptr); } // MODIFICATION MEMBER FUNCTIONS void push(const Item& entry); void pop( ); void operator =(const stack& source); Item& top( ); // CONSTANT MEMBER FUNCTIONS size_type size( ) const { return main_savitch_6B::list_length(top_ptr); } bool empty( ) const { return (top_ptr == NULL); } const Item& top( ) const; private: main_savitch_6B::node *top_ptr; // Points to top of stack }; }

#include "stack4.template" // Include the implementation #endif

/////////////////////////////

// FILE: stack4.template // TEMPLATE CLASS IMPLEMENTED: stack (see stack4.h for documentation) // This file is included in the header file, and not compiled separately. // INVARIANT for the stack class: // 1. The items in the stack are stored in a linked list, with the top of the // stack stored at the head node, down to the bottom of the stack at the // final node. // 2. The member variable top_ptr is the head pointer of the linked list.

#include // Provides assert #include "node2.h" // Node template class

namespace main_savitch_7B { template stack::stack(const stack& source) // Library facilities used: node2.h { main_savitch_6B::node *tail_ptr; // Needed for argument of list_copy

list_copy(source.top_ptr, top_ptr, tail_ptr); }

template void stack::push(const Item& entry) // Library facilities used: node2.h { list_head_insert(top_ptr, entry); }

template void stack::pop( ) // Library facilities used: cassert, node2.h { assert(!empty( )); list_head_remove(top_ptr); } template void stack::operator =(const stack& source) // Library facilities used: node2.h { main_savitch_6B::node *tail_ptr; // Needed for argument of list_copy

if (this == &source) // Handle self-assignment return;

list_clear(top_ptr); list_copy(source.top_ptr, top_ptr, tail_ptr); }

template Item& stack::top( ) // Library facilities used: cassert { assert(!empty( )); return top_ptr->data( ); }

template const Item& stack::top( ) const // Library facilities used: cassert { assert(!empty( )); return top_ptr->data( ); } }

///////////////////////////////////////////

// FILE: node2.h (part of the namespace main_savitch_6B) // PROVIDES: A template class for a node in a linked list, and list manipulation // functions. The template parameter is the type of the data in each node. // This file also defines a template class: node_iterator. // The node_iterator is a forward iterators with two constructors: // (1) A constructor (with a node* parameter) that attaches the iterator // to the specified node in a linked list, and (2) a default constructor that // creates a special iterator that marks the position that is beyond the end of a // linked list. There is also a const_node_iterator for use with // const node* . // // TYPEDEF for the node template class: // Each node of the list contains a piece of data and a pointer to the // next node. The type of the data (node::value_type) is the Item type // from the template parameter. The type may be any of the built-in C++ classes // (int, char, ...) or a class with a default constructor, an assignment // operator, and a test for equality (x == y). // NOTE: // Many compilers require the use of the new keyword typename before using // the expression node::value_type. Otherwise // the compiler doesn't have enough information to realize that it is the // name of a data type. // // CONSTRUCTOR for the node class: // node( // const Item& init_data = Item(), // node* init_link = NULL // ) // Postcondition: The node contains the specified data and link. // NOTE: The default value for the init_data is obtained from the default // constructor of the Item. In the ANSI/ISO standard, this notation // is also allowed for the built-in types, providing a default value of // zero. The init_link has a default value of NULL. // // NOTE about two versions of some functions: // The data function returns a reference to the data field of a node and // the link function returns a copy of the link field of a node. // Each of these functions comes in two versions: a const version and a // non-const version. If the function is activated by a const node, then the // compiler choses the const version (and the return value is const). // If the function is activated by a non-const node, then the compiler choses // the non-const version (and the return value will be non-const). // EXAMPLES: // const node *c; // c->link( ) activates the const version of link returning const node* // c->data( ) activates the const version of data returning const Item& // c->data( ) = 42; ... is forbidden // node *p; // p->link( ) activates the non-const version of link returning node* // p->data( ) activates the non-const version of data returning Item& // p->data( ) = 42; ... actually changes the data in p's node // // MEMBER FUNCTIONS for the node class: // const Item& data( ) const // void list_clear(node*& head_ptr) // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: All nodes of the list have been returned to the heap, // and the head_ptr is now NULL. // // template // void list_copy // (const node* source_ptr, node*& head_ptr, node*& tail_ptr) // Precondition: source_ptr is the head pointer of a linked list. // Postcondition: head_ptr and tail_ptr are the head and tail pointers for // a new list that contains the same items as the list pointed to by // source_ptr. The original list is unaltered. // // template // void list_head_insert(node*& head_ptr, const Item& entry) // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: A new node containing the given entry has been added at // the head of the linked list; head_ptr now points to the head of the new, // longer linked list. // // template // void list_head_remove(node*& head_ptr) // Precondition: head_ptr is the head pointer of a linked list, with at // least one node. // Postcondition: The head node has been removed and returned to the heap; // head_ptr is now the head pointer of the new, shorter linked list. // // template // void list_insert(node* previous_ptr, const Item& entry) // Precondition: previous_ptr points to a node in a linked list. // Postcondition: A new node containing the given entry has been added // after the node that previous_ptr points to. // // template // size_t list_length(const node* head_ptr) // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: The value returned is the number of nodes in the linked // list. // // template // NodePtr list_locate(NodePtr head_ptr, SizeType position) // The NodePtr may be either node* or const node* // Precondition: head_ptr is the head pointer of a linked list, and // position > 0. // Postcondition: The return value is a pointer that points to the node at // the specified position in the list. (The head node is position 1, the // next node is position 2, and so on). If there is no such position, then // the null pointer is returned. // // template // void list_remove(node* previous_ptr) // Precondition: previous_ptr points to a node in a linked list, and this // is not the tail node of the list. // Postcondition: The node after previous_ptr has been removed from the // linked list. // // template // NodePtr list_search // (NodePtr head_ptr, const Item& target) // The NodePtr may be either node* or const node* // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: The return value is a pointer that points to the first // node containing the specified target in its data member. If there is no // such node, the null pointer is returned. // // DYNAMIC MEMORY usage by the toolkit: // If there is insufficient dynamic memory, then the following functions throw // bad_alloc: the constructor, list_head_insert, list_insert, list_copy.

#ifndef MAIN_SAVITCH_NODE2_H #define MAIN_SAVITCH_NODE2_H #include // Provides NULL and size_t #include // Provides iterator and forward_iterator_tag

namespace main_savitch_6B { template class node { public: // TYPEDEF typedef Item value_type; // CONSTRUCTOR node(const Item& init_data=Item( ), node* init_link=NULL) { data_field = init_data; link_field = init_link; } // MODIFICATION MEMBER FUNCTIONS Item& data( ) { return data_field; } node* link( ) { return link_field; } void set_data(const Item& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; } // CONST MEMBER FUNCTIONS const Item& data( ) const { return data_field; } const node* link( ) const { return link_field; } private: Item data_field; node *link_field; };

// FUNCTIONS to manipulate a linked list: template void list_clear(node*& head_ptr);

template void list_copy (const node* source_ptr, node*& head_ptr, node*& tail_ptr);

template void list_head_insert(node*& head_ptr, const Item& entry);

template void list_head_remove(node*& head_ptr);

template void list_insert(node* previous_ptr, const Item& entry); template std::size_t list_length(const node* head_ptr);

template NodePtr list_locate(NodePtr head_ptr, SizeType position);

template void list_remove(node* previous_ptr); template NodePtr list_search(NodePtr head_ptr, const Item& target);

// FORWARD ITERATORS to step through the nodes of a linked list // A node_iterator of can change the underlying linked list through the // * operator, so it may not be used with a const node. The // node_const_iterator cannot change the underlying linked list // through the * operator, so it may be used with a const node. // WARNING: // This classes use std::iterator as its base class; // Older compilers that do not support the std::iterator class can // delete everything after the word iterator in the second line:

template class node_iterator : public std::iterator<:forward_iterator_tag item> { public: node_iterator(node* initial = NULL) { current = initial; } Item& operator *( ) const { return current->data( ); } node_iterator& operator ++( ) // Prefix ++ { current = current->link( ); return *this; } node_iterator operator ++(int) // Postfix ++ { node_iterator original(current); current = current->link( ); return original; } bool operator ==(const node_iterator other) const { return current == other.current; } bool operator !=(const node_iterator other) const { return current != other.current; } private: node* current; };

template class const_node_iterator : public std::iterator<:forward_iterator_tag const item> { public: const_node_iterator(const node* initial = NULL) { current = initial; } const Item& operator *( ) const { return current->data( ); } const_node_iterator& operator ++( ) // Prefix ++ { current = current->link( ); return *this; } const_node_iterator operator ++(int) // Postfix ++ { const_node_iterator original(current); current = current->link( ); return original; } bool operator ==(const const_node_iterator other) const { return current == other.current; } bool operator !=(const const_node_iterator other) const { return current != other.current; } private: const node* current; };

}

#include "node2.template" #endif

//////////////////////////////////////////////

// FILE: node2.template // IMPLEMENTS: The functions of the node template class and the // linked list toolkit (see node2.h for documentation). // // NOTE: // Since node is a template class, this file is included in node2.h. // Therefore, we should not put any using directives in this file. // // INVARIANT for the node class: // The data of a node is stored in data_field, and the link in link_field.

#include // Provides assert #include // Provides NULL and size_t

namespace main_savitch_6B { template void list_clear(node*& head_ptr) // Library facilities used: cstdlib { while (head_ptr != NULL) list_head_remove(head_ptr); }

template void list_copy( const node* source_ptr, node*& head_ptr, node*& tail_ptr ) // Library facilities used: cstdlib { head_ptr = NULL; tail_ptr = NULL;

// Handle the case of the empty list if (source_ptr == NULL) return;

// Make the head node for the newly created list, and put data in it list_head_insert(head_ptr, source_ptr->data( )); tail_ptr = head_ptr; // Copy rest of the nodes one at a time, adding at the tail of new list source_ptr = source_ptr->link( ); while (source_ptr != NULL) { list_insert(tail_ptr, source_ptr->data( )); tail_ptr = tail_ptr->link( ); source_ptr = source_ptr->link( ); } } template void list_head_insert(node*& head_ptr, const Item& entry) { head_ptr = new node(entry, head_ptr); }

template void list_head_remove(node*& head_ptr) { node *remove_ptr;

remove_ptr = head_ptr; head_ptr = head_ptr->link( ); delete remove_ptr; }

template void list_insert(node* previous_ptr, const Item& entry) { node *insert_ptr; insert_ptr = new node(entry, previous_ptr->link( )); previous_ptr->set_link(insert_ptr); }

template std::size_t list_length(const node* head_ptr) // Library facilities used: cstdlib { const node *cursor; std::size_t answer; answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) ++answer; return answer; }

template NodePtr list_locate(NodePtr head_ptr, SizeType position) // Library facilities used: cassert, cstdlib { NodePtr cursor; SizeType i; assert(0 link( ); return cursor; }

template void list_remove(node* previous_ptr) { node *remove_ptr;

remove_ptr = previous_ptr->link( ); previous_ptr->set_link(remove_ptr->link( )); delete remove_ptr; }

template NodePtr list_search(NodePtr head_ptr, const Item& target) // Library facilities used: cstdlib { NodePtr cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) if (target == cursor->data( )) return cursor; return NULL; } }

For any of your stack implementations 15 please write a new member function called swap with one reference parameter that is also a stack. After calling x.swap Cy), the value of x should equal the original value of y and vice versa