Please Need hellp with Data Structures C++ problem. The objective of this proble
ID: 3819551 • Letter: P
Question
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 <stdio.h>
#include <iostream>
#include "stack4.h"
using namespace std;
using namespace main_savitch_7B;
int main(int argc, char **argv)
{
stack<int> s, s1;
s.push(1);
s.push(2);
s.push(3);
s1=s;
while(!s.empty())
{
cout<<s.top()<<end1;
s.pop();
}
return 0;
}
/////////////////////////////////////////////////////////////////////////////////////
// FILE: stack4.h (part of the namespace main_savitch_7B)
// TEMPLATE CLASS PROVIDED: stack<Item> (a stack of items)
// The template parameter, Item, is the data type of the items in the stack,
// also defined as stack<Item>::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<Item>::size_type is the data type of
// any variable that keeps track of how many items are in a stack.
//
// CONSTRUCTOR for the stack<Item> template class:
// stack( )
// Postcondition: The stack has been initialized as an empty stack.
//
// MODIFICATION MEMBER FUNCTIONS for the stack<Item> class:
// void push(const Item& entry)
// Precondition: size( ) < CAPACITY.
// Postcondition: A new copy of entry has been pushed onto the stack.
//
// Item pop( )
// 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<Item> 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<Item> class:
// Assignments and the copy constructor may be used with stack<Item>
// objects.
//
// DYNAMIC MEMORY USAGE by the stack<Item> 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 <cstdlib> // Provides NULL and size_t
#include "node2.h" // Node template class from Figure 6.5 on page 308
namespace main_savitch_7B
{
template <class Item>
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<Item> *top_ptr; // Points to top of stack
};
}
#include "stack4.template" // Include the implementation
#endif
/////////////////////////////
// FILE: stack4.template
// TEMPLATE CLASS IMPLEMENTED: stack<Item> (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 <cassert> // Provides assert
#include "node2.h" // Node template class
namespace main_savitch_7B
{
template <class Item>
stack<Item>::stack(const stack<Item>& source)
// Library facilities used: node2.h
{
main_savitch_6B::node<Item> *tail_ptr; // Needed for argument of list_copy
list_copy(source.top_ptr, top_ptr, tail_ptr);
}
template <class Item>
void stack<Item>::push(const Item& entry)
// Library facilities used: node2.h
{
list_head_insert(top_ptr, entry);
}
template <class Item>
void stack<Item>::pop( )
// Library facilities used: cassert, node2.h
{
assert(!empty( ));
list_head_remove(top_ptr);
}
template <class Item>
void stack<Item>::operator =(const stack<Item>& source)
// Library facilities used: node2.h
{
main_savitch_6B::node<Item> *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 <class Item>
Item& stack<Item>::top( )
// Library facilities used: cassert
{
assert(!empty( ));
return top_ptr->data( );
}
template <class Item>
const Item& stack<Item>::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<Item>.
// The node_iterator is a forward iterators with two constructors:
// (1) A constructor (with a node<Item>* 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<Item>* .
//
// TYPEDEF for the node<Item> 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<Item>::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<Item>::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<Item> 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<int> *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<int> *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<Item> class:
// const Item& data( ) const <----- const version
// and
// Item& data( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is a reference to the data from this node.
//
// const node* link( ) const <----- const version
// and
// node* link( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is the link from this node.
//
// void set_data(const Item& new_data)
// Postcondition: The node now contains the specified new data.
//
// void set_link(node* new_link)
// Postcondition: The node now contains the specified new link.
//
// FUNCTIONS in the linked list toolkit:
// template <class Item>
// void list_clear(node<Item>*& 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 <class Item>
// void list_copy
// (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& 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 <class Item>
// void list_head_insert(node<Item>*& 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 <class Item>
// void list_head_remove(node<Item>*& 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 <class Item>
// void list_insert(node<Item>* 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 <class Item>
// size_t list_length(const node<Item>* 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 <class NodePtr, class SizeType>
// NodePtr list_locate(NodePtr head_ptr, SizeType position)
// The NodePtr may be either node<Item>* or const node<Item>*
// 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 <class Item>
// void list_remove(node<Item>* 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 <class NodePtr, class Item>
// NodePtr list_search
// (NodePtr head_ptr, const Item& target)
// The NodePtr may be either node<Item>* or const node<Item>*
// 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 <cstdlib> // Provides NULL and size_t
#include <iterator> // Provides iterator and forward_iterator_tag
namespace main_savitch_6B
{
template <class Item>
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 <class Item>
void list_clear(node<Item>*& head_ptr);
template <class Item>
void list_copy
(const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);
template <class Item>
void list_head_insert(node<Item>*& head_ptr, const Item& entry);
template <class Item>
void list_head_remove(node<Item>*& head_ptr);
template <class Item>
void list_insert(node<Item>* previous_ptr, const Item& entry);
template <class Item>
std::size_t list_length(const node<Item>* head_ptr);
template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position);
template <class Item>
void list_remove(node<Item>* previous_ptr);
template <class NodePtr, class Item>
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 Item>
class node_iterator
: public std::iterator<std::forward_iterator_tag, Item>
{
public:
node_iterator(node<Item>* 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<Item>* current;
};
template <class Item>
class const_node_iterator
: public std::iterator<std::forward_iterator_tag, const Item>
{
public:
const_node_iterator(const node<Item>* 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<Item>* 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 <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t
namespace main_savitch_6B
{
template <class Item>
void list_clear(node<Item>*& head_ptr)
// Library facilities used: cstdlib
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
template <class Item>
void list_copy(
const node<Item>* source_ptr,
node<Item>*& head_ptr,
node<Item>*& 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 <class Item>
void list_head_insert(node<Item>*& head_ptr, const Item& entry)
{
head_ptr = new node<Item>(entry, head_ptr);
}
template <class Item>
void list_head_remove(node<Item>*& head_ptr)
{
node<Item> *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link( );
delete remove_ptr;
}
template <class Item>
void list_insert(node<Item>* previous_ptr, const Item& entry)
{
node<Item> *insert_ptr;
insert_ptr = new node<Item>(entry, previous_ptr->link( ));
previous_ptr->set_link(insert_ptr);
}
template <class Item>
std::size_t list_length(const node<Item>* head_ptr)
// Library facilities used: cstdlib
{
const node<Item> *cursor;
std::size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
++answer;
return answer;
}
template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position)
// Library facilities used: cassert, cstdlib
{
NodePtr cursor;
SizeType i;
assert(0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); ++i)
cursor = cursor->link( );
return cursor;
}
template <class Item>
void list_remove(node<Item>* previous_ptr)
{
node<Item> *remove_ptr;
remove_ptr = previous_ptr->link( );
previous_ptr->set_link(remove_ptr->link( ));
delete remove_ptr;
}
template <class NodePtr, class Item>
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;
}
}
Explanation / Answer
#include<iostream>
#include<cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *link;
}*top;
/*
* Class Declaration
*/
class stack_list
{
public:
node *push(node *, int);
node *pop(node *);
void traverse(node *);
stack_list()
{
top = NULL;
}
};
/*
* Main: Contains Menu
*/
int main()
{
int choice, item;
stack_list sl;
while (1)
{
cout<<" -------------"<<endl;
cout<<"Operations on Stack"<<endl;
cout<<" -------------"<<endl;
cout<<"1.Push Element into the Stack"<<endl;
cout<<"2.Pop Element from the Stack"<<endl;
cout<<"3.Traverse the Stack"<<endl;
cout<<"4.Quit"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be pushed into the stack: ";
cin>>item;
top = sl.push(top, item);
break;
case 2:
top = sl.pop(top);
break;
case 3:
sl.traverse(top);
break;
case 4:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
/*
* Push Element into the Stack
*/
node *stack_list::push(node *top, int item)
{
node *tmp;
tmp = new (struct node);
tmp->info = item;
tmp->link = top;
top = tmp;
return top;
}
/*
* Pop Element from the Stack
*/
node *stack_list::pop(node *top)
{
node *tmp;
if (top == NULL)
cout<<"Stack is Empty"<<endl;
else
{
tmp = top;
cout<<"Element Popped: "<<tmp->info<<endl;
top = top->link;
free(tmp);
}
return top;
}
/*
* Traversing the Stack
*/
void stack_list::traverse(node *top)
{
node *ptr;
ptr = top;
if (top == NULL)
cout<<"Stack is empty"<<endl;
else
{
cout<<"Stack elements :"<<endl;
while (ptr != NULL)
{
cout<<ptr->info<<endl;
ptr = ptr->link;
}
}
}