C++

Forum

 
Trouble with FIFO(Queue)

ghost305 (5)
Description

Create a Queue class that implements a queue abstraction. A queue is a FIFO list (First In First Out queue). A simple example is waiting in line, where the first person in the line is the first served. New arrivals are added to the back of the line, the next person served is (removed) from the front of the line.

The Queue class needs to implement the following operations:

* adding to the queue at one end (the tail)
* removing from the queue at the other end (the head)
* printing all items the queue (from head to tail)
* erasing all items in the queue (leaving the queue empty).
* destructor to empty the queue before it's destroyed (to release all memory)

Additions and removals always occur at the opposite ends of the queue.

You should create the following methods in your Queue class to implement the above operationsm

Your Queue implementation uses a companion QueueItem class to represent each element in the list. A QueueItem contains character string as the data value, a unique (among all QueueItems in a Queue) integer node identifier, and a pointer to the next QueueItem in the list. The following is the definition for the QueueItem class.

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:
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
 
//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();
}

---------------------------------------

What is wrong with my program???
Last edited on
Gumbercules (209)
Take a closer look at this. I think you would want to assign char by char the caracters of pData to mData, and set mNodeID to ID.
1
2
3
4
5
6
 
QueueItem::QueueItem(char *pData, int id)
{
pData = mData;
id = mNodeID;
mpNext = NULL;
}
ghost305 (5)
Thats what i did but it still print zeros
Gumbercules (209)
You can't just assign arrays to each other, you have to go member by member. Make sure to include <cstrng> 
1
2
3
4
5
6
 
QueueItem::QueueItem(char *pData, int id)
{
strncpy(mDate, pDate, 29);
mNodeID = id;
mpNext = NULL;
}


also, your print list advances the head. You'll want to keep this pointing to the first item. Make another pointer that's a copy of head, and advance that.
Also, your removeItem function tries to access head after it has been deleted.
Last edited on
ghost305 (5)
isn't mpHead the first item on the list?

The removeItem is supposed to remove the head and advance the next item to the head.
Topic archived. No new replies allowed.