class QueueItem {
public:
QueueItem(char *pData, int id); // ctor
void setNext(QueueItem *pItem);
QueueItem* getNext();
int getId();
const char* getData();
private:
char mData[30]; // or, use a char* if you want to dynamically alloc memory
int mNodeID;
QueueItem * mpNext;
};

The QueueItem member functions are very basic, just setting or getting data members of the class. All the linked list manipulation is done by the Queue class member functions.

The Queue class member functions manipulate the linked list of QueueItem's, creating and destroying QueueItem objects as needed using the C++ new and delete operators. The Queue class member data includes a pointer to the head and and pointer to the tail of the linked list of QueueItems, and an integer node counter used to provide a unique node ID for every newly created QueueItem (incremented each time a new QueueItem is added, and passed as a parameter to the QueueItem constructor. It is never decremented).

The following is a partial example of the Queue class; you will need to fill in the remaining methods.

class Queue {
public:
Queue(); // ctor inits a new Queue
~Queue(); // dtor erases any remaining QueueItems
void addItem(char *pData);
void removeItem();
...
private:
QueueItem *mpHead; // always points to first QueueItem in the list
QueueItem *mpTail; // always points to the last QueueItem in the list
int mNodeCounter; // always increasing for a unique id to assign to each new QueueItem
};

The Queue class member functions should not have access to the private members of QueueItem objects. They call the public member functions of QueueItem.

As an example, the outline of the Queue::addItem() member function is shown below. It must add a new QueueItem at the tail of the Queue, and update the mpTail pointer to point to it. The first item in the Queue is both the head and the tail of the list.:


void Queue::addItem(char *pData)
{
// dynamically create and init a new QueueItem object
QueueItem *pQI = new QueueItem(pData, ++mNodeCounter);

if (0 == mpHead) // chk for empty queue
mpHead = mpTail = pQI;
else
{
// link new item onto tail of list using mpTail pointer
...
}
}

The removeItem() method removes the head QueueItem from the queue, and should release the memory using the C++ delete operator. It updates mpHead to point at the following item (if any) as the new head. If the list becomes empty, both mpHead and mpTail must be set to null (0). It does not change the value of mNodeCounter (which is always incremented when a new item is added). If called on an empty Queue, it does nothing.

The erase() method removes all the items in the queue and should release the memory. To implement, you could loop calling removeItem() until the queue is empty.

The Queue destructor should ensure that all items are removed from the queue. The easiest way is to call the erase() method from the destructor.
The user code (main) never see's QueueItem objects, since they are used only for implementation inside of class Queue. main() has only the Queue object to work with. For example, the following code would create a queue with three elements, and then print it out:



-------------------------------------------------------------------------------
my Program:

//QueueItem.h
//Declaration of class QueueItem


#ifndef QUEUEITEM_H
#define QUEUEITEM_H



class QueueItem
{
public:
QueueItem(char *pData, int id); // constructor
void setNext(QueueItem *pItem); //set pointer to next Item
QueueItem* getNext(); //get pointer to next Item
int getId(); //get Id
const char* getData(); //get data member

private:
char mData[30]; // or, use a char* if you want to dynamically alloc memory
int mNodeID;
QueueItem *mpNext; // pointer to another object of same type
};//end class QueueItem

#endif
------
//Queue.h
//Declaration of class Queue

//prevent multiple inclusions of header file
#ifndef QUEUE_H
#define QUEUE_H

#include "QueueItem.h" // include definitions of class QueueItem from QueueItem.h

class Queue
{
public:
Queue(); // constructor
~Queue(); // destructor
void addItem(char *pData);
void removeItem();
void eraseList();
void printList();

private:
QueueItem *mpHead; // always points to first QueueItem in the list
QueueItem *mpTail; // always points to the last QueueItem in the list
int mNodeCounter; // always increasing for a unique id to assign to each new QueueItem
};//end class Queue
#endif
-----------
//member function definitions for class QueueItem

#include <iostream> // allows program to output data
using namespace std;

#include <string>

#include "QueueItem.h" // include definition of class QueueItem from QueueItem.h

//QueueItem constructor
QueueItem::QueueItem(char *pData, int id)
{
pData = mData;
id = mNodeID;
mpNext = NULL;

}// end constructor

void QueueItem::setNext(QueueItem *pItem)
{
mpNext = pItem;
}// end setNext function


QueueItem* QueueItem::getNext()
{
return mpNext;
}//end getNext function

int QueueItem::getId()
{
return mNodeID;
}//end getId function

const char* QueueItem::getData()
{
return mData;
}//end getData function
--------------
//member function definitions for class Date
#include <iostream> //allows program to output data on screen
using std::cout;
using std::endl;
using namespace std;

#include <iomanip>
using std::setfill;
using std::setw;

#include <string>
using std::string;
using std::strcpy;

#include "Queue.h" //include definition of class Queue from Queue.h



//constructor
Queue::Queue()
{
mpHead = NULL;
mpTail = NULL;
mNodeCounter = 0;
}

void Queue::addItem(char *pData)
{
//create and initialize new QueueItem dynamically
QueueItem *pQI = new QueueItem(pData, ++mNodeCounter);

if ( mpHead == 0 ){ //check for empty queue
mpHead = mpTail = pQI;}

else{
// link new item onto tail of list using mpTail pointer

mpTail->setNext(pQI);
mpTail = pQI;

}

}//end addItem function

//function removeItem
void Queue::removeItem()
{
if(mpHead == NULL){
mpHead = mpTail;}
else{
delete mpHead;
mpHead = mpHead->getNext();}



}//end removeItem function

//Erase List
void Queue::eraseList()
{
while (mpHead != 0)
removeItem();
mpHead = mpTail = 0;
}//end eraseList function

//prints contents of queue
void Queue::printList()
{
while (mpHead != 0){
cout << mpHead->getData() << endl;
mpHead = mpHead->getNext();
cout << mNodeCounter << endl;}
}//end printList function

//destructor
Queue::~Queue()
{
eraseList();
}
---------------------------------------

//QueueItem constructor
QueueItem::QueueItem(char *pData, int id)
{
// set the internal variables to the parameters, not vice versa
//pData = mData; 
//id = mNodeID;
mData = pData;
mNodeID = id;
mpNext = NULL;

}// end constructor