Circular linked Queue using 1 pointer to the rear
I will state up front that this is an assignment and I understand the rules on the issue. I was provided the class specification and I have to come up with the implementation and methods. I have to design the methods for a circular linked queue with only 1 pointer that keeps track of the rear of the queue. Here is what I have come up with so far. I'm starting to get stuck now though. I'm not sure how to implement the print function. I also would like some input to make sure that what I have so far is even on the right track. Pointers are really confusing and it's taken me hours just to get this much done. Thanks in advance!
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_TYPE
#define QUEUE_TYPE
#include <iostream>
using std::cout; // generic output stream
using std::endl;
#include <new>
using std::bad_alloc;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::EnQue
{
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
}
rear = tempPtr;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
rear = NULL;
else
rear->next = tempPtr->next;
item = tempPtr->info;
delete tempPtr;
return item;
}
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
}
//assigns one queue to another
template<class ItemType>
QueueType& QueueType<ItemType>::Opera
{
rear = NULL;
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
EnQueue(right->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
#endif
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_TYPE
#define QUEUE_TYPE
#include <iostream>
using std::cout; // generic output stream
using std::endl;
#include <new>
using std::bad_alloc;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::EnQue
{
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
}
rear = tempPtr;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
rear = NULL;
else
rear->next = tempPtr->next;
item = tempPtr->info;
delete tempPtr;
return item;
}
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
}
//assigns one queue to another
template<class ItemType>
QueueType& QueueType<ItemType>::Opera
{
rear = NULL;
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
EnQueue(right->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
#endif
ASKER
Thank you for the help thus far! I have implemented your suggestions, correctly I hope. HaHa. I'm sure the print function still isn't right and I need some assistance understanding the MakeEmpty function as well. I tried to start it at least. Please also make sure that I fixed the DeQueue function properly. I appreciate all the help you guys can offer. It's important that I understand pointers. My next program uses this code too, so it's important it works and I understand it. Thanks!
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_TYPE
#define QUEUE_TYPE
#include <iostream>
using std::cout; // generic output stream
using std::endl;
#include <new>
using std::bad_alloc;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
NodeType *tempPtr;
while ( rear != NULL )
{
delete tempPtr;
}
rear = NULL;
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::EnQue
{
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
}
rear = tempPtr;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
status = true;
}
else
{
rear->next = tempPtr->next;
status = false;
}
item = tempPtr->info;
delete tempPtr;
return status;
}
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
while ( tempPtr != rear )
{
cout << tempPtr->info << endl;
tempPtr = tempPtr->next;
}
cout << tempPtr->info << endl;
}
else
cout << "The queue is empty." << endl;
}
//assigns one queue to another
template<class ItemType>
QueueType& QueueType<ItemType>::Opera
{
if ( MakeEmpty() )
rear = NULL;
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
EnQueue(rightPtr->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
}
#endif
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_TYPE
#define QUEUE_TYPE
#include <iostream>
using std::cout; // generic output stream
using std::endl;
#include <new>
using std::bad_alloc;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
NodeType *tempPtr;
while ( rear != NULL )
{
delete tempPtr;
}
rear = NULL;
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::EnQue
{
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
}
rear = tempPtr;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
status = true;
}
else
{
rear->next = tempPtr->next;
status = false;
}
item = tempPtr->info;
delete tempPtr;
return status;
}
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
while ( tempPtr != rear )
{
cout << tempPtr->info << endl;
tempPtr = tempPtr->next;
}
cout << tempPtr->info << endl;
}
else
cout << "The queue is empty." << endl;
}
//assigns one queue to another
template<class ItemType>
QueueType& QueueType<ItemType>::Opera
{
if ( MakeEmpty() )
rear = NULL;
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
EnQueue(rightPtr->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
}
#endif
>> Please also make sure that I fixed the DeQueue function properly.
It's closer, but the bool value you want to return is whether or not you were able to get an info value from the queue. The return value has to be false in case the queue is empty, and true otherwise (when you were ablt to fill in the item argument).
>> and I need some assistance understanding the MakeEmpty function as well.
What the MakeEmpty method should do, is remove all the nodes from the queue.
Take a look at your DeQueue method : there you remove one node. For the MakeEmpty, you have to do something similar, but for all nodes.
You could call DeQueue repeatedly until the queue is empty, or you could write a loop that removes one node per iteration until the queue is empty.
>> if ( MakeEmpty() )
In the assignment operator, you now have :
if ( MakeEmpty() )
rear = NULL;
MakeEmpty() doesn't return a value, so you can't check it with an if ... You don't need to check anything either. MakeEmpty() will empty the queue, and get it ready for filling it again ...
In other words, you can just do :
MakeEmpty();
instead of the two lines above.
>> I'm sure the print function still isn't right
It looks fine to me :)
Do you have a test program to test the queue class ? That will help you a lot to figure out if the code is working, and if it does what you want it to do.
It's closer, but the bool value you want to return is whether or not you were able to get an info value from the queue. The return value has to be false in case the queue is empty, and true otherwise (when you were ablt to fill in the item argument).
>> and I need some assistance understanding the MakeEmpty function as well.
What the MakeEmpty method should do, is remove all the nodes from the queue.
Take a look at your DeQueue method : there you remove one node. For the MakeEmpty, you have to do something similar, but for all nodes.
You could call DeQueue repeatedly until the queue is empty, or you could write a loop that removes one node per iteration until the queue is empty.
>> if ( MakeEmpty() )
In the assignment operator, you now have :
if ( MakeEmpty() )
rear = NULL;
MakeEmpty() doesn't return a value, so you can't check it with an if ... You don't need to check anything either. MakeEmpty() will empty the queue, and get it ready for filling it again ...
In other words, you can just do :
MakeEmpty();
instead of the two lines above.
>> I'm sure the print function still isn't right
It looks fine to me :)
Do you have a test program to test the queue class ? That will help you a lot to figure out if the code is working, and if it does what you want it to do.
ASKER
I don't have a test program to run. I have to write one! That will be my next challenge. I didn't want to start that yet until I knew I had the methods mostly correct and understood them. It would have been pointless in my opinion and I would have been even more lost.
For the deQueue, I switched the true and false statements, is that what you were referring to?
So for MakeEmpty I'm not sure exactly how to call the function. Is what I have correct?
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_TYPE
#define QUEUE_TYPE
#include <iostream>
using std::cout; // generic output stream
using std::endl;
#include <new>
using std::bad_alloc;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
while (!IsEmpty() )
{
DeQueue(rear->next);
}
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::EnQue
{
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
}
rear = tempPtr;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
status = false;
}
else
{
rear->next = tempPtr->next;
status = true;
}
item = tempPtr->info;
delete tempPtr;
return status;
}
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
while ( tempPtr != rear )
{
cout << tempPtr->info << endl;
tempPtr = tempPtr->next;
}
cout << tempPtr->info << endl;
}
else
cout << "The queue is empty." << endl;
}
//assigns one queue to another
template<class ItemType>
QueueType& QueueType<ItemType>::Opera
{
MakeEmpty();
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
EnQueue(rightPtr->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
}
#endif
For the deQueue, I switched the true and false statements, is that what you were referring to?
So for MakeEmpty I'm not sure exactly how to call the function. Is what I have correct?
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_TYPE
#define QUEUE_TYPE
#include <iostream>
using std::cout; // generic output stream
using std::endl;
#include <new>
using std::bad_alloc;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
while (!IsEmpty() )
{
DeQueue(rear->next);
}
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::EnQue
{
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
}
rear = tempPtr;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
status = false;
}
else
{
rear->next = tempPtr->next;
status = true;
}
item = tempPtr->info;
delete tempPtr;
return status;
}
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
while ( tempPtr != rear )
{
cout << tempPtr->info << endl;
tempPtr = tempPtr->next;
}
cout << tempPtr->info << endl;
}
else
cout << "The queue is empty." << endl;
}
//assigns one queue to another
template<class ItemType>
QueueType& QueueType<ItemType>::Opera
{
MakeEmpty();
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
EnQueue(rightPtr->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
}
#endif
>> For the deQueue, I switched the true and false statements, is that what you were referring to?
No, not really. Let's back up ... You have this at the beginning of the method :
if ( !IsEmpty() )
and then there's a block handling the case where the queue is not empty. However, you didn't cover the case where the queue IS empty. And that's precisely when you want to return false. In all the other cases (when the queue isn't empty), you want to return true.
>> So for MakeEmpty I'm not sure exactly how to call the function. Is what I have correct?
Yes. In the assignment operator, you now have :
MakeEmpty();
which empties the queue entirely. That's the way you want it to be, because what you do next, is fill up the queue with the same nodes as the "right" queue.
About the implementation of the MakeEmpty method : that looks ok, except for one little detail : the parameter you pass to the DeQueue method call : take a look at what parameter the method expects, and which one you're passing it ... :
bool QueueType<ItemType>::DeQue
vs. :
DeQueue(rear->next);
>> I don't have a test program to run. I have to write one! That will be my next challenge. I didn't want to start that yet until I knew I had the methods mostly correct and understood them. It would have been pointless in my opinion and I would have been even more lost.
Well, it depends on how you approach the problem. You are trying to write code without ever testing it until you're fairly certain that it will work. That's ok, but sometimes it's easier to test the bits of code you already wrote to make sure that those bits are correct, and that you can continue implementing the rest. In other words, you're building a program one little bit at a time, and after completing a part, you want to test whether it works as you expect. And then you can continue with the other parts.
I'm not saying that your approach is bad - I'm saying that verifying that code works while you're writing the code, re-assures you that what you're doing is good, and avoids that you make the same mistake more than once, or even worse : that you base yourself on incorrect code.
No, not really. Let's back up ... You have this at the beginning of the method :
if ( !IsEmpty() )
and then there's a block handling the case where the queue is not empty. However, you didn't cover the case where the queue IS empty. And that's precisely when you want to return false. In all the other cases (when the queue isn't empty), you want to return true.
>> So for MakeEmpty I'm not sure exactly how to call the function. Is what I have correct?
Yes. In the assignment operator, you now have :
MakeEmpty();
which empties the queue entirely. That's the way you want it to be, because what you do next, is fill up the queue with the same nodes as the "right" queue.
About the implementation of the MakeEmpty method : that looks ok, except for one little detail : the parameter you pass to the DeQueue method call : take a look at what parameter the method expects, and which one you're passing it ... :
bool QueueType<ItemType>::DeQue
vs. :
DeQueue(rear->next);
>> I don't have a test program to run. I have to write one! That will be my next challenge. I didn't want to start that yet until I knew I had the methods mostly correct and understood them. It would have been pointless in my opinion and I would have been even more lost.
Well, it depends on how you approach the problem. You are trying to write code without ever testing it until you're fairly certain that it will work. That's ok, but sometimes it's easier to test the bits of code you already wrote to make sure that those bits are correct, and that you can continue implementing the rest. In other words, you're building a program one little bit at a time, and after completing a part, you want to test whether it works as you expect. And then you can continue with the other parts.
I'm not saying that your approach is bad - I'm saying that verifying that code works while you're writing the code, re-assures you that what you're doing is good, and avoids that you make the same mistake more than once, or even worse : that you base yourself on incorrect code.
ASKER
Is the DeQueue method correct now?
Did I make the right adjustment to the call for DeQueue in the MakeEmpty method?
I agree with testing as you go. I'm starting to work on the shell of a test program now.
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_TYPE
#define QUEUE_TYPE
#include <iostream>
using std::cout; // generic output stream
using std::endl;
#include <new>
using std::bad_alloc;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
while (!IsEmpty() )
{
DeQueue(item);
}
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::EnQue
{
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
}
rear = tempPtr;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
status = true;
}
else
{
rear->next = tempPtr->next;
status = true;
}
item = tempPtr->info;
}
else
status = false;
delete tempPtr;
return status;
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
while ( tempPtr != rear )
{
cout << tempPtr->info << endl;
tempPtr = tempPtr->next;
}
cout << tempPtr->info << endl;
}
else
cout << "The queue is empty." << endl;
}
//assigns one queue to another
template<class ItemType>
QueueType& QueueType<ItemType>::Opera
{
MakeEmpty();
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
EnQueue(rightPtr->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
}
#endif
Did I make the right adjustment to the call for DeQueue in the MakeEmpty method?
I agree with testing as you go. I'm starting to work on the shell of a test program now.
// Header file for Queue ADT - Linked
// Template class for dynamically allocated queue - rear pointer tracked only
// Nodes for queue are allocated and deallocated as needed
#ifndef QUEUE_TYPE
#define QUEUE_TYPE
#include <iostream>
using std::cout; // generic output stream
using std::endl;
#include <new>
using std::bad_alloc;
//------------------------
// Class specification
template <class ItemType>
class QueueType
{
public:
QueueType(); // Class constructor.
QueueType(const QueueType &); // Copy constructor
~QueueType(); // Class destructor.
void MakeEmpty(); // Function: Initializes the queue to an empty state.
bool IsEmpty() const; // Function: Determines whether the queue is empty.
bool IsFull() const; // Function: Determines whether the queue is full.
bool Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue.
bool Dequeue(ItemType & item); // Function: Removes front item from the queue
void Print(); // Function: Prints contents of queue to an output stream
QueueType& operator= (const QueueType &); // Assigns one queue to another
private:
struct NodeType
{
ItemType info;
NodeType * next;
};
NodeType* rear;
};
//class constructor
template<class ItemType>
QueueType<ItemType>::Queue
{
rear = NULL;
}
//------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::Queue
if (right.rear != NULL) {
NodeType * rightPtr = right.rear->next;
rear = NULL;
do {
Enqueue (rightPtr->info);
rightPtr = rightPtr->next;
}while (rightPtr != right.rear->next);
}
else
rear = NULL;
}
//------------------------
// Function: IsFull - // Returns true if there is no room for another ItemType
// on the free store; false otherwise.
// Pre: Queue has been initialized
// Post: Queue is not modified
template<class ItemType>
bool QueueType<ItemType>::IsFul
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc &memoryAllocationException
{
return true;
}
}
//class destructor
template<class ItemType>
QueueType<ItemType>::~Queu
{
MakeEmpty();
}
//initializes the queue to an empty state
template<class ItemType>
void QueueType<ItemType>::MakeE
{
while (!IsEmpty() )
{
DeQueue(item);
}
}
//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmp
{
return ( rear == NULL);
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::EnQue
{
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
}
rear = tempPtr;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
status = true;
}
else
{
rear->next = tempPtr->next;
status = true;
}
item = tempPtr->info;
}
else
status = false;
delete tempPtr;
return status;
}
//Prints the contents of the queue to the screen
template<class ItemType>
void QueueType<ItemType>::Print
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
while ( tempPtr != rear )
{
cout << tempPtr->info << endl;
tempPtr = tempPtr->next;
}
cout << tempPtr->info << endl;
}
else
cout << "The queue is empty." << endl;
}
//assigns one queue to another
template<class ItemType>
QueueType& QueueType<ItemType>::Opera
{
MakeEmpty();
if ( right.rear != NULL )
{
NodeType *rightPtr = right.rear->next;
do
{
EnQueue(rightPtr->info);
rightPtr = rightPtr->next;
}
while ( rightPtr != right.rear->next );
}
}
#endif
>> Is the DeQueue method correct now?
Not really. Take it one step at a time. First understand what the method needs to do, then understand what it's doing right now, and find the differences.
A practical problem is that you haven't defined what status is ...
Another problem is that the delete tempPtr; you have might delete an invalid (or null) pointer - you don't want to do that.
In other words, what you need to do, is have two blocks of code : one that handles the case where the queue is empty, and another that handles the case where it's not empty. Keep these two separate - they don't need to have common code.
You don't need a status value either, because the return value is true in one case, and false in the other ...
>> Did I make the right adjustment to the call for DeQueue in the MakeEmpty method?
Almost. But you're passing the parameter item to the function without defining what item is ...
Not really. Take it one step at a time. First understand what the method needs to do, then understand what it's doing right now, and find the differences.
A practical problem is that you haven't defined what status is ...
Another problem is that the delete tempPtr; you have might delete an invalid (or null) pointer - you don't want to do that.
In other words, what you need to do, is have two blocks of code : one that handles the case where the queue is empty, and another that handles the case where it's not empty. Keep these two separate - they don't need to have common code.
You don't need a status value either, because the return value is true in one case, and false in the other ...
>> Did I make the right adjustment to the call for DeQueue in the MakeEmpty method?
Almost. But you're passing the parameter item to the function without defining what item is ...
ASKER
Ok, clearly I'm not understanding the DeQueue function. Is this any closer or am I completely lost?
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
}
else
{
rear->next = tempPtr->next;
}
item = tempPtr->info;
delete tempPtr;
}
else
{
cout << "The queue is empty " << endl;
item = rear;
}
return item;
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
}
else
{
rear->next = tempPtr->next;
}
item = tempPtr->info;
delete tempPtr;
}
else
{
cout << "The queue is empty " << endl;
item = rear;
}
return item;
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Any better?
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
bool status = false;
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
}
else
{
rear->next = tempPtr->next;
status = true;
}
item = tempPtr->info;
}
else
{
cout << "The queue is empty " << endl;
status = false;
}
return status;
}
//Removes front item from the queue
template<class ItemType>
bool QueueType<ItemType>::DeQue
{
bool status = false;
NodeType *tempPtr;
if ( !IsEmpty() )
{
tempPtr = rear->next;
if ( tempPtr == rear )
{
rear = NULL;
}
else
{
rear->next = tempPtr->next;
status = true;
}
item = tempPtr->info;
}
else
{
cout << "The queue is empty " << endl;
status = false;
}
return status;
}
>> Any better?
Almost ... Just one more detail : the status has to be true for the whole if ( !IsEmpty() ) block, so also when tempPtr == rear.
Almost ... Just one more detail : the status has to be true for the whole if ( !IsEmpty() ) block, so also when tempPtr == rear.
ASKER
I realized that I had no return status on my Enqueue function. Would this be correct?
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::Enque
{
bool status = false;
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
status = true;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
status = true;
}
rear = tempPtr;
return status;
}
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::Enque
{
bool status = false;
NodeType *tempPtr = new NodeType;
tempPtr->item = newItem;
if ( IsEmpty() )
tempPtr->next = tempPtr;
status = true;
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
status = true;
}
rear = tempPtr;
return status;
}
>> I realized that I had no return status on my Enqueue function.
Good catch - I missed that :)
>> Would this be correct?
Almost. Take care with the {}'s around if blocks :
if ( IsEmpty() )
tempPtr->next = tempPtr;
status = true;
is NOT the same as :
if ( IsEmpty() ) {
tempPtr->next = tempPtr;
status = true;
}
And you probably want to return false in case the memory allocation failed.
Good catch - I missed that :)
>> Would this be correct?
Almost. Take care with the {}'s around if blocks :
if ( IsEmpty() )
tempPtr->next = tempPtr;
status = true;
is NOT the same as :
if ( IsEmpty() ) {
tempPtr->next = tempPtr;
status = true;
}
And you probably want to return false in case the memory allocation failed.
ASKER
I'm starting the test program now so that I can test the methods. I'm not sure if I'm doing this right tho. I get the following compile error when I tried to compile this. What am I doing wrong?
case 1: //Enqueue an item
cout << "Enter an integer to Enqueue: ";
cin >> item;
item = q1.Enqueue(item);
cout << item << " is enqueued." << endl;
break;
queue.h: In member function `bool QueueType<ItemType>::Enque
prog5a.cpp:30: instantiated from here
queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
case 1: //Enqueue an item
cout << "Enter an integer to Enqueue: ";
cin >> item;
item = q1.Enqueue(item);
cout << item << " is enqueued." << endl;
break;
queue.h: In member function `bool QueueType<ItemType>::Enque
prog5a.cpp:30: instantiated from here
queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
>> queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
Well, there is no member named item in the NodeType struct, but you're trying to reference it.
How did you define item ?
Btw, EnQueue returns a bool - you shouldn't save the return value in item ! You should only check the return value whether it's true ... if it's false, then the operation failed.
Can you show a bit more code ?
Well, there is no member named item in the NodeType struct, but you're trying to reference it.
How did you define item ?
Btw, EnQueue returns a bool - you shouldn't save the return value in item ! You should only check the return value whether it's true ... if it's false, then the operation failed.
Can you show a bit more code ?
ASKER
I'm using the queue.h file that's posted above and creating a new .cpp file for the test program. I have only just started with it. But here is the top 1/2 of it.
#include <iostream>
using namespace std;
#include "queue.h"
int menu();
int main ()
{
system("clear");
int item;
int opt;
QueueType<int> q1, q2;
cout << "Please enter a selection. " << endl;
cin >> opt;
while ( opt > 0 && opt < 9 )
opt = menu();
switch(opt)
{
case 1: //Enqueue an item
cout << "Enter an integer to Enqueue: ";
cin >> item;
item = q1.Enqueue(item);
cout << item << " is enqueued." << endl;
break;
case 2 : //Dequeue an item
break;
case 3: // check for IsEmpty
break;
case 4: // check for IsFull
break;
case 5: // print the queue
break;
case 6: //copy the queue
#include <iostream>
using namespace std;
#include "queue.h"
int menu();
int main ()
{
system("clear");
int item;
int opt;
QueueType<int> q1, q2;
cout << "Please enter a selection. " << endl;
cin >> opt;
while ( opt > 0 && opt < 9 )
opt = menu();
switch(opt)
{
case 1: //Enqueue an item
cout << "Enter an integer to Enqueue: ";
cin >> item;
item = q1.Enqueue(item);
cout << item << " is enqueued." << endl;
break;
case 2 : //Dequeue an item
break;
case 3: // check for IsEmpty
break;
case 4: // check for IsFull
break;
case 5: // print the queue
break;
case 6: //copy the queue
>> while ( opt > 0 && opt < 9 )
>> opt = menu();
What's this supposed to do ?
>> queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
Take a look at this line in your EnQueue method :
tempPtr->item = newItem;
>> opt = menu();
What's this supposed to do ?
>> queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
Take a look at this line in your EnQueue method :
tempPtr->item = newItem;
ASKER
It will end up being a menu function. I don't have it all done yet. I'm still trying to understand how to call the functions and at least get one of them working so I can understand the rest of them. I don't understand your reference to the line in the Enqueue method. What I'm trying to do is prompt the user to enter an integer and then call the enqueue function to put it into the queue.
>> I don't understand your reference to the line in the Enqueue method.
tempPtr is a pointer to a NodeType struct. The NodeType struct is defined like this :
struct NodeType
{
ItemType info;
NodeType * next;
};
It has two fields : info which is of type ItemType, and next which is a pointer to a NodeType struct.
Now, with this line :
tempPtr->item = newItem;
you try to access the item field of the NodeType struct pointed to by tempPtr, and you try to set it to newItem.
However, there is no such field in the NodeType struct ... and so you get this error :
>> queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
>> What I'm trying to do is prompt the user to enter an integer and then call the enqueue function to put it into the queue.
The way you call it is fine :
cout << "Enter an integer to Enqueue: ";
cin >> item;
item = q1.Enqueue(item);
cout << item << " is enqueued." << endl;
except for the small remark I made earlier : EnQueue returns a bool - you don't want to save that value in item. Instead, you want to use an if to check whether the return value was true or not.
>> It will end up being a menu function.
I should have made myself more clear :
while ( opt > 0 && opt < 9 )
opt = menu();
will call the menu() method for as long as opt is between 0 and 9, and store the returned value in opt. So, this loop will continue until menu() returns a value that is either <= 0 or >= 9. I don't think that's what you want ... You probably want the opposite, right ?
tempPtr is a pointer to a NodeType struct. The NodeType struct is defined like this :
struct NodeType
{
ItemType info;
NodeType * next;
};
It has two fields : info which is of type ItemType, and next which is a pointer to a NodeType struct.
Now, with this line :
tempPtr->item = newItem;
you try to access the item field of the NodeType struct pointed to by tempPtr, and you try to set it to newItem.
However, there is no such field in the NodeType struct ... and so you get this error :
>> queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
>> What I'm trying to do is prompt the user to enter an integer and then call the enqueue function to put it into the queue.
The way you call it is fine :
cout << "Enter an integer to Enqueue: ";
cin >> item;
item = q1.Enqueue(item);
cout << item << " is enqueued." << endl;
except for the small remark I made earlier : EnQueue returns a bool - you don't want to save that value in item. Instead, you want to use an if to check whether the return value was true or not.
>> It will end up being a menu function.
I should have made myself more clear :
while ( opt > 0 && opt < 9 )
opt = menu();
will call the menu() method for as long as opt is between 0 and 9, and store the returned value in opt. So, this loop will continue until menu() returns a value that is either <= 0 or >= 9. I don't think that's what you want ... You probably want the opposite, right ?
ASKER
>>It has two fields : info which is of type ItemType, and next which is a pointer to a NodeType struct.
>>Now, with this line :
>> tempPtr->item = newItem;
>>you try to access the item field of the NodeType struct pointed to by tempPtr, and you try to set it to >>newItem.
>>However, there is no such field in the NodeType struct ... and so you get this error :
>> queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
So I need to change it to: tempPtr->info = newItem ?
Also, when I call my Dequeue method, it's not popping off items in the right order. This is what I wrote for my test program so far. Please ignore the menu() and while loops. I didn't post the rest of the code that will make that understandable for you right now.
#include <iostream>
using namespace std;
#include "queue.h"
int menu();
int main ()
{
system("clear");
int item;
int opt = 1;
QueueType<int> q1, q2;
while ( opt > 0 && opt < 9 )
{
opt = menu();
switch(opt)
{
case 1: //Enqueue an item
cout << "Enter an integer to Enqueue: ";
cin >> item;
q1.Enqueue(item);
cout << item << " is enqueued." << endl << endl;
break;
case 2 : //Dequeue an item
cout << item << " has been removed from the Queue." << endl << endl;
q1.Dequeue(item);
break;
>>Now, with this line :
>> tempPtr->item = newItem;
>>you try to access the item field of the NodeType struct pointed to by tempPtr, and you try to set it to >>newItem.
>>However, there is no such field in the NodeType struct ... and so you get this error :
>> queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
So I need to change it to: tempPtr->info = newItem ?
Also, when I call my Dequeue method, it's not popping off items in the right order. This is what I wrote for my test program so far. Please ignore the menu() and while loops. I didn't post the rest of the code that will make that understandable for you right now.
#include <iostream>
using namespace std;
#include "queue.h"
int menu();
int main ()
{
system("clear");
int item;
int opt = 1;
QueueType<int> q1, q2;
while ( opt > 0 && opt < 9 )
{
opt = menu();
switch(opt)
{
case 1: //Enqueue an item
cout << "Enter an integer to Enqueue: ";
cin >> item;
q1.Enqueue(item);
cout << item << " is enqueued." << endl << endl;
break;
case 2 : //Dequeue an item
cout << item << " has been removed from the Queue." << endl << endl;
q1.Dequeue(item);
break;
>> So I need to change it to: tempPtr->info = newItem ?
Indeed :)
>> Also, when I call my Dequeue method, it's not popping off items in the right order.
What input did you give, and what output did you get ?
Indeed :)
>> Also, when I call my Dequeue method, it's not popping off items in the right order.
What input did you give, and what output did you get ?
Do you still have this line in your EnQueue method :
rear = tempPtr;
??? That line should only be executed when the queue was empty at the start of the method.
rear = tempPtr;
??? That line should only be executed when the queue was empty at the start of the method.
ASKER
is it because In my test program I'm using the statement:
cout << item << " has been removed from the Queue." << endl << endl;
item is not returning the corrrect integer. If I enter 9 and then 8. it says it's dequeing the 8 where it should display the 9 because of FIFO correct? But when I call my print method, it shows that the 9 actually was dequeued. So I think I'm not using the COUT statement properly in my test program.
cout << item << " has been removed from the Queue." << endl << endl;
item is not returning the corrrect integer. If I enter 9 and then 8. it says it's dequeing the 8 where it should display the 9 because of FIFO correct? But when I call my print method, it shows that the 9 actually was dequeued. So I think I'm not using the COUT statement properly in my test program.
ASKER
Yes I do:
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::Enque
{
bool status = false;
NodeType *tempPtr = new NodeType;
tempPtr->info = newItem;
tempPtr->next = NULL;
if ( IsEmpty() )
{
tempPtr->next = tempPtr;
status = true;
}
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
status = true;
}
rear = tempPtr;
return status;
}
So I need to move it into the if (IsEmpty()) block?
//Adds newItem to the rear of the queue
template<class ItemType>
bool QueueType<ItemType>::Enque
{
bool status = false;
NodeType *tempPtr = new NodeType;
tempPtr->info = newItem;
tempPtr->next = NULL;
if ( IsEmpty() )
{
tempPtr->next = tempPtr;
status = true;
}
else
{
tempPtr->next = rear->next;
rear->next = tempPtr;
status = true;
}
rear = tempPtr;
return status;
}
So I need to move it into the if (IsEmpty()) block?
>> So I need to move it into the if (IsEmpty()) block?
Yes, and I think that should solve your problem (I don't have your latest code, so I can't be sure ;) ).
Note that in the else block you already have this line that links it to the rear :
rear->next = tempPtr;
Yes, and I think that should solve your problem (I don't have your latest code, so I can't be sure ;) ).
Note that in the else block you already have this line that links it to the rear :
rear->next = tempPtr;
ASKER
I'm going to open up a fresh question. You certainly deserve more points for your efforts in trying to help!
1) your DeQueue function is missing the proper returns. You have to return a value in all cases (so also if the queue is empty), and the return value is of type bool. The value retrieved from the queue has to be put in the item parameter (ie. return item; is not correct).
2) You haven't implemented MakeEmpty(), but I'm sure you know that ;)
3) in the assignment operator (operator=), be carefull with setting rear to NULL without checking if it already has a queue attached to it ... Rather call MakeEmpty().
4) The EnQueue(right->info); line in the assignment operator has a problem too ;) Compare to your copy constructor to spot it ...
5) You're missing the final } for the assignment operator.
There might be other things, but on first sight, the rest of your code looks ok.
Now, for the Print() method :
>> I'm not sure how to implement the print function.
You can loop over the queue in the same way as you did in the copy constructor, and print the info value for every node you pass until you arrive at the rear of the queue. You can do output with cout :
http://www.cplusplus.com/doc/tutorial/basic_io.html
Does that help you further ? If not, can you tell what you're stuck at ?