C++ || Snippet – Singly Linked List Custom Template Queue Sample Code
This page will consist of sample code for a custom singly linked list template queue. This implementation differs from the previously highlighted doubly linked list in that this version uses a single node to store its data rather than using two separate nodes (front and rear).
Looking for sample code for a stack? Click here.
REQUIRED KNOWLEDGE FOR THIS SNIPPET
Structs
Classes
Template Classes - What Are They?''
Queue - What is it?
FIFO - First In First Out
#include < queue>
Linked Lists - How To Use
This template class is a custom duplication of the Standard Template Library (STL) queue 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 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 |
// ============================================================================ // Author: K Perkins // Date: Jul 14, 2012 // Taken From: http://programmingnotes.org/ // File: SingleQueue.h // Description: This is a class which implements various functions // demonstrating the use of a queue. // ============================================================================ #include <iostream> template <class ItemType> class SingleQueue { public: SingleQueue(); /* Function: Constructor initializes queue Precondition: None Postcondition: Defines private variables */ bool IsEmpty(); /* Function: Determines whether queue is empty Precondition: Queue has been created Postcondition: The function = true if the queue is empty and the function = false if queue is not empty */ bool IsFull(); /* Function: Determines whether queue is full Precondition: Queue has been created Postcondition: The function = true if the queue is full and the function = false if queue is not full */ void EnQueue(ItemType item); /* Function: Adds new item to the back of the queue Precondition: Queue has been created and is not full Postcondition: Item is in the queue */ ItemType DeQueue(); /* Function: Returns and then deletes the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been removed and the queue order is maintained */ ItemType Front(); /* Function: Returns (but does not delete) the first item in the queue Precondition: Queue has been created and is not empty Postcondition: The first item in the queue has been returned and the queue order is maintained */ ItemType Rear(); /* Function: Returns (but does not delete) the last item in the queue Precondition: Queue has been created and is not empty Postcondition: The last item in the queue has been returned and the queue order is maintained */ int Size(); /* Function: Return the current size of the queue Precondition: Queue has been initialized Postcondition: The size of the queue is returned */ void MakeEmpty(); /* Function: Initializes queue to an empty state Precondition: Queue has been created Postcondition: Queue no longer exists */ ~SingleQueue(); /* Function: Removes the queue Precondition: Queue has been declared Postcondition: Queue no longer exists */ private: struct NodeType { ItemType currentItem; NodeType* next; }; NodeType* head; // front of queue int size; }; //========================= Implementation ================================// template<class ItemType> SingleQueue<ItemType>::SingleQueue() { head = NULL; size = 0; }/* end of SingleQueue */ template<class ItemType> bool SingleQueue<ItemType>::IsEmpty() { return (head == NULL); }/* end of IsEmpty */ template<class ItemType> bool SingleQueue<ItemType>::IsFull() { try { NodeType* location = new NodeType; delete location; return false; } catch(std::bad_alloc&) { return true; } }/* end of IsFull */ template<class ItemType> void SingleQueue<ItemType>::EnQueue(ItemType newItem) { if(IsFull()) { std::cout<<"nQUEUE FULLn"; } else { NodeType* newNode = new NodeType; // adds new node newNode-> currentItem = newItem; newNode-> next = NULL; if(IsEmpty()) { head = newNode; } else { NodeType* tempPtr = head; while(tempPtr-> next != NULL) { tempPtr = tempPtr-> next; } tempPtr-> next = newNode; } ++size; } }/* end of EnQueue */ template<class ItemType> ItemType SingleQueue<ItemType>::DeQueue() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = head; // temporary pointer ItemType item = head-> currentItem; head = head-> next; delete tempPtr; --size; return item; } }/* end of DeQueue */ template<class ItemType> ItemType SingleQueue<ItemType>::Front() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { ItemType item = head-> currentItem; return item; } }/* end of Front */ template<class ItemType> ItemType SingleQueue<ItemType>::Rear() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = head; // temporary pointer while(tempPtr->next != NULL) { tempPtr = tempPtr-> next; } ItemType item = tempPtr-> currentItem; return item; } }/* end of Rear */ template<class ItemType> int SingleQueue<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } return size; }/* end of Size */ template<class ItemType> void SingleQueue<ItemType>::MakeEmpty() { if(!IsEmpty()) { std::cout << "Destroying nodes ...n"; while(!IsEmpty()) { NodeType* tempPtr = head; //std::cout << tempPtr-> currentItem << 'n'; head = head-> next; delete tempPtr; } size = 0; } }/* end of MakeEmpty */ template<class ItemType> SingleQueue<ItemType>::~SingleQueue() { 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 61 62 63 |
#include <iostream> #include "SingleQueue.h" using namespace std; int main() { // declare variables SingleQueue<char> charQueue; SingleQueue<int> intQueue; SingleQueue<double> doubleQueue; // ------ Char Example ------// char charArry[]="My Programming Notes Is A Big Help!"; int counter=0; while(charArry[counter]!='\0') { charQueue.EnQueue(charArry[counter]); ++counter; } cout<<"charQueue has "<<charQueue.Size()<<" items in it " <<"and contains the text:n"; while(!charQueue.IsEmpty()) { cout<<charQueue.DeQueue(); } cout<<endl; // ------ Int Example ------// int intArry[]={1,22,309,461,-92,66,7,8,1987,9,27,12}; counter=0; while(counter < sizeof(intArry)/sizeof(intArry[0])) { intQueue.EnQueue(intArry[counter]); ++counter; } cout<<"nintQueue has "<<intQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; counter=0; while(!intQueue.IsEmpty()) { counter-=intQueue.DeQueue(); } cout<<counter<<endl; // ------ Double Example ------// double doubleArry[]={31.62,2.8,43.9,4.4,19.87,6.23,7.787,68.99,9.6,3.540,12.04}; double sum=0; counter=0; while(counter < sizeof(doubleArry)/sizeof(doubleArry[0])) { doubleQueue.EnQueue(doubleArry[counter]); ++counter; } cout<<"ndoubleQueue has "<<doubleQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; while(!doubleQueue.IsEmpty()) { sum+=doubleQueue.DeQueue(); } cout<<sum<<endl; return 0; }// http://programmingnotes.org/ |
Once compiled, you should get this as your output
charQueue has 35 items in it and contains the text:
My Programming Notes Is A Big Help!intQueue has 12 items in it.
The sum of the numbers in the queue is: -2817doubleQueue has 11 items in it.
The sum of the numbers in the queue is: 210.777
Press any key to continue . . .
Was this article helpful?
👍 YesNo
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply