Data structure and alogorithm

/** @file Stack.hpp * @brief header file for Stack class for Assignment 09 using stacks. * * @author Derek Harter * @note cwid : 123 45 678 * @note class: COSC 2336, Summer 2020 * @note ide : Atom Text Editor 1.46.0 / build package / GNU gcc tools * @note assg : Assignment 09 * @date June 1, 2020 * * NOTE: Do not edit this file for Assignment 09. You are to use the Stack * ADT as given for the assignment. * * Assignment 09 using stacks. Use the given Stack ADT to implement a set of * functions/algorithms. This header file contains the declaration of the Stack * class container that defines the ADT abstraction for Stacks to use for this * assignment. */ #include <iostream> using namespace std; #ifndef _STACK_H_ #define _STACK_H_ //------------------------------------------------------------------------- /** stack (base class) * The basic definition of the Stack Abstract Data Type (ADT) * and stack operations. All declared functions here are * virtual, they must be implemented by concrete derived * classes. */ template <class T> class Stack { public: /** clear * Method to clear out or empty any items on stack, * put stack back to empty state. * Postcondition: Stack is empty. * * @returns void Nothing returned */ virtual void clear() = 0; /** isEmpty * Function to determine whether the stack is empty. Needed * because it is undefined to pop from empty stack. This * function will not change the state of the stack (const). * * @returns bool true if stack is empty, false otherwise. */ virtual bool isEmpty() const = 0; /** push * Add a new item onto top of stack. * * @param newItem The item of template type T to push on top of * the current stack. * * @returns void Nothing is returned */ virtual void push(const T& newItem) = 0; /** top * Return the top item from the stack. Note in this ADT, peeking * at the top item does not remove the top item. Some ADT combine * top() and pop() as one operation. It is undefined to try and * peek at the top item of an empty stack. Derived classes should * throw an exception if this is attempted. * * @returns T Returns the top item from stack. */ virtual T top() const = 0; /** pop * Remove the item from the top of the stack. It is undefined what * it means to try and pop from an empty stack. Derived classes should * throw an exception if pop() from empty is attempted. * * @returns void Returns nothing */ virtual void pop() = 0; /** size * Accessor method to provide the current size of the stack. * * @returns int Returns the current stack size as an int. */ virtual int size() const = 0; /** tostring * Represent stack as a string * * @returns string Returns a string representation of the items on * this stack. */ virtual string tostring() const = 0; // operload operators, mostly to support boolean comparison between // two stacks for testing bool operator==(const Stack<T>& rhs) const; /** operator indexing * Virtual function for implementation of operator indexing. Subclasses * must implement this function. * * @param index The index into the Stack of the item we want to access. * * @returns T& Returns a reference to the indexed item. */ virtual const T& operator[](int index) const = 0; // overload output stream operator for all stacks using tostring() template <typename U> friend ostream& operator<<(ostream& out, const Stack<U>& aStack); }; //------------------------------------------------------------------------- /** Empty stack exception * Class for empty stack exceptions */ class EmptyStackException { private: /// @brief Additional error message information associated with this /// empty stack exception. string message; public: /** default constructor * Default construction of an empty stack exception object. */ EmptyStackException() { message = "Error: operation on empty stack"; } /** string constructor * Constructor for empty stack exception to add additional information to * the exception message. * * @param str The string with additional error information for this exception * to use. */ EmptyStackException(string str) { message = "Error: " + str + " attempted on emtpy stack"; } /** what accessor * Access the empty stack exception error message. * * @returns string Returns what the error message associated with this * empty stack excpetion is. */ string what() { return message; } }; //------------------------------------------------------------------------- /** InvalidIndex stack exception * Class for InvalidIndex stack exceptions */ class InvalidIndexStackException { private: /// @brief Additional error message information associated with this /// invalid index stack exception. string message; public: /** default constructor * Default construction of an invalid index stack exception object. */ InvalidIndexStackException() { message = "Error: invalid index attempted on stack"; } /** string constructor * Constructor for invalid index stack exception to add additional * information to the exception message. * * @param str The string with additional error information for this exception * to use. */ InvalidIndexStackException(string str) { message = "Error: " + str + " invalid index reference on stack"; } /** what accessor * Access the invalid index stack exception error message. * * @returns string Returns what the error message associated with this * invalid index stack excpetion is. */ string what() { return message; } }; //------------------------------------------------------------------------- /** stack (array implementation) * Implementation of the stack ADT as a fixed array. This implementation * uses dynamic memory allocation, and demonstrates doubling the size * of the allocated space as needed to grow stack. */ template <class T> class AStack : public Stack<T> { private: /// @brief The amount of memory currently allocated for this stack. int allocSize; /// @brief The index pointing to top item location on stack array. The /// stack grows from 0 up, so the top also indicates the current size /// of the stack. int topIndex; /// @brief The items on the stack. This is a dynamically allocated array /// that can grow if needed when stack exceeds current allocation. T* items; public: AStack(int initialAlloc = 100); // constructor AStack(T initItems[], int length); ~AStack(); // destructor void clear(); bool isEmpty() const; void push(const T& newItem); T top() const; void pop(); int size() const; string tostring() const; const T& operator[](int index) const; }; //------------------------------------------------------------------------- /** Node * A basic node contaning an item and a link to the next node in * the linked list. */ template <class T> struct Node { /// @brief The item of type T held in this linked list node T item; /// @brief link A pointer to the next node in the linked list data structure Node<T>* link; }; /** stack (linked list implementation) * Implementation of the stack ADT as a dynamic linked list. This implementation * uses link nodes and grows (and shrinks) the nodes as items popped and pushed * onto stack. */ template <class T> class LStack : public Stack<T> { private: /// @brief A pointe to our current top stack item node. This will be NULL /// if the stack is currently empty. Node<T>* stackTop; /// @brief The number of items currently on this stack. Should be 0 when this /// stack is empty. int numItems; public: LStack(); // default constructor LStack(T initItems[], int length); ~LStack(); // destructor void clear(); bool isEmpty() const; void push(const T& newItem); T top() const; void pop(); int size() const; string tostring() const; const T& operator[](int index) const; }; // include template implementations so they are included with header #include "Stack.cpp" #endif // _STACK_H_