Using C++ to program

A stack is a Last In First Out (LIFO) data structure. It is one of the basic data structures used in programming. A stack is fundamental to how local variables of a function are allocated and how functions are called. There are three core operations performed by a stack:

push - adds an element to the stack

pop - removes an element from the stack

peek - returns the last element added to the stack

In addition, other operations such as size and is_empty may be supported.

-----------------------------------------------------------------------------------------------------

You will implement a templated stack to allow the stack to store whatever type you need. When implementing a stack, one of the basic decisions is how to store the elements and there are two primary approaches. The first option is to store each element in a node by itself and manage links, just like a linked list. The second is to store the elements in an array. You will use the second option.

Your stack needs to support the following public operations:

void push(T item) - Adds an element to the stack

void pop() - Removes the last added element to the stack. If the stack is empty, nothing should happen.

const T &peek() const - Returns the last added element to the stack. If the stack is empty, an exception of type std::out_of_range should be thrown.

T &peek() - Returns the last added element to the stack. If the stack is empty, an exception of type std::out_of_range should be thrown.

int size() const - Returns the number of elements in the stack

bool is_empty() const - Returns whether there are any elements in the stack

int capacity() const - Returns the number of potential elements that can be stored before a reallocation is triggered.

In addition you will want to write various private functions to help facilitate the above commands and store whatever variables you deem necessary.

Behind the scenes you will need to manage a dynamically allocated array that stores the elements. If a push would add an element to the stack beyond what can currently be stored, the stack should grow. In particular the a new array twice the size of the existing array should be created and all the existing elements copied to the new array. Then the original array should be properly disposed of.

As always, you must satisfy the Rule of Zero / Three / Five as appropriate. For this assignment, the Rule of Three is not an option.

Finally, you may not use a std::vector or other type provided by the standard library. You need to manage the memory manually using pointers.

Your final submission should include a fully working stack that is thoroughly tested. When executed it should perform the various tests. The exact output is not important.

-----------------------------------------------------------------------------------------------------

Testing

Because this is a templated type, your testing is essential. You need to test the behavior of all of the functions completely for at least two different types (int and string are recommended). This means you need to check things like push/pop as they transition across a reallocation boundary, exceptions are thrown when appropriate, and state querying functions like size and is_empty are always correct.

Note that there are two different peek functions you need to implement. Ensure your tests are testing both methods completely.

Be aware, part of the testing must include all constructors, operators, and so forth. It is not limited to just the explicitly mentioned functions above.