C++ || Snippet – Linked List Custom Template Stack Sample Code
This page will consist of sample code for a custom linked list template stack. This page differs from the previously highlighted array based template stack in that this version uses a singly linked list to store data rather than using an array.
Looking for sample code for a queue? Click here.
REQUIRED KNOWLEDGE FOR THIS SNIPPET
Structs
Classes
Template Classes - What Are They?
Stacks
LIFO - What Is It?
#include < stack>
Linked Lists - How To Use
This template class is a custom duplication of the Standard Template Library (STL) stack class. Whether you like building your own data structures, you simply do not like to use any inbuilt functions, opting to build everything yourself, or your homework requires you make your own data structure, this sample code is really useful. I feel its beneficial building functions such as this, that way you better understand the behind the scene processes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
// ============================================================================ // Author: K Perkins // Date: Apr 9, 2012 // Taken From: http://programmingnotes.org/ // File: ClassStackListType.h // Description: This is a class which implements various functions // demonstrating the use of a stack. // ============================================================================ #include <iostream> template <class ItemType> class StackListType { public: StackListType(); /* Function: constructor initializes class variables Precondition: none Postcondition: defines private variables */ bool IsEmpty(); /* Function: Determines whether the stack is empty Precondition: Stack has been initialized Postcondition: Function value = (stack is empty) */ bool IsFull(); /* Function: Determines whether the stack is full Precondition: Stack has been initialized Postcondition: Function value = (stack is full) */ int Size(); /* Function: Return the current size of the stack Precondition: Stack has been initialized Postcondition: If (stack is full) exception FullStack is thrown else newItem is at the top of the stack */ void MakeEmpty(); /* Function: Empties the stack Precondition: Stack has been initialized Postcondition: Stack is empty */ void Push(ItemType newItem); /* Function: Adds newItem to the top of the stack Precondition: Stack has been initialized Postcondition: If (stack is full) exception FullStack is thrown else newItem is at the top of the stack */ ItemType Pop(); /* Function: Returns & then removes top item from the stack Precondition: Stack has been initialized Postcondition: If (stack is empty) exception EmptyStack is thrown else top element has been removed from the stack */ ItemType Top(); /* Function: Returns the top item from the stack Precondition: Stack has been initialized Postcondition: If (stack is empty) exception EmptyStack is thrown else top element has been removed from the stack */ ~StackListType(); /* Function: destructor deallocates class variables Precondition: none Postcondition: deallocates private variables */ private: struct NodeType { ItemType currentItem; // Variable which hold all the incoming currentItem NodeType* next; // Creates a pointer that points to the next node in the list. }; int size; // Indicates the size of the stack ItemType junk; NodeType* headPtr; // Creates a head pointer that will point to the begining of the list. }; //========================= Implementation ================================// template<class ItemType> StackListType<ItemType>::StackListType() { size = 0; headPtr = NULL; }// End of StackListType template<class ItemType> bool StackListType<ItemType>::IsEmpty() { return (headPtr == NULL); }// End of IsEmpty template<class ItemType> bool StackListType<ItemType>::IsFull() { try { NodeType* tempPtr = new NodeType; delete tempPtr; return false; } catch(std::bad_alloc&) { return true; } }// End of IsFull template<class ItemType> int StackListType<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; } return size; }// End of Size template<class ItemType> void StackListType<ItemType>::MakeEmpty() { size = 0; if (!IsEmpty()) { std::cout << "Destroying nodes ...n"; while (!IsEmpty()) { NodeType* tempPtr = headPtr; //std::cout << tempPtr-> currentItem << 'n'; headPtr = headPtr-> next; delete tempPtr; } } }// End of MakeEmpty template<class ItemType> void StackListType<ItemType>::Push(ItemType newItem) { if(IsFull()) { std::cout<<"nSTACK FULLn"; return; } NodeType* tempPtr = new NodeType; tempPtr-> currentItem = newItem; tempPtr-> next = headPtr; headPtr = tempPtr; ++size; }// End of Push template<class ItemType> ItemType StackListType<ItemType>::Pop() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; return junk; } else { ItemType data = headPtr-> currentItem; NodeType* tempPtr = headPtr; headPtr = headPtr-> next; delete tempPtr; --size; return data; } }// End of Pop template<class ItemType> ItemType StackListType<ItemType>::Top() { if(IsEmpty()) { std::cout<<"nSTACK EMPTYn"; return junk; } else { return headPtr-> currentItem; } }// End of Top template<class ItemType> StackListType<ItemType>::~StackListType() { MakeEmpty(); }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
===== DEMONSTRATION HOW TO USE =====
Use of the above template class is the same as its STL counterpart. Here is a sample program demonstrating its use.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include "ClassStackListType.h" using namespace std; int main() { // declare variables StackListType<char> charStack; StackListType<int> intStack; StackListType<float> floatStack; // ------ Char Example ------// char charArry[]="My Programming Notes Is Awesome"; int counter=0; while(charArry[counter]!='\0') { charStack.Push(charArry[counter]); ++counter; } cout<<"charStack has "<<charStack.Size()<<" items in itn" <<"and contains the text ""<<charArry<<"" backwards:n"; while(!charStack.IsEmpty()) { cout<<charStack.Pop(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,3,46,5,66,7,8,1987}; counter=0; while(counter<9) { intStack.Push(intArry[counter]); ++counter; } cout<<"nintStack has "<<intStack.Size()<<" items in it.n" <<"The sum of the numbers in the stack is: "; counter=0; while(!intStack.IsEmpty()) { counter+=intStack.Pop(); } cout<<counter<<endl; // ------ Float Example ------// float floatArry[]={41.6,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,81.540}; float sum=0; counter=0; while(counter<10) { floatStack.Push(floatArry[counter]); ++counter; } cout<<"nfloatStack has "<<floatStack.Size()<<" items in it.n" <<"The sum of the numbers in the stack is: "; while(!floatStack.IsEmpty()) { sum+=floatStack.Pop(); } cout<<sum<<endl; }// http://programmingnotes.org/ |
Once compiled, you should get this as your output
charStack has 31 items in it
and contains the text "My Programming Notes Is Awesome" backwards:
emosewA sI setoN gnimmargorP yMintStack has 9 items in it.
The sum of the numbers in the stack is: 2145floatStack has 10 items in it.
The sum of the numbers in the stack is: 286.717
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply