Daily Archives: May 20, 2012
C++ || Snippet – Doubly Linked List Custom Template Queue Sample Code
This page will consist of sample code for a custom doubly linked list template queue. This implementation is considered a doubly linked list because it uses two nodes to store data in the queue – a ‘front’ and a ‘rear’ node. This is not a circular linked list, nor does it link forwards and/or backwards.
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 |
// ============================================================================ // Author: K Perkins // Date: May 20, 2012 // Taken From: http://programmingnotes.org/ // File: DoubleQueue.h // Description: This is a class which implements various functions // demonstrating the use of a queue. // ============================================================================ #include <iostream> template <class ItemType> class DoubleQueue { public: DoubleQueue(); /* 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 */ ~DoubleQueue(); /* Function: Removes the queue Precondition: Queue has been declared Postcondition: Queue no longer exists */ private: struct NodeType { ItemType currentItem; NodeType* next; }; NodeType* front; // front of queue NodeType* rear; // back of queue int size; }; //========================= Implementation ================================// template<class ItemType> DoubleQueue<ItemType>::DoubleQueue() { front = NULL; rear = NULL; size = 0; }/* end of DoubleQueue */ template<class ItemType> bool DoubleQueue<ItemType>::IsEmpty() { return (front == NULL); }/* end of IsEmpty */ template<class ItemType> bool DoubleQueue<ItemType>::IsFull() { try { NodeType* location = new NodeType; delete location; return false; } catch(std::bad_alloc&) { return true; } }/* end of IsFull */ template<class ItemType> void DoubleQueue<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(rear == NULL) { front = newNode; } else { rear-> next = newNode; } rear = newNode; ++size; } }/* end of EnQueue */ template<class ItemType> ItemType DoubleQueue<ItemType>::DeQueue() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { NodeType* tempPtr = front; // temporary pointer ItemType item = front-> currentItem; front = front-> next; if(front == NULL) { rear = NULL; } delete tempPtr; --size; return item; } }/* end of DeQueue */ template<class ItemType> ItemType DoubleQueue<ItemType>::Front() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { return front-> currentItem; } }/* end of Front */ template<class ItemType> ItemType DoubleQueue<ItemType>::Rear() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } else { return rear-> currentItem; } }/* end of Rear */ template<class ItemType> int DoubleQueue<ItemType>::Size() { if(IsEmpty()) { std::cout<<"nQUEUE EMPTYn"; } return size; }/* end of Size */ template<class ItemType> void DoubleQueue<ItemType>::MakeEmpty() { if(!IsEmpty()) { std::cout << "Destroying nodes ...n"; while(!IsEmpty()) { NodeType* tempPtr = front; //std::cout << tempPtr-> currentItem << 'n'; front = front-> next; delete tempPtr; } rear = NULL; size = 0; } }/* end of MakeEmpty */ template<class ItemType> DoubleQueue<ItemType>::~DoubleQueue() { 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 "DoubleQueue.h" using namespace std; int main() { // declare variables DoubleQueue<char> charQueue; DoubleQueue<int> intQueue; DoubleQueue<float> floatQueue; // ------ Char Example ------// char charArry[]="My Programming Notes Helped Me Succeed!"; 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,3,46,5,66,7,8,1987}; counter=0; while(counter<9) { 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; // ------ 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) { floatQueue.EnQueue(floatArry[counter]); ++counter; } cout<<"nfloatQueue has "<<floatQueue.Size()<<" items in it.n" <<"The sum of the numbers in the queue is: "; while(!floatQueue.IsEmpty()) { sum-=floatQueue.DeQueue(); } cout<<sum<<endl; return 0; }// http://programmingnotes.org/ |
Once compiled, you should get this as your output
charQueue has 39 items in it and contains the text:
My Programming Notes Helped Me Succeed!intQueue has 9 items in it.
The sum of the numbers in the queue is: -2145floatQueue has 10 items in it.
The sum of the numbers in the queue is: -286.717
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
