Stack coding

/** * @author Derek Harter * @cwid 123 45 678 * @class COSC 2336, Spring 2019 * @ide Visual Studio Community 2017 * @date January 18, 2019 * @assg C++ Stacks videos * * @description A Stack ADT with two concrete impelementation * examples: an array based stack implementaiton (AStack), and * a linked list based implementation (LStack). */ #include <iostream> #include <string> #include <sstream> using namespace std; //------------------------------------------------------------------------- /** 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. */ 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. */ 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. */ virtual void pop() = 0; /** size * Accessor method to provide the current size of the stack. */ virtual int size() const = 0; /** tostring * Represent stack as a string */ virtual string tostring() const = 0; // operload operators, mostly to support boolean comparison between // two stacks for testing bool operator==(const Stack<T>& rhs) const; 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); }; /** 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. */ template <typename U> ostream& operator<<(ostream& out, const Stack<U>& aStack) { out << aStack.tostring(); return out; } //------------------------------------------------------------------------- /** Empty stack exception * Class for empty stack exceptions */ class EmptyStackException { private: string message; public: EmptyStackException() { message = "Error: operation on empty stack"; } EmptyStackException(string str) { message = "Error: " + str + " attempted on emtpy stack"; } string what() { return message; } }; //------------------------------------------------------------------------- /** InvalidIndex stack exception * Class for InvalidIndex stack exceptions */ class InvalidIndexStackException { private: string message; public: InvalidIndexStackException() { message = "Error: invalid index attempted on stack"; } InvalidIndexStackException(string str) { message = "Error: " + str + " invalid index reference on stack"; } 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. * * @var allocSize The amount of memory currently allocated for this stack. * @var topIndex 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. * @var items The items on the stack. This is a dynamically allocated array that * can grow if needed when stack exceeds current allocation. */ template <class T> class AStack : public Stack<T> { private: int allocSize; // amount of memory allocated int topIndex; // index to top item on stack, stack 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; }; /** 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 items 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. */ 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]; } } //------------------------------------------------------------------------- /** Node * A basic node contaning an item and a link to the next node in * the linked list. */ template <class T> struct Node { T item; 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> { public: LStack(); // default constructor ~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; private: Node<T>* stackTop; int numItems; }; /** stack (list) constructor * Constructor for linked list version of stack. */ template <class T> LStack<T>::LStack() { stackTop = NULL; numItems = 0; } /** 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 * */ template <class T> bool LStack<T>::isEmpty() const { return stackTop == NULL; } /** stack (list) push * */ 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 * */ 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 * */ 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; } }