Help with FIFO QUEUE

jackfraust · 04-01-2009, 07:16 PM

[quote]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. [/QUOTE}

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:

Code:

//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

Code:

//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

Code:

//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

Code:

//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??? it only prints 00000s. can somebody help me?
|

vart · 04-01-2009, 11:11 PM

what's up with the indentation? you really hope someone will read your mess? work a little bit on the readability of the code then

R.Stiltskin · 04-01-2009, 11:26 PM

It might also be a good idea to post the program (main function) that you say only prints 0's.

jackfraust · 04-02-2009, 10:07 AM

Code:

int main()
{
	Queue numbers;

	numbers.addItem("one");
	numbers.addItem("two");
	numbers.addItem("three");
	numbers.addItem("four");
	numbers.printList();
	numbers.removeItem();
	numbers.removeItem();
	numbers.addItem("five");
	numbers.addItem("six");
	numbers.addItem("seven");
	numbers.addItem("eight");
	numbers.printList();
	numbers.removeItem();
	numbers.removeItem();
	numbers.removeItem();
	numbers.removeItem();
	numbers.printList();
	numbers.eraseList();
	numbers.addItem("nine");
	numbers.addItem("ten");
	numbers.addItem("eleven");
	numbers.printList();
	numbers.eraseList();
	numbers.printList();

	return 0;
}

That's the main code, its made to test out the program

vart · 04-02-2009, 10:22 AM

in your QueuItem constructor
pData = mData; - this should be opposite

Code:

delete mpHead;
mpHead = mpHead->getNext();

you cannot access deleted pointer

your const correctness went out of window

your printList changes the head pointer making it impossible to remove head or print list once again

jackfraust · 04-02-2009, 10:58 AM

Quote:

Originally Posted by vart

in your QueuItem constructor
pData = mData; - this should be opposite

Code:

delete mpHead;
mpHead = mpHead->getNext();

you cannot access deleted pointer

your const correctness went out of window

your printList changes the head pointer making it impossible to remove head or print list once again

I changed the Queueitem constructor to:

Code:

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

for the removeItem function, after deleting the head shouldn't i push the next item on top??
How does the printlist change the head pointer?

vart · 04-02-2009, 11:00 AM

strncpy(mData, pData);
this will not compile...

and definitely will crash as you do not have a storage where to copy string

Switch to std::string if you want to store the passed value an not just a pointer

jackfraust · 04-02-2009, 11:28 AM

Quote:

Originally Posted by vart

strncpy(mData, pData);
this will not compile...

and definitely will crash as you do not have a storage where to copy string

Switch to std::string if you want to store the passed value an not just a pointer

mData is not a const char pointer, thats why i used
strncpy(mData, pData, 30);
----------------------------------------
what do you suggest for printlist() and removeItem()?

vart · 04-02-2009, 01:09 PM

Quote:

Originally Posted by jackfraust

mData is not a const char pointer, thats why i used
strncpy(mData, pData, 30);

why are you using char array and not std::string?

Quote:

what do you suggest for printlist() and removeItem()?

declare printlist as const (as it should - and fix the compiler error

in the removeItem - take the next pointer before deleting the current node

jackfraust · 04-02-2009, 01:48 PM

Quote:

Originally Posted by vart

why are you using char array and not std::string?

declare printlist as const (as it should - and fix the compiler error

in the removeItem - take the next pointer before deleting the current node

im supposed to use char and not std::string. as for taking the next pointer, should i use mpNext or getNext() function?

should i just leave removeitem as:

Code:

void Queue::removeItem()
{	
	delete mpHead;
}

R.Stiltskin · 04-02-2009, 08:21 PM

Quote:

Originally Posted by jackfraust

should i just leave removeitem as:

Code:

void Queue::removeItem()
{	
	delete mpHead;
}

No - if you do that on a non-empty queue you will "lose" (and leak) the rest of the queue; if you do it on an empty queue you will be trying to delete "NULL", which I suppose won't do any harm but makes no sense.

removeItem() should check to see if the queue is empty. If so, just return. If not empty, create a local QueueItem* temp, assign mpHead to temp just to hold it temporarily, reassign mphead to point to mpHead->getNext(), then delete temp.

You also need to make a similar correction to your printList(). You shouldn't be reassigning mpHead while you print -- after printing you will no longer have a pointer to the head of the queue. Instead use a temporary pointer to iterate through the queue (and print both the data and the id number before advancing that pointer).

jackfraust · 04-02-2009, 08:52 PM

Quote:

Originally Posted by R.Stiltskin

No - if you do that on a non-empty queue you will "lose" (and leak) the rest of the queue; if you do it on an empty queue you will be trying to delete "NULL", which I suppose won't do any harm but makes no sense.

removeItem() should check to see if the queue is empty. If so, just return. If not empty, create a local QueueItem* temp, assign mpHead to temp just to hold it temporarily, reassign mphead to point to mpHead->getNext(), then delete temp.

You also need to make a similar correction to your printList(). You shouldn't be reassigning mpHead while you print -- after printing you will no longer have a pointer to the head of the queue. Instead use a temporary pointer to iterate through the queue (and print both the data and the id number before advancing that pointer).

I see where you are coming from but the compiler doesn't want to let me create temporary pointers. For some reason it says unitialized local variable.

R.Stiltskin · 04-02-2009, 09:00 PM

Are you trying to define a pointer or a reference?

It won't let you do:

Code:

QueueItem *temp = mpHead;

???

Show me what you are are trying to do.

jackfraust · 04-02-2009, 09:14 PM

Quote:

Originally Posted by R.Stiltskin

Are you trying to define a pointer or a reference?

It won't let you do:

Code:

QueueItem *temp = mpHead;

???

Show me what you are are trying to do.

I had to restart the compiler for it to work, don't know what's wrong with it. But i got a question though, shouldn't the nodeID also get deleted everytime the removeItem() function is called, or eraseList()?

my int main() looks like this:

Code:

int main()
{
	numbers.addItem("one");
	numbers.addItem("two");
	numbers.addItem("three");
	numbers.addItem("four");
	numbers.printList();
	numbers.removeItem();
	numbers.removeItem();
	numbers.addItem("five");
	numbers.addItem("six");
	numbers.addItem("seven");
	numbers.addItem("eight");
	numbers.printList();
	numbers.removeItem();
	numbers.removeItem();
	numbers.removeItem();
	numbers.removeItem();
	numbers.printList();
	numbers.eraseList();
	numbers.addItem("nine");
	numbers.addItem("ten");
	numbers.addItem("eleven");
	numbers.printList();
	numbers.eraseList();
	numbers.printList();

return 0;
}

OUTPUT looks like this:
one 4
three 8
seven 8
nine 11

R.Stiltskin · 04-02-2009, 09:32 PM

Quote:

Originally Posted by jackfraust

my int main() looks like this:

No, show me what you did to removeItem().

Edit: and you also have to correct printList() as I mentioned above. Otherwise everything will be messed up after the first call to that method.

Quote:

Originally Posted by jackfraust

But i got a question though, shouldn't the nodeID also get deleted everytime the removeItem() function is called, or eraseList()?

No. You're not using dynamic allocation inside the nodes, so all you have to do is delete the node and that will automatically deal with the node's data members.

04-01-2009, 07:16 PM	#1
jackfraust Registered User Join Date: Feb 2009 Posts: 72	Help with FIFO QUEUE [quote]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. [/QUOTE} 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: Code: //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 Code: //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 Code: //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 Code: //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??? it only prints 00000s. can somebody help me? \| Last edited by jackfraust; 04-01-2009 at 07:23 PM.
jackfraust is offline

04-01-2009, 11:11 PM	#2
vart CSharpener Join Date: Oct 2006 Posts: 5,324	what's up with the indentation? you really hope someone will read your mess? work a little bit on the readability of the code then __________________ If I have eight hours for cutting wood, I spend six sharpening my axe.
vart is online now

04-01-2009, 11:26 PM	#3
R.Stiltskin Registered User Join Date: Feb 2003 Posts: 490	It might also be a good idea to post the program (main function) that you say only prints 0's.
R.Stiltskin is offline

04-02-2009, 10:22 AM	#5
vart CSharpener Join Date: Oct 2006 Posts: 5,324	in your QueuItem constructor pData = mData; - this should be opposite Code: delete mpHead; mpHead = mpHead->getNext(); you cannot access deleted pointer your const correctness went out of window your printList changes the head pointer making it impossible to remove head or print list once again __________________ If I have eight hours for cutting wood, I spend six sharpening my axe.
vart is online now

04-02-2009, 11:00 AM	#7
vart CSharpener Join Date: Oct 2006 Posts: 5,324	strncpy(mData, pData); this will not compile... and definitely will crash as you do not have a storage where to copy string Switch to std::string if you want to store the passed value an not just a pointer __________________ If I have eight hours for cutting wood, I spend six sharpening my axe.
vart is online now

04-02-2009, 09:00 PM	#13
R.Stiltskin Registered User Join Date: Feb 2003 Posts: 490	Are you trying to define a pointer or a reference? It won't let you do: Code: QueueItem *temp = mpHead; ??? Show me what you are are trying to do.
R.Stiltskin is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Fixing my program	Mcwaffle	C Programming	5	11-05-2008 03:55 AM
Need help with FIFO Queue using Singly Linked Lists	astou	C++ Programming	6	03-15-2008 02:36 PM
help with queues	Unregistered	C Programming	3	05-21-2002 09:09 PM
help with queues	Unregistered	C Programming	3	05-21-2002 11:39 AM
queue help	Unregistered	C Programming	2	10-29-2001 09:38 AM