// http://mschat.net/// Queue.class.h#ifndef __QUEUE_CLASS__#define __QUEUE_CLASS__#ifndef NULL#define NULL ((void*)0)#endif// We can't use the data type supplied to us without any modification,// so we simply make a structure containing the value and the next item (pointer).template <class datatype>struct QueueNode{ datatype value; QueueNode *next;};// The class definition of Queuetemplate <class datatype>class Queue{ private: QueueNode<datatype> *top; QueueNode<datatype> *bottom; QueueNode<datatype> *current; int items; public: Queue(); ~Queue(); void add(datatype item); void push(datatype item); datatype remove(); datatype pop(); int length(); void empty(); void reset(); datatype next(); datatype front(); datatype back();};#include "Queue.class.cpp"#endif// Queue.class.cpp#ifndef __QUEUE_CLASS__#include "Queue.class.h"#endiftemplate <class datatype>Queue<datatype>::Queue(){ // Top needs to point to NULL top = NULL; // Same goes for bottom... bottom = NULL; // No items, quite yet. items = 0;}template <class datatype>Queue<datatype>::~Queue(){ empty();}template <class datatype>void Queue<datatype>::add(datatype item){ // add is an alias of push(); push(item);}template <class datatype>void Queue<datatype>::push(datatype item){ // We can't use the item supplied exactly, so we need // a struct to hold the value and the next item (pointer) QueueNode<datatype> *dummy; dummy = new(QueueNode<datatype>); // Now set dummys value. dummy->value = item; if(top == NULL) { // Top now needs to point to dummy and bottom needs to point to top ;) top = dummy; bottom = top; reset(); } // Now we need to link the last item to the next one. bottom->next = dummy; // Bottom now needs to go to dummy, since it is now the last one. bottom = dummy; // The very last item points to nothing, for now. bottom->next = NULL; // That's one more item!!! items++;}template <class datatype>int Queue<datatype>::length(){ return items;}template <class datatype>void Queue<datatype>::empty(){ // Get rid of everything! If anything, that is. if(items > 0) { delete[] top; delete[] bottom; // Now set them back to NULL top = NULL; bottom = NULL; reset(); items = 0; }}template <class datatype>datatype Queue<datatype>::remove(){ // remove is an alias of pop(); return pop();}template <class datatype>datatype Queue<datatype>::pop(){ // Can't remove anything if top is NULL, can we? if(top != NULL) { // The first item is what we want to remove. QueueNode<datatype> *dummy = top; // Now that dummy points to top, we can make top top's next... top = top->next; // 1 less item ;) items--; // No items..? We can't have bottom pointing there. if(items == 0) bottom = NULL; // We need to make a new variable to hold the previous top item, so we can return it. datatype value = dummy->value; delete(dummy); // Oh yeah, don't forget, we now have a new top! reset(); return value; } else return false;}template <class datatype>void Queue<datatype>::reset(){ // Reset current to the top. current = top;}template <class datatype>datatype Queue<datatype>::next(){ // Current NULL? Nothing more!!! if(current == NULL) return false; // Save the current value, and more to the next item. datatype value = current->value; current = current->next; return value;}template <class datatype>datatype Queue<datatype>::front(){ if(top == NULL) return false; return top->value;}template <class datatype>datatype Queue<datatype>::back(){ if(bottom == NULL) return false; return bottom->value;}