Practice Questions

Given the following ADT definition of a stack to use: /** 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. * * @returns int The current size (number of items) on the stack. */ virtual int size() const = 0; }; perform the following tasks by writing code that uses a stack to accomplish the task. You will need to create a stack of the needed type, then use the methods of the stack abstraction (push, top, pop, etc.) to solve the given task asked for. Question 7 (5 points) Given a stack of integers, calculate the sum of the integer values. Also, the stack should still be unchanged after you have calculated the sum Hint: take the items off the stack to sum them up and keep them on a second temporary stack so you can put them all back on after you have calculated the sum. ANSWER FOR NUMBER 7: int sumStackOfIntegers(Stack<int> currentStack) { Stack<int> tempStack; int sum = 0; while(!currentStack.isEmpty()) { int temp = currentStack.top(); tempStack.push(temp); currentStack.pop(); sum += temp; } while(!tempStack.isEmpty()) { int temp = tempStack.top(); currentStack.push(temp); tempStack.pop(); } return sum; } Stack Implementation Given the following linked list implementation of a Stack ADT (this is the same implementation you used in Assignment 10), add the asked for additional member methods to the linked list stack implementation. /** 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; 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; } Question 9 (10 points) Saved In our usual stack abstraction we normally do not want or need to delete from the middle of the stack. But lets say we have a special case where we need a method to search for and remove items somewhere in the stack. Write the following member function that takes an item of type T to search for, and searches from the top of the linked list structure of our LStack, and removes the first such item it finds. For this question, if the item is not found you can simply ignore the request, or print out an error message. As a hint, you may want to treat it as a special case if the searchItem is at the top of the stack, and use the pop() method in that case, otherwise you need to search through the list, possibly using a current and previous pointer, and remove the node if you find one with the matching item (and don't forget to free up the nodes memory if you find and delete it). Here is the prototype for the member function you are to implement: /** stack (list) search for item and remove * Search from the top of the stack for the indicated item, and remove * the item from the stack if it is found. * * @param searchItem The item to search for and remove if found */ template <class T> void LStack<T>::removeItemFromStack(const T& searchItem) { } ANSWER FOR QUESTION NUMBER 9: IS IT RIGHT OR WRONG? template <class T> void LStack<T>::removeItemFromStack(const T& searchItem) { if (this->stackTop == searchItem) { if (stackTop->link == NULL) { return; } T.pop(T.top()); stackTop->item = stackTop->link->item; searchItem = stackTop->link; stackTop->link = stackTop->link->link; free(searchItem); return; } Node<T>* prev = stackTop; while (prev->link != NULL && prev->link != searchItem) { prev = prev->link; if (prev->link == NULL) { return; } prev->link = prev->link->link; free(searchItem); return; } }