A stack is a basic data structure that is commonly used throughout computer science. For example, a stack is utilized by your web browser to remember the last few pages you were on. Developers and programmers should be very familiar with...
Part 1 of 5:
Configuring the Initial Environment
Add a class to your project. In Visual Studio, the easiest way to add class is to simply use the keyboard shortcut Ctrl+⇧ Shift+X. Once the window title Class Wizard opens, click the Add Class button towards the top right.
Enter the details for your class. In the Add Class window, enter StackLinked in the text box titled Class Name. Assure that none of the option boxes towards the bottom are checked. Once this is completed, click the OK button towards the bottom right.
Part 2 of 5:
Preparing Your Pre-Implementation Files
#include using namespace std; template typename DataType> class StackLinked { public: StackLinked( ); // Constructor ~StackLinked( ); // Destructor // Member functions void push( const DataType& newDataItem ); DataType pop( ) throw ( logic_error ); bool isEmpty( ) const; // Display Stack (Testing and Debugging) void showStructure() const; private: /* * !!!!! NOTE !!!!!: * LEAVE ROOM HERE TO INSERT --- Node Class --- IN THE NEXT STEP > */ StackNode* top; // Ptr to remember top of stack };
// Node Class (Each item in stack is one node, insert this in the same file as above) class StackNode { public: StackNode(const DataType& nodeData, StackNode* nextPtr) { dataItem = nodeData; next = nextPtr; } DataType dataItem; // Data stored in node StackNode* next; // Pointer holding the address of the next node };
Part 3 of 5:
Implementing the Code for Stack
/* * Default Constructor * Method to initialize all class variables * PreCondition - None * PostCondition - top is initialized */ // Class Member top is initialized to nullptr template typename DataType> StackLinkedDataType>::StackLinked ( ) { top = nullptr; // initialize value }
/* * Destructor * Method will deallocate all space taken by the stack * PreCondition - None ( No operations preformed is stack if empty ) * PostCondition - top = nullptr ( No Nodes in Stack ) */ // All nodes in stack are deallocated template typename DataType> StackLinkedDataType>::~StackLinked( ) { StackNode* traverse; // Temp NodePtr while ( !this->empty( ) ) { // Stop when no nodes left traverse = top; // Remember the previous top node top = top->next; // Move top node to the next node delete traverse; // Deallocate the top node stored at start } }
// Method to insert an item at the top of the stack // newDataItem: Data item that will be inserted on top of stack template typename DataType> void StackLinkedDataType>::push( const DataType& newDataItem ) { // Allocate new node with newDataItem and link to previous top StackNode* t = new StackNode ( newDataItem, top ); top = t; // Insert item to top of stack }
// Method will remove the top member of the stack // (most recently inserted) and return that data (PostCondition) // Function will throw Stack is not empty template typename DataType> DataType StackLinkedDataType>::pop() throw (logic_error) { if ( !this->empty( ) ) { DataType d = top->dataItem; // Hold data at the top of stack StackNode* t = top; // Temp. store address of top top = top->next; // Advance top to now reference next item delete t; // Deallocate the space being used by previous top return d; // Return data stored in the previous top node } else { // PreCondition is that the stack cannot be empty throw logic_error("Error: Pop was unsuccessful. Make sure stack is not empty."); } }
// Will determine if list is empty ( No space taken by stack ) // PreCondition: None // PostCondition: Return either true or false template typename DataType> bool StackLinkedDataType>:: isEmpty( ) const { return ( top == nullptr ); }
Part 4 of 5:
Testing the Implementation
Add a new file to your project. Now that the stack has been implemented, validate the implementation behavior. To do this, create a testStack.cpp file by using the keyboard short cut Ctrl+N and renaming the file testStack.cpp. Alternatively, right click the source folder and select Add new item, rename this item testStack.cpp.
///////////////////// -- PROJECT DESCRIPTION -- //////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // // Testing File for Stack Data Structure // // SPECIFICATIONS: // // Push: // Should add item to top of stack // // Pop: // Should remove item from top of stack // //Empty: // Should say "empty stack" if no items otherwise // say "not empty stack" // //operator= : // Should make a copy of a stack (right hand side) // in other stack (left hand side) // //Stack exampleStack: // Should make a empty stack // //Stack temp(oldStack): // Should copy items from oldstack and put them in temp // stack // //TEST CASES: // // STEP NO. |COMMAND | RESULT // ------------------------------------------------------ // 1 | +a+b+c | [c] b a // 2 | -- | [a] // 3 | E | Stack is NOT empty // 4 | +e | [e] a // 5 | C | Stack is empty // 6 | Q | N/A // //PASS CRITERIA FOR IMPLEMENTATION: // - All Test Cases above produce proper result // - All Stack specifications are followed // - No Memory Leaks, Build Errors, Segmentation Faults, etc. // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //////////// Header Files and Namespaces - DO NOT DELETE //////////////////////// #include // For cout #include // For formatted output #include "StackLinked.cpp"// To use your stack implementation using namespace std; // Use items in std namespace (std::) //////////// Header Files and Namespaces - DO NOT DELETE //////////////////////// //////////// SHOW STRUCTURE - TESTING AND DEBUGGING ////////////////////// /* * Outputs the data items in a stack. * If the stack is empty, outputs "Empty stack". */ template typename DataType> void StackLinkedDataType>::showStructure() const { if( isEmpty() ) { cout "Empty stack" endl; } else { cout "Topt"; for (StackNode* temp = top; temp != 0; temp = temp->next) { if( temp == top ) { cout "[" temp->dataItem "]t"; } else { cout temp->dataItem "t"; } } cout "Bottom" endl; } } //////////// SHOW STRUCTURE - TESTING AND DEBUGGING ////////////////////// //////////// TESTING MENU - START /////////////////////////// void testMenu( ) { cout setw( 20 ) left "Command" setw( 20 ) left "Description" endl; cout setw( 20 ) left "H" setw( 20 ) left "Show Help Menu." endl; cout setw( 20 ) left "+[item]" setw( 20 ) left "Push item ([item]) to stack. '[item]' is a placeholder. (ex. +a will add 'a' to stack.)" endl; cout setw( 20 ) left "-" setw( 20 ) left "Pop item from stack. Will remove last inserted item to stack." endl; cout setw( 20 ) left "E" setw( 20 ) left "Check if stack is empty" endl; cout setw( 20 ) left "Q" setw( 20 ) left "Terminate testing." endl endl; } //////////// TESTING MENU - END /////////////////////////////// int main() { cout "Testing Stack Data Structure Implementation" endl; cout "-----------------------------------------------------------" endl; StackLinkedchar> testStack; // Stack char testDataItem, cmd; // Stack data item, Input Command testMenu(); // Show Command Menu // TESTING LOOP (READ CMD -> PREFORM OPERATION) do { testStack.showStructure(); // Output stack cout endl "Command: "; cin >> cmd;// Read command try { switch ( cmd ) { case 'H' : case 'h': testMenu(); break; case '+' : cin >> testDataItem; testStack.push(testDataItem); break; case '-' : cout "Popped " testStack.pop() endl; break; case 'Q' : case 'q' : break; case 'E' : case 'e' : cout ( ( testStack.isEmpty() ) ? ( "Stack is emptyn" ) : ( "Stack is NOT emptyn") ); break; default : cout cmd "is an invalid command. Enter H to see menu." endl; } } catch ( logic_error _stackError ) { cout "ERROR: " _stackError.what() endl; } } while ( cin && cmd != 'Q' && cmd != 'q' ); }
Part 5 of 5:
Debugging
Walk through the particular function or program that has an issue. Visualize what each line of code is doing. This will help with targeting the issue.
Comment and clean up your code and identifiers. This will help both you and others read the code and identify where a particular function isn't working according to specification.
Ask a friend or colleague to also take a look at your code. It is possibly that you are skipping over some detail that a new set eyes may be able to see. However, your code must be well formatted so they can understand, further implicating the importance of following coding conventions.
Step back and take a break from the code. Attempt to mentally run through how the code should be working, possibly think of a better way to do the same function, or just don't think about the whole program at all to refresh your thinking. Once you have found a possibly solution or have relaxed your mind, get back and attempt to solve it again. More often than not, you will be able to see the mistake being made.
Set breakpoints at lines where you think the program is failing. If you are utilizing an IDE, then you can set breakpoints at specific lines of code; this will tell the computer to stop running for a moment so that you can see exactly what it has already done and predicate what it will do next. This will often show you exactly why the program is failing to execute how you want it.
Update 05 March 2020
ncG1vNJzZmismaXArq3KnmWcp51ktbDDjK2mZqGdpbmmucSnq2aZXajBoq%2FKZpuarJFiwLW%2B1JyrrqqVYravecI%3D