You will implement a Stack class for this project. Your Stack class must utilize a dynamic allocated double-linked sequence of nodes to store data values (integers) that have been pushed on to the stack. Each node in the doubly-linked sequence must contain both a next pointer which holds the address of the nodes successor and a previous pointer which holds the address of the nodes predecessor.
Struct Node // Node data type for storing a single stack entry { Node *previous; //Holds the address of the predecessor node Node *next; //Holds the address of the successor node int data; // Holds the data value };
[next NULL topPt 5 15 NULL previous]
To implement the stack class, stack.h and main.cpp is given. Your task is to complete the stack.cpp file.
This is the main.cpp code given
// // main.cpp-- Stacks // // Driver program for Stack ADT -- The text files (read by this code) contain a series of commands // that will help you test your Stack ADT code by triggering various Stack class methods. // // DO NOT MODIFY OR SUBMIT THIS FILE // #include #include #include #include #include "stack.h" using namespace std; int main(int argc, char* argv[]) { ifstream inputs; // Input file for commands char op; // Hold operation and optional char input int value; // Value input from file string comment; // Holds comment from file Stack* sPtr = NULL; // Will point to stack object // Output usage message if one input file name is not provided if (argc != 2) { cout << "Usage: project03 "; return 1; } // Attempt to open input file -- terminate if file does not open inputs.open(argv[1]); if (!inputs) { cout << "Error - unable to open input file" << endl; return 1; } // Input and echo header comment from file getline(inputs, comment); // Input and echo the comment appearing in the test file cout << endl << '#' << comment << endl; // Process commands from input file inputs >> op; // Attempt to input first command while (inputs) { switch (op) // Process operation input from file { case '#': // Test file comment getline(inputs, comment); // Input and echo the comment appearing in the test file cout << '#' << comment << endl; break; case 'c': // Constructor cout << endl << "Stack( )"; try { sPtr = new Stack( ); // Attempt to create an empty stack object cout << " -- Successful" << endl; } catch ( std::bad_alloc ) { cout << "Failed : Terminating now..." << endl; return 1; } break; case '+': // Push inputs >> value; cout << "Push(" << value << ")"; try { sPtr->Push(value); cout << " -- successful"; } catch (StackFull) { cout << " -- Failed Full Stack"; } cout << endl; break; case '-': // Pop cout << "Pop() -- "; try { sPtr->Pop(); cout << "successful"; } catch (StackEmpty) { cout << "Failed Empty Stack"; } cout << endl; break; case 'f': // IsFull cout << "IsFull() -- "; try { if (sPtr->IsFull()) cout << "true"; else cout << "false"; } catch ( ... ) { cout << "operation failed"; } cout << endl; break; case 'e': // IsEmpty cout << "IsEmpty() -- "; try { if (sPtr->IsEmpty()) cout << "true"; else cout << "false"; } catch ( ... ) { cout << "operation failed"; } cout << endl; break; case 'm': // Make Empty sPtr->MakeEmpty(); cout << "MakeEmpty()" << endl; break; case 'p': // Print Stack cout << "Print() -- "; sPtr->Print(); break; case 't': // Top of Stack try { cout << "Top() -- " << sPtr->Top() << endl; } catch (StackEmpty) { cout << "Top() -- Failed Empty Stack" << endl; } break; case '>': // Max value within Stack try { cout << "Max() -- " << sPtr->Max() << endl; } catch (StackEmpty) { cout << "Max() -- Failed Empty Stack" << endl; } break; case '<': // Min value within Stack try { cout << "Min() -- " << sPtr->Min() << endl; } catch (StackEmpty) { cout << "Min() -- Failed Empty Stack" << endl; } break; case '?': // Peek(n) Stack inputs >> value; try { cout << "Peek(" << value << ") -- " << sPtr->Peek(value) << endl; } catch (StackInvalidPeek) { cout << "Peek(" << value << ") -- Failed Invalid Peek" << endl; } break; case 's': // Size of Stack cout << "Size() -- " << sPtr->Size() << endl; break; case 'd': // Destructor delete sPtr; sPtr = NULL; cout << "~Stack()" << endl << endl; break; default: // Error cout << "Error - unrecognized operation '" << op << "'" << endl; cout << "Terminating now..." << endl; return 1; break; } inputs >> op; // Attempt to input next command } return 0; } // End main()
This is the stack.h file that should be completed:
// // stack.h // // Specification file for Stack class, a stack of integers implemented // using doubly-linked nodes. // #include using namespace std; #ifndef STACK_H #define STACK_H class StackEmpty { /* No Code */ }; // StackEmpty exception class - throw an object of this type when stack is empty // Hint: there is no code for exception classes class StackFull { /* No Code */ }; // StackFull exception class - throw an object of this type when stack is full class StackInvalidPeek { /* No Code */ }; // StackInvalidPeek exception class - throw an object of this type when invalid peek position is used struct Node // Node data type for storing a single stack entry along with pointers to { // neighboring entries (previous and next) in the stack Node* previous; // Member variable that holds the address of the predessor node in the stack sequence Node* next; // Member variable that holds the address of the successor node in the stack sequence int data; // Member variable that holds the data value }; class Stack // Implements stack of integers ADT using doubly-linked sequence of nodes { private: Node* topPtr; // Points to the top node on the stack array public: Stack(); // Default constructor initializes empty stack ~Stack(); // Destructor deallocates all nodes from stack // Must not create a memory leak void Push(int n); // Pushes integer n onto top of stack. // If unable to push, throws StackFull exception. void Pop(); // Removes top integer from stack // If stack is already empty, throws StackEmpty exception bool IsEmpty() const; // Returns true if stack is empty; false otherwise bool IsFull() const; // Returns true if stack is full; false otherwise void MakeEmpty(); // Removes all nodes from stack leaving an empty, but usable stack // Must not create a memory leak int Top() const; // Returns value of top integer on stack WITHOUT modifying the stack // If stack is empty, throws StackEmpty exception int Size() const; // Returns number of items on stack WITHOUT modifying the stack int Max() const; // Returns value of largest integer within stack WITHOUT modifying the stack // If stack is empty, throws StackEmpty int Min() const; // Returns value of smallest integer within stack WITHOUT modifying the stack // If stack is empty, throws StackEmpty int Peek( int n) const; // Returns stack value n levels down from top of stack. Peek(0) = Top() // If position n does not exist, throws StackInvalidPeek /******* DO NOT MODIFY ANY OF THE CODE FOR PRINT() *******/ /****** DO NOT PLACE A COPY OF PRINT() CODE IN STACK.CPP!!! *******/ void Print() const // Prints stack contents to stdout in both top-to-bottom and bottom-to-top order { Node* temp = topPtr; cout << "Top { "; // Forward print while (temp != NULL) { cout << temp->data << " "; if (temp->next == NULL) break; temp = temp->next; } cout << "} Bottom Bottom { "; // Reverse print while (temp != NULL) { cout << temp->data << " "; temp = temp->previous; } cout << "} Top" << endl; } // End Print() }; // End Class Stack #endif
This is the given input file to test code with:
This file is saved as a txt file
# p03input1.txt -- Test: Stack(), Push(), Pop(), Top(), and ~Stack() c p t + 5 + 10 + 15 p t + 20 + 25 + 30 p t - - p + 35 + 40 t + 45 t p - - - - - - - - p t d c p - t d
