?
Solved

Circular linked Queue using 1 pointer to the rear

Posted on 2007-10-20
26
Medium Priority
?
524 Views
Last Modified: 2013-12-14
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>::QueueType()
{
rear = NULL;
}

//-----------------------------------------------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::QueueType(const QueueType<ItemType> & right) {

    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>::IsFull() const

{
    NodeType* location;
    try
    {
        location = new NodeType;
        delete location;
        return false;
    }
    catch(bad_alloc &memoryAllocationException)
    {
        return true;
    }
}

//class destructor
    template<class ItemType>
QueueType<ItemType>::~QueueType()
{
    MakeEmpty();
}

//initializes the queue to an empty state
    template<class ItemType>
void QueueType<ItemType>::MakeEmpty()

{

}

//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmpty() const
{
    return ( rear == NULL);
}

//Adds newItem to the rear of the queue
    template<class ItemType>
bool QueueType<ItemType>::EnQueue(ItemType newItem)
{
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>::DeQueue(ItemType & item)
{
   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>::Operator=(const QueueType<ItemType> &right)
{
    rear = NULL;
    if ( right.rear != NULL )
    {
        NodeType *rightPtr = right.rear->next;
        do
        {
            EnQueue(right->info);
            rightPtr = rightPtr->next;
        }
        while ( rightPtr != right.rear->next );
    }

#endif
0
Comment
Question by:PMG76
  • 13
  • 13
26 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 20117387
A few comments first :

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 ?
0
 

Author Comment

by:PMG76
ID: 20117708
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>::QueueType()
{
rear = NULL;
}

//-----------------------------------------------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::QueueType(const QueueType<ItemType> & right) {

    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>::IsFull() const

{
    NodeType* location;
    try
    {
        location = new NodeType;
        delete location;
        return false;
    }
    catch(bad_alloc &memoryAllocationException)
    {
        return true;
    }
}

//class destructor
    template<class ItemType>
QueueType<ItemType>::~QueueType()
{
    MakeEmpty();
}

//initializes the queue to an empty state
    template<class ItemType>
void QueueType<ItemType>::MakeEmpty()

{
NodeType *tempPtr;
while ( rear != NULL )
{
   

    delete tempPtr;
}
rear = NULL;
}

//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmpty() const
{
    return ( rear == NULL);
}

//Adds newItem to the rear of the queue
    template<class ItemType>
bool QueueType<ItemType>::EnQueue(ItemType newItem)
{
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>::DeQueue(ItemType & item)
{
   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>::Operator=(const QueueType<ItemType> &right)
{
    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
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20117738
>> 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.
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

Author Comment

by:PMG76
ID: 20117786
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>::QueueType()
{
rear = NULL;
}

//-----------------------------------------------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::QueueType(const QueueType<ItemType> & right) {

    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>::IsFull() const

{
    NodeType* location;
    try
    {
        location = new NodeType;
        delete location;
        return false;
    }
    catch(bad_alloc &memoryAllocationException)
    {
        return true;
    }
}

//class destructor
    template<class ItemType>
QueueType<ItemType>::~QueueType()
{
    MakeEmpty();
}

//initializes the queue to an empty state
    template<class ItemType>
void QueueType<ItemType>::MakeEmpty()

{
while (!IsEmpty() )
{
DeQueue(rear->next);
}
}

//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmpty() const
{
    return ( rear == NULL);
}

//Adds newItem to the rear of the queue
    template<class ItemType>
bool QueueType<ItemType>::EnQueue(ItemType newItem)
{
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>::DeQueue(ItemType & item)
{
   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>::Operator=(const QueueType<ItemType> &right)
{
    MakeEmpty();
        if ( right.rear != NULL )
    {
        NodeType *rightPtr = right.rear->next;
        do
        {
            EnQueue(rightPtr->info);
            rightPtr = rightPtr->next;
        }
        while ( rightPtr != right.rear->next );
    }
}
#endif
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20117819
>> 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>::DeQueue(ItemType & item)

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.
0
 

Author Comment

by:PMG76
ID: 20117854
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>::QueueType()
{
rear = NULL;
}

//-----------------------------------------------------------------
// Copy Constuctor
// Pre: "right" queue has been initialized
// Post: Queue contains all elements contained in "right" queue
template <class ItemType>
QueueType<ItemType>::QueueType(const QueueType<ItemType> & right) {

    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>::IsFull() const

{
    NodeType* location;
    try
    {
        location = new NodeType;
        delete location;
        return false;
    }
    catch(bad_alloc &memoryAllocationException)
    {
        return true;
    }
}

//class destructor
    template<class ItemType>
QueueType<ItemType>::~QueueType()
{
    MakeEmpty();
}

//initializes the queue to an empty state
    template<class ItemType>
void QueueType<ItemType>::MakeEmpty()

{
while (!IsEmpty() )
{
DeQueue(item);
}
}

//Determines whether the queue is empty or not
template<class ItemType>
bool QueueType<ItemType>::IsEmpty() const
{
    return ( rear == NULL);
}

//Adds newItem to the rear of the queue
    template<class ItemType>
bool QueueType<ItemType>::EnQueue(ItemType newItem)
{
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>::DeQueue(ItemType & item)
{
   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>::Operator=(const QueueType<ItemType> &right)
{
    MakeEmpty();
        if ( right.rear != NULL )
    {
        NodeType *rightPtr = right.rear->next;
        do
        {
            EnQueue(rightPtr->info);
            rightPtr = rightPtr->next;
        }
        while ( rightPtr != right.rear->next );
    }
}
#endif
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20117888
>> 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 ...
0
 

Author Comment

by:PMG76
ID: 20117971
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>::DeQueue(ItemType & item)
{
    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;
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 2000 total points
ID: 20118010
>> Is this any closer or am I completely lost?

I think you indeed got lost somewhere ... You need to make sure you understand everything before trying to make modifications, or you'll just make things worse ...

From the top : The DeQueue method takes one argument (item), which will be used to return the info value from the node to the caller. In other words, the caller of the method will call it like this :

        ItemType info;
        queue.DeQueue(info);
        // info now contains the value that was retrieved from the queue

The DeQueue method returns a bool. This bool will tell whether an info value could be retrieved from the queue or not. It tells whether the info value from the argument can be used or whether the queue was empty. So, the complete way of calling this method will be :

        ItemType info;
        if (queue.DeQueue(info)) {
            // info now contains the value that was retrieved from the queue
        }
        else {
            // the queue was empty, so the value in info should not be used
        }

This should explain clearly what the method has to do. Now, your job is to implement the DeQueue method in such a way that it behaves as explained above :

        1) if the queue is empty, it returns false
        2) if the queue is not empty, then :
                a. it gets the info value from the first queue node, and puts it in the item argument
                b. it removes that node from the queue
                c. it returns true

This is the algorithm you can use to implement the DeQueue method. You have two options :

         1) you can compare the current implementation with the above algorithm, and spot the mistakes
         2) you can start over with the implementation
0
 

Author Comment

by:PMG76
ID: 20118193
Any better?

//Removes front item from the queue
    template<class ItemType>
bool QueueType<ItemType>::DeQueue(ItemType & item)
{
    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;
}
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20118271
>> Any better?

Almost ... Just one more detail : the status has to be true for the whole if ( !IsEmpty() ) block, so also when tempPtr == rear.
0
 

Author Comment

by:PMG76
ID: 20118633
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>::Enqueue(ItemType newItem)
{
    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;
}
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20118654
>> 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.
0
 

Author Comment

by:PMG76
ID: 20118824
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>::Enqueue(ItemType) [with ItemType = int]':
prog5a.cpp:30:   instantiated from here
queue.h:133: error: 'struct QueueType<int>::NodeType' has no member named 'item'
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20118870
>> 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 ?
0
 

Author Comment

by:PMG76
ID: 20118921
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
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20118942
>> 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;

0
 

Author Comment

by:PMG76
ID: 20118971
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.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20119095
>> 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 ?
0
 

Author Comment

by:PMG76
ID: 20122999
>>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;
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20123138
>> 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 ?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20123164
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.
0
 

Author Comment

by:PMG76
ID: 20123178
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.
0
 

Author Comment

by:PMG76
ID: 20123201
Yes I do:
//Adds newItem to the rear of the queue
    template<class ItemType>
bool QueueType<ItemType>::Enqueue(ItemType newItem)
{
    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?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 20123430
>> 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;
0
 

Author Comment

by:PMG76
ID: 20123484
I'm going to open up a fresh question.  You certainly deserve more points for your efforts in trying to help!
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
The viewer will learn how to use and create new code templates in NetBeans IDE 8.0 for Windows.
Suggested Courses

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question