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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214
// ============================================================================// 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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263
#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: -2817
doubleQueue 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