This assignment is an exercise in implementing the stack ADT using an array-base
ID: 3553308 • Letter: T
Question
This assignment is an exercise in implementing the stack ADT using an array-based data structure. This assignment also introduces C++ exception handling.
This program creates and implements a class to represent the Stack ADT using a dynamic array.
A driver program is provided for this assignment to test your implementation. You don't have to write the tests.
You will need to write a single class for this assignment, the Stack class. You will need to implement several methods and functions associated with this class.
The class should be implemented as two separate files. The class definition should be placed in an appropriately named header (.h) file. The implementations of the class methods and any other associated functions should be placed in a separate .cpp file for the class.
Data members
This class contains a dynamically allocated array of integer data values (the stack array). Because the array is allocated dynamically, an unsigned integer value is also maintained inside the class to determine the maximum number of elements that may be stored in the array (the stack capacity). The class also requires one other unsigned integer data member: the number of data items currently stored in the stack (the stack size). Don't give these data members the same names as methods of the class.
You may also choose to have a data member to keep track of the subscript of the top item in the stack (the stack top subscript). Since the subscript of the top item is always equal to the stack size - 1, doing so is optional, but if you make this a separate data member it should be an integer.
Methods and associated functions
As usual, methods that do not alter the data members of the object that called the method should be declared to be const.
Constructor
The class should have a default constructor that takes no arguments. The constructor should set the stack capacity and stack size to 0, and the stack array pointer to NULL.
Destructor
The class should have a destructor that deletes the dynamic memory for the stack array.
Copy constructor
The class should also have a proper copy constructor. This will be similar to the copy constructor you wrote for the MyString class for Assignment 4. You will need to account for the possibility that the existingStack object used to initialize the new Stack may have a capacity of 0 (and therefore a stack array pointer that is NULL).
operator=
The assignment operator should be properly overloaded to allow one Stack to be assigned to another. Once again, the code here will be similar to what you wrote for Assignment 4. You will need to account for the possibility that the right operand Stack may have a capacity of 0 (and therefore a stack array pointer that is NULL).
void Stack::clear()
This method should set the stack size to 0. It should not change the stack capacity or the stack array.
size()
This method is essentially the same as in Assignment 4.
capacity()
This method is essentially the same as in Assignment 4.
empty()
This method is essentially the same as in Assignment 4.
int Stack::top() const throw(out_of_range)
This method takes no arguments and returns an integer. If the stack is empty, this method should throw an out_of_range exception, like so:
Otherwise, the method should return the top element of the stack array (the one at the stack size - 1).
void Stack::push(int item)
This method takes an integer argument, the item to insert into the stack. If the stack is full (the stack size is equal to the stack capacity), this method will need to call the reserve() method to increase the capacity of the stack array and make room for the item to insert. If the stack capacity is currently 0, pass a new capacity of 1 to the reserve() method. Otherwise, pass a new capacity of twice the current stack capacity to thereserve() method..
void Stack::pop() throw(out_of_range)
This method takes no arguments and returns nothing. If the stack is empty, this method should throw an out_of_range exception. Otherwise, it should decrement the stack size to effectively remove the top item in the stack array. No changes need be made to the stack array contents.
void Stack::reserve(unsigned int newCapacity)
This method increases the capacity of the stack array. It takes a single unsigned integer argument, the new capacity. The logic for this method should look something like this:
ostream& operator<<(ostream& leftOp, const Stack& rightOp)
The output operator should be overloaded so that a Stack can be printed on the standard output. As in Assignment 4, this will need to be a standalone friend function rather than a method.
The items stored in the stack should be printed starting with the first array element (subscript 0) and ending with the last valid element (subscript stack size - 1). Print a space after each stack element.
A driver program, assign5.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/Spring2014/Assign5/assign5.cpp.
Explanation / Answer
To this point in your programming experience (assumed restricted to this course), you have written all your code in a single file. It contained the main function, the prototypes, system includes, extra functions... everything! It turns out that this is not the best way to put together a (large)programming project. In order to make your program more organized, secure, portable, modifiable and faster to recompile, you will now learn how to break up your programming project into multiple files. Many of the reasons I just cited I cannot expound upon due to time and information overload, but in time you will learn. Here and now we will see how this is done, some reasons to do it, and how it affects your call to the compiler. Initially, your programs will be comprised of 3 files: a