This assignment is an exercise in implementing the stack ADT using a singly-link
ID: 3819450 • Letter: T
Question
This assignment is an exercise in implementing the stack ADT using a singly-linked list. This assignment also introduces the concept of templates.
Assignment
This program creates and implements a class to represent the Stack ADT using a singly-linked list.
A driver program is provided for this assignment to test your implementation. You don't have to write the tests.
Program
You will need to write one template structure and one template class for this assignment, called Node and Stack. You will need to implement several methods and functions associated with these data types.
Since these are both C++ templates and are closely related to each other, all of your code should be placed in a single header (.h) file. This includes the implementations of all methods and any other associated functions.
struct Node
Data members
This template structure should have two data members: a member of the template parameter type to store an item to be inserted into the stack, and a pointer to a Node. This pointer, next, will point to the next node in the linked list (or be nullptr if this is the last node in the list).
Since the Stack class will need access to these data members, make them public (which is the default for a struct).
Methods
Constructor
The structure should have a constructor that can be used to initialize the data members of the stack node.
class Stack
Data members
This class should have two data members. The first is a pointer to an Node. This pointer, stkTop, will point to the first node in the list, i.e. the top node in the stack (or will be nullptr if the stack is empty). The second data member should be an size_t or unsigned integer that will be used to store the stack size, the number of items currently stored in the stack.
Methods and associated functions
Constructor
The class should have a default constructor that takes no arguments. The constructor should set stkTop to nullptr and set the stack size to 0.
Destructor
The class should have a destructor. The destructor can simply call the clear() method described below.
Copy constructor
The class should also have a proper copy constructor.
operator=
The assignment operator should be properly overloaded.
operator<<
The output operator should be overloaded so that an entire Stack can be sent to the standard output. As usual, this function will need to be a friend rather than a method. Declaring a template function to be a friend of a template class requires some special syntax - see the Implementation Hints below.
clear()
This method takes no arguments and returns nothing. It should properly set the stack back to the empty state. That means deleting all of the nodes in the stack, setting the top pointer back to nullptr, and setting the stack size back to 0. One easy way to accomplish this is to repeatedly pop until the stack is empty.
size()
This method takes no arguments and returns an unsigned integer or size_t. It should return the stack size; i.e., the number of data items currently stored in the stack.
empty()
Returns true if there are no data items currently stored in the stack; otherwise returns false.
top()
This method takes no arguments and returns a reference to a constant item of the template parameter type. It should return the data stored in the top node of the stack (i.e., the first node in the linked list). You may assume this method will not be called if the stack is empty.
push()
This method takes a reference to a constant item of the template parameter type as its argument (the item to insert into the stack). It returns nothing. The method should insert the item at the top of the stack (at the front of the linked list).
pop()
This method takes no arguments and returns nothing. It should remove the node at the top of the stack. You may assume this method will not be called if the stack is empty.
If you like, you may write private methods for the Stack class in addition to the methods described above. For example, you may want to write a copyList() method that can be called by both the copy constructor and overloaded assignment operator to make a copy of the linked list.
Driver Program
A driver program, assign7.cpp is provided for this assignment. The purpose of a driver program is to test other pieces that you code. You do not need to write the driver program yourself. A copy of the driver program can also be found on turing at /home/turing/t90kjm1/CS241/Code/Spring2017/Assign7/assign7.cpp.
Output
Output from the correctly functioning driver program should look like the following:
Implementation Hints
Implement this similarly to the last assignment. Start off at the beginning of the driver program and try to get it working piece by piece. Maintain a working program as you go.
Declaring a template function to be a friend of a template class is one of the classic "gotcha's" in C++. We are trying to declare a function to be a friend of all classes that might be instantiated from the Stack template class, and most C++ compilers will quite properly refuse to do that without some special syntax.
The friend declaration must contain an extra set of <> to indicate that it is a template function (however, do not code this in the actual function definition - only the friend declaration). You'll also usually need to forward declare both the template class and the template function, as shown below.
How much of this you actually need to do can vary from compiler to compiler, but the code shown below should work in Quincy, Dev-C++, and with g++ on turing/hopper.
Explanation / Answer
Stack.cpp
/**************************************************************
FILE: Stack.cpp
PURPOSE: This program creates and implements a class to
represent the Stack ADT using an array.
***************************************************************/
#include "Stack.h"
/***************************************************************
FUNCTION: Stack()
USE: The class has a default constructor that takes
no arguments. The constructor should set the stack's initial
capacity to 8 and dynamically allocate an array of integers
of that capacity. The stack size should be initialized to 0.
The stack top subscript should be initialized to -1.
ARGUMENTS: None.
***************************************************************/
Stack::Stack()
{
stackCapacity = 8;//initial stack Capacity
stackAR = new int[stackCapacity];//allocate array
stackSize = 0;//empty array
stackTop = -1;
}
/***************************************************************
FUNCTION: ~Stack()
USE: The destructor for the Stack class should use the
delete[] operator to delete the stack array.
ARGUMENTS: N/A
***************************************************************/
Stack::~Stack()
{
delete [] stackAR;
}
/***************************************************************
FUNCTION: Stack(const Stack&)
USE: This "copy constructor" for the Stack class should
initialize a new Stack object to the same data as the
existing Stack object s.
ARGUMENTS: s: the Stack object to be intialized as a new
Stack object.
***************************************************************/
Stack::Stack(const Stack& s)
{
stackSize = s.stackSize;//size equal to arg object size
stackAR = new int[stackCapacity];//stack array
stackCapacity = s.stackCapacity;//capacity equal to arg
//object capacity
for(int i = 0; i < stackSize; i++)
{
stackAR[i] = s.stackAR[i];
}//copy arg object array
}
/***************************************************************
FUNCTION: operator=(const Stack& rightOp)
USE: This overloaded assignment operator should assign one
Stack object (the object rightOp) to another (the object
that called the method, which is pointed to by this).
ARGUMENTS: rightOp: Stack object to be passed in.
RETURNS: Stack object of calling object
*
***************************************************************/
Stack& Stack::operator=(const Stack& rightOp)
{
if(&rightOp != this)//if addresses not equal
{
delete[] stackAR;
stackSize = rightOp.stackSize;//size equals arg size
stackCapacity = rightOp.stackCapacity;//capacities equal
stackTop = rightOp.stackSize - 1;//top subs equal //arg capacity
stackAR = new int[stackCapacity];//allocate array
for(int i = 0; i < stackSize; i++)
{
stackAR[i] = rightOp.stackAR[i];
}//copy arg array
}
return *this;//calling object
}
/***************************************************************
FUNCTION: clear()
USE: This method should properly set the stack back to the empty
state (set the stack size to 0 and the stack top subscript to -1).
ARGUMENTS: N/A
RETURNS: N/A
***************************************************************/
void Stack::clear()
{
stackSize = 0;//empty array
stackTop = -1;
}
/***************************************************************
FUNCTION: size()
USE: This method should return the stack size.
ARGUMENTS: N/A
RETURNS: stackSize: the stack size
***************************************************************/
int Stack::size() const
{
return stackSize;
}
/***************************************************************
FUNCTION: empty()
USE: This method should return true if the stack size is 0
otherwise it should return false.
ARGUMENTS: N/A
RETURNS: bool value
***************************************************************/
bool Stack::empty() const
{
if(stackSize == 0)//if empty
return true;
else//if not empty
return false;
}
/***************************************************************
FUNCTION: top()
USE: If the stack is empty, this method should throw an
out_of_range exception. Otherwise, it should return the top
element of the stack array (the one at the stack top subscript).
ARGUMENTS: N/A
RETURNS: bool value
***************************************************************/
int Stack::top() const
{
if(stackSize == 0)//if empty
throw out_of_range("Stack underflow on top()");
else//if not empty
return stackAR[stackTop];
}
/***************************************************************
FUNCTION: push(int)
USE: The method should increment the stack top subscript
and then copy the method argument into the stack array as the
new top item in the stack. The stack size should be incremented
by 1.
ARGUMENTS: N/A
RETURNS: N/A
***************************************************************/
void Stack::push(int item)
{
if((stackSize == stackCapacity))//if array needs resizing
{
stackCapacity = stackCapacity * 2 ;//double array capacity
int * tempAR;//new temp pointer to int
tempAR = new int[stackCapacity];//allocate array
for(int i = 0; i < stackSize; i++)
{
tempAR[i] = stackAR[i];
}//copy arg array
delete [] stackAR;//remove array
stackAR = tempAR; //set array to address of temp array
}
//insert new item into stack
stackTop++;
stackAR[stackTop] = item;
stackSize++;
}
/***************************************************************
FUNCTION: pop()
USE: If the stack is empty, this method should throw an
out_of_range exception. Otherwise, it should decrement the
stack top subscript to effectively remove the top item in
the stack array. The stack size should be decremented by 1.
ARGUMENTS: N/A
RETURNS: N/A
***************************************************************/
void Stack::pop()
{
if(stackSize == 0)//if empty
throw out_of_range("Stack underflow on pop()");
else//if not empty
{
//remove top element of stack
stackTop--;
stackSize--;
}
}
//stand alone functions
/***************************************************************
FUNCTION: operator<<(ostream& leftOp, const Stack& rightOp)
USE: This method should print the array stored in the
array of the Stack object passed in as rightOp using the
stream object passed in as leftOp.
ARGUMENTS: leftOp - stream object being passed in.
rightOp - Stack object being passed in.
RETURNS: leftOp: ostream object reference.
***************************************************************/
ostream& operator<<(ostream& leftOp, const Stack& rightOp)
{
for(int i = 0; i < rightOp.size(); i++)
{
//print stack as standard output
leftOp << rightOp.stackAR[i] << ' ';
}
return leftOp;
}
_________________________________________________________________________________________________________________
Stack.h
#ifndef Stack_H
#define Stack_H
#include <iostream>
#include <stdexcept>
using namespace std;
/**************************************************************
FILE: Stack.h
PURPOSE: Contains the declaration for the Stack class.
***************************************************************/
class Stack
{
//friend declarations
friend ostream& operator<<(ostream&, const Stack&);//output operator
private:
// Data members
int * stackAR;
int stackCapacity;
int stackSize;
int stackTop;
public:
//constructors
Stack();
//destructor
~Stack();
//copy constructor
Stack(const Stack& s);
//operator overloads
Stack& operator=(const Stack& rightOp); //assignment operator
//methods
void clear();
int size() const;
bool empty() const;
int top() const;
void push(int item);
void pop();
};
#endif
___________________________________________________________________________________________________________________
assign7.cpp
/*********************************************************************
PROGRAM: CSCI 241 Assignment 7
FUNCTION: This program tests the functionality of the MyString
class.
*********************************************************************/
#include <iostream>
#include <stdexcept>
#include "Stack.h"
using std::cin;
using std::cout;
using std::endl;
using std::out_of_range;
int main()
{
cout << "Testing default constructor ";
Stack s1;
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing push() ";
for (int i = 10; i < 80; i+= 10)
s1.push(i);
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
for (int i = 15; i < 85; i+= 10)
s1.push(i);
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing copy constructor() ";
Stack s2 = s1;
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing top() ";
cout << "Top item of s1: " << s1.top() << endl << endl;
cout << "Testing pop() Top item of s1: ";
while (!s1.empty())
{
cout << s1.top() << ' ';
s1.pop();
}
cout << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
cout << "Testing assignment operator ";
Stack s3;
s3 = s2;
cout << "s2 (size " << s2.size() << "): " << s2 << endl;
cout << "s3 (size " << s3.size() << "): " << s3 << endl << endl;
cout << "Testing clear() ";
s2.clear();
cout << "s2 (size " << s2.size() << "): " << s2 << endl;
cout << "s3 (size " << s3.size() << "): " << s3 << endl << endl;
cout << "Testing assignment to self and swap ";
s3 = s3;
s2 = s3;
s3.clear();
cout << "s2 (size " << s2.size() << "): " << s2 << endl;
cout << "s3 (size " << s3.size() << "): " << s3 << endl << endl;
cout << "Testing chained assignment ";
Stack s4;
s4 = s3 = s2;
cout << "s2 (size " << s2.size() << "): " << s2 << endl;
cout << "s3 (size " << s3.size() << "): " << s3 << endl;
cout << "s4 (size " << s4.size() << "): " << s4 << endl << endl;
cout << "Testing const correctness ";
const Stack& r4 = s4;
cout << "s4: " << r4 << endl;
cout << "s4 size: " << r4.size() << endl;
cout << "s4 is " << ((r4.empty()) ? "empty " : "not empty ");
cout << "Top item of s4: " << r4.top() << endl << endl;
s1 = r4;
cout << "s1: " << s1 << endl;
cout << "s1 size: " << s1.size() << endl;
cout << "s1 is " << ((s1.empty()) ? "empty " : "not empty ");
cout << endl;
s1.clear();
cout << "Testing top() with empty stack ";
try
{
cout << s1.top() << endl;
}
catch (out_of_range orex)
{
cout << "Exception: "<< orex.what() << endl << endl;
}
cout << "Testing pop() with empty stack ";
try
{
s1.pop();
}
catch (out_of_range orex)
{
cout << "Exception: "<< orex.what() << endl;
}
return 0;
}
______________________________________________________________________________________________________
makefile
#
# PROGRAM: assign7
#
# Compiler variables
CCFLAGS = -ansi -Wall
# Rule to link object code files to create executable file
assign7: assign7.o Stack.o
g++ $(CCFLAGS) -o assign7 assign7.o Stack.o
# Rules to compile source code files to object code
assign7.o: assign7.cpp Stack.h
g++ $(CCFLAGS) -c assign7.cpp
Stack.o: Stack.cpp Stack.h
g++ $(CCFLAGS) -c Stack.cpp
# Pseudo-target to remove object code and executable files
clean:
-rm *.o assign7