Data structure and alogorithm

/** @file Stack.cpp * @brief implementation 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 implementation file contains the actual * implementation of the functions for the Stack ADT given for this assignment. */ #include <sstream> #include "Stack.hpp" //------------------------------------------------------------------------- // friend/helper functions of the Stack ADT /** Stack equivalence * Compare two given stacks to determine if they are equal or not. * stacks are equal if they are both of the same size, and each corresponding * item on each stack is equal at the same position on the stack. * This function relies on overloaded operator[] to access items on stack * by index for the comparison. * * @param rhs The stack on the right hand side of the boolean comparison * expression to compare this stack against to check for equivalence. * * @returns bool Returns true if the stacks are equal, and false otherwise. */ template <class T> bool Stack<T>::operator==(const Stack& rhs) const { // if number of items on the stacks don't match, then they can't // be equivalent if (this->size() != rhs.size()) { return false; } // otherwise need to check each item individually for (int index = 0; index < this->size(); index++) { if ((*this)[index] != rhs[index]) { return false; } } // if we get to this point, all items checked were equivalent, so // we are done and the answer is yes the stacks are equal return true; } /** Stack output stream operator * Friend function for Stack ADT, overload output stream operator to allow * easy output of stack representation to an output stream. * * @param out The output stream we are to stream additional output into. * @param aStack The Stack instance we are to stream a representation of * into the output stream given. * * @returns ostream& Returns a reference to the original output stream we * were given, but after we have inserted new values into the stream. */ template <typename U> ostream& operator<<(ostream& out, const Stack<U>& aStack) { out << aStack.tostring(); return out; } //------------------------------------------------------------------------- // AStack (array stack) member functions /** stack (array) constructor * Constructor for stack. Default to enough room for 100 items * * @param initialAlloc Initial space to allocate for stack, defaults to * 100. */ template <class T> AStack<T>::AStack(int initialAlloc) { allocSize = initialAlloc; topIndex = 0; items = new T[allocSize]; } /** stack (array) array constructor * Constructor for stack. Copy items from an array as initial items * on the stack. * * @param initItems An array of items to copy/push onto the stack. The item * at index 0 of the array will be the bottom of the stack, and the * last item will end up on the top. * @param length The total number of items in the array to copy/push onto * the new stack. */ template <class T> AStack<T>::AStack(T initItems[], int length) { allocSize = length; topIndex = 0; items = new T[allocSize]; // copy the init items to our block of memory. Also // we update the topIndex to use as our iterator index // and incidentally it will be correctly set to point to // the top of the stack once this copy is finished. for (topIndex = 0; topIndex < length; topIndex++) { items[topIndex] = initItems[topIndex]; } } /** stack (array) destructor */ template <class T> AStack<T>::~AStack() { // free up currently allocated memory delete [] items; } /** stack (array) clear * Function to initialize the stack back to an empty state. * Postcondition: topIndex = 0; isEmpty() == true */ template <class T> void AStack<T>::clear() { topIndex = 0; } /** stack (array) isEmpty * Determine whether stack is currently empty or not. * * @returns returns true if the stack is empty, otherwis * returns false. */ template <class T> bool AStack<T>::isEmpty() const { return topIndex == 0; } /** stack (array) push * Add newItem to the top of the stack. * Preconditon: The stack exists * Postcondition: The stack is changed and newItem is added to the top * of the stack. * @param newItem The new item to push on top of this stack. */ template <class T> void AStack<T>::push(const T& newItem) { // if stack is full, grow it if (topIndex == allocSize) { // double the current size allocSize = 2 * allocSize; // alloc the new space T* newItems = new T[allocSize]; // and copy the stack to the new storage space for (int index = 0; index < topIndex; index++) { newItems[index] = items[index]; } // free up the old space, start using the new space delete [] items; items = newItems; } // add the item, and increment our top items[topIndex] = newItem; topIndex++; } /** stack (array) top * Peek at and return the top element of the stack. * Preconditon: The stack exists and is not empty * Postcondition: If the stack is empty, we throw StackEmpty * exception; otherwise, the top element of the stack is * returned * * @param newItem The new item to push on top of this stack. * * @returns T Returns the top item of type T on the stack. */ template <class T> T AStack<T>::top() const { //assert(topIndex != 0); if (topIndex == 0) { throw EmptyStackException("AStack<T>::top()"); } else { return items[topIndex - 1]; } } /** stack (array) pop * Remove the top element from the stack. Some ADT combine pop * and top. We have two separate operations in this ADT. * Preconditon: The stack exists and is not empty. * Postcondition: If the stack is empty, we throw StackEmpty * exception; otherwise the top element of the stack is removed * from the stack. */ template <class T> void AStack<T>::pop() { // assert(topIndex != 0); if (topIndex == 0) { throw EmptyStackException("AStack<T>::pop()"); } else { topIndex--; } } /** Stack (array) size * Return the current size (number of items) on this stack. * * @returns int Returns the current stack size. */ template <class T> int AStack<T>::size() const { return topIndex; } /** Stack (array) tostring * Represent this stack as a string. * * @returns string Returns the contents of stack as a string. */ template <class T> string AStack<T>::tostring() const { ostringstream out; out << "--TopTop--" << endl; for (int index = topIndex- 1; index >= 0; index--) { out << items[index] << endl; } out << "--Bottom--" << endl; return out.str(); } /** Stack (array) indexing operator * Access internel elements of stack using indexing operator[]. * This is not a normal stack operation, we use mainly for testing * so that we can compare if two stack are equal at each internal * element of the stack. For this reason, this operator should * probably be private to the Stack class. * * @param index The index of the item onf the stack we want to access * and return, where index 0 represents the bottom of the stack and * index == size-1 is the top. * * @returns T Returns the item at "index" on the stack. */ template <class T> const T& AStack<T>::operator[](int index) const { // bounds checking, we will throw our stack exception if fails if (index < 0 || index >= topIndex) { throw InvalidIndexStackException("AStack<T>::operator[]"); } // otherwise we can directly access the asked for item from our items array else { return items[index]; } } //------------------------------------------------------------------------- // LStack (linked list stack) member functions /** stack (list) constructor * Default onstructor for linked list version of stack. */ template <class T> LStack<T>::LStack() { stackTop = NULL; numItems = 0; } /** stack (list) constructor * Alternate constructor to construct a stack from a given array * of values. The first item in the array should be the first item * pushed on stack, and thus ends up on the bottom of the stack. * * @param initItems An array of items to be used to initialize this Stack * with. * @param length The length or number of items in the initialization array * we were given. */ template <class T> LStack<T>::LStack(T initItems[], int length) { // make sure stack starts off empty before we start pushing the asked for // items onto the stack stackTop = NULL; numItems = 0; // we will reuse the push() functio to simply push all of the items in // the array onto this stack for (int idx = 0; idx < length; idx++) { push(initItems[idx]); } } /** stack (list) destructor * Destructor for linked list version of stack. */ template <class T> LStack<T>::~LStack() { clear(); } /** stack (list) clear * */ template <class T> void LStack<T>::clear() { Node<T>* temp; // iterate through Nodes in stack, freeing them up // as we visit them while (stackTop != NULL) { temp = stackTop; stackTop = stackTop->link; // dellocate this Node memory delete temp; } numItems = 0; } /** stack (list) isEmpty * Implement the base classes isEmpty member function to test if this * stack is currently empty or not. * * @returns bool Returns true if the list is empty, false if it is not. */ template <class T> bool LStack<T>::isEmpty() const { return stackTop == NULL; } /** stack (list) push * Push a new item onto the stack. Implement the base class virtual * push function. * * @param newItem The new item we are to push onto the top of this stack. */ template <class T> void LStack<T>::push(const T& newItem) { // dynamically allocate space for the new Node to hold // this newItem Node<T>* newNode = new Node<T>; // initialize the node newNode->item = newItem; newNode->link = stackTop; // now make this new node the new top of stack stackTop = newNode; numItems++; } /** stack (list) top * Impelmentation of the base class virtual top method. Access and return * a copy of the top element currently on this stack. * * @returns T Returns the top item of type T from the stack. */ template <class T> T LStack<T>::top() const { //assert(stackTop != NULL) if (stackTop == NULL) { throw EmptyStackException("LStack<T>::top()"); } else { return stackTop->item; } } /** stack (list) pop * Implement the base class virtual method to pop the top item from this * stack. */ template <class T> void LStack<T>::pop() { //assert(stackTop != NULL) if (stackTop == NULL) { throw EmptyStackException("LStack<T>::pop()"); } else { // keep track of the current top, so we can deallocate Node<T>* temp; temp = stackTop; // pop off the top stackTop = stackTop->link; // deallocate the old top now delete temp; // update size after removal numItems--; } } /** Stack (list) size * Return the current size (number of items) on this stack. * * @returns int Returns the current stack size. */ template <class T> int LStack<T>::size() const { return numItems; } /** stack (list) tostring * Represent this stack as a string. * * @returns string Returns the contents of stack as a string. */ template <class T> string LStack<T>::tostring() const { ostringstream out; Node<T>* temp = stackTop; out << "--TopTop--" << endl; while (temp != NULL) { out << temp->item << endl; temp = temp->link; } out << "--Bottom--" << endl; return out.str(); } /** Stack (list) indexing operator * Access internel elements of stack using indexing operator[]. * This is not a normal stack operation, we use mainly for testing * so that we can compare if two stack are equal at each internal * element of the stack. For this reason, this operator should * probably be private to the Stack class. * * @param index The index of the item on the stack we want to access * and return, where index 0 represents the bottom of the stack and * index == size-1 is the top. * * @returns T Returns the item at "index" on the stack. */ template <class T> const T& LStack<T>::operator[](int index) const { // bounds checking, we will throw our stack exception if fails if (index < 0 || index >= numItems) { throw InvalidIndexStackException("LStack<T>::operator[]"); } // otherwise we will have to search our list for the desired item // we will search backwards, so the stackTop node is at index // numItems-1, and we iterate back through the list till we // arrive at index else { int currentIndex = numItems - 1; Node<T>* currentNode = stackTop; while (currentIndex != index) { currentIndex--; currentNode = currentNode->link; } return currentNode->item; } }