Link to home
Start Free TrialLog in
Avatar of PMG76
PMG76Flag for United States of America

asked on

Circular linked Queue using 1 pointer

Please look over my Enqueue, DeQueue and Print methods carefully as these are the 3 methods that I am currently trying to test.  In my test driver program if I enter a 9 and then an 8 for example.  My cout statement is telling me that 8 was dequeued.  In fact, the 9 should be listed as the item dequed since it was entered first.  That is my first problem.  Also, then after I dequeue an item, I call my Print method and it's telling me that it's empty when there should still be 1 more item in the queue.

// 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_H
#define QUEUE_H
#include <iostream>
using namespace std;
#include <new>
using std::bad_alloc;

//int item;
   
//-----------------------------------------------------------------
// 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->info);
    }
}

//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)
{
    bool status = false;
    NodeType *tempPtr = new NodeType;
    tempPtr->info = newItem;

    if ( IsEmpty() )
    {
        rear = tempPtr;
        rear->next = tempPtr;
        status = true;
    }
    else
    {
        tempPtr->next = rear->next;
        rear->next = tempPtr;
        rear = rear->next;
        status = true;
    }
    return status;
}

//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;
            status = true;
        }  
        else
        {
            rear->next = tempPtr->next;
            status = true;
        }
        item = tempPtr->info;
    }
    else
    {
        cout << "The queue is empty " << endl;
        status = false;
    }
    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;
        cout << "The queue contains: ";
        while ( tempPtr != rear )
        {
            cout << tempPtr->info << " ";
            tempPtr = tempPtr->next;
        }

        cout << tempPtr->info << endl << endl;
    }
    else
        cout << "The queue is empty." << endl << endl;
}

//assigns one queue to another
    template<class ItemType>
QueueType<ItemType>& 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


#include <iostream>
using namespace std;
#include "queue.h"
int menu();

int main ()
{
    system("clear");
    int item;
    int opt = 1;
    bool status;
    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
                status = q1.Dequeue(item);
                if (q1.Dequeue(item))
                {
                cout << item << " has been removed from the Queue." << endl << endl;
                }
                else
                    cout << "There are no items to Dequeue." << endl << endl;
                break;

            case 3: // check for IsEmpty

                break;

            case 4: // check for IsFull

                break;

            case 5: // print the queue
                q1.Print();
                break;

            case 6: //copy the queue

                break;

            case 7: //assign one queue to another

                break;

            case 8: // clear all items from the queue

                break;

            case 0: //quit the program
                break;
        }
    }
    return 0;
}

//menu function for the main menu of the program for user selection
int menu()
{
    int opt = 1;
    do
    {
        if ( opt < 0 || opt > 8 )
            cout << "You have entered an invalid number." << endl;

        cout << "Select one of the following options: " << endl;
        cout << "\t1. Enqueue an item " << endl;
        cout << "\t2. Dequeue an item " << endl;
        cout << "\t3. Is queue empty? " << endl;
        cout << "\t4. Is queue full? " << endl;
        cout << "\t5. Print the queue " << endl;
        cout << "\t6. Copy the queue " << endl;
        cout << "\t7. Assign one queue to another " << endl;
        cout << "\t8. Clear all items from the queue " << endl;
        cout << "\t0. Quit the program " << endl;
        cin >> opt;
    }
    while ( opt < 0 || opt > 8 );
    return opt;
}


Avatar of PMG76
PMG76
Flag of United States of America image

ASKER

Here is an example of what I'm talking about from my test driver program.  It's almost like the first value being entered is somehow not getting stored.

The queue contains: 9 8 7 6 5

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program
2
8 has been removed from the Queue.

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program
5
The queue contains: 7 6 5

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program

Avatar of Infinity08
I see you added this to the else block in the EnQueue method now :

        rear = rear->next;

You shouldn't have ... Just this is good :

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

    if ( IsEmpty() )
    {
        rear = tempPtr;
        rear->next = tempPtr;
        status = true;
    }
    else
    {
        tempPtr->next = rear->next;
        rear->next = tempPtr;
        status = true;
    }
    return status;
}
Avatar of PMG76

ASKER

I guess the first value is actually getting stored, but something in my Dequeue I suspect is not performing correctly and I'm lost as to what it is.  It seems to be taking things off two at a time.

The queue contains: 9 8

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program
2
8 has been removed from the Queue.

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program
5
The queue is empty.

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program

Avatar of PMG76

ASKER

Removing that line made it so that my cout is telling me it is dequing the right item, but it still seems to be taking two items from the queue.  If i have a 9 and an 8 and deque 1 item it says it's empty.
The queue contains: 8 9

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program
2
9 has been removed from the Queue.

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program
5
The queue is empty.

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program
Avatar of PMG76

ASKER

actually I guess it's not returning the right value.  it's still not performing correctly.

The queue contains: 6 7 8 9

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program
2
7 has been removed from the Queue.

Select one of the following options:
        1. Enqueue an item
        2. Dequeue an item
        3. Is queue empty?
        4. Is queue full?
        5. Print the queue
        6. Copy the queue
        7. Assign one queue to another
        8. Clear all items from the queue
        0. Quit the program

Avatar of PMG76

ASKER

Another thing I noticed is that when I call the print method my items are not listed correctly.  It should be listed the other way around.  like 9 8 7 ,  not 7 8 9.  Any ideas?
ASKER CERTIFIED SOLUTION
Avatar of itsmeandnobodyelse
itsmeandnobodyelse
Flag of Germany image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
BTW, if making it a stack you would need to change print function so that it prints rear->info before the loop (not after as it is now).
Did you also make the modification I mentioned ?
Avatar of PMG76

ASKER

I have a question about my copy constructor.  I'm sure it's in my syntax.  I'm not sure exactly how to set up this function in my test program.  Here is what I have, but clearly not right.

case 6: //copy the queue
                QueueType<int> q2(q1);
                cout << "Original queue = " << endl;
                q1.print();
                cout << "Test of copy constructor: New queue: " << endl;
                q2.print();
                break;
>>>> Did you also make the modification I mentioned ?
As far as I see (now) your suggestion was to *not* changing the rear (thus making it a LIFO queue).

But the statement

    rear = rear->next;

already was added in code of the previous question. It wasn't in the else branch but below the if/else block what had the same effect to turn a LIFO to a FIFO.
>>>> Here is what I have, but clearly not right.

You have to turn 'print' by 'Print' and make curly brackets {} around the code of case 6  

    case 6:
    {
         ...
    }
    break;


You must put it into a block so that the object q2 can be orderly destroyed.

Regards, Alex

>> As far as I see (now) your suggestion was to *not* changing the rear (thus making it a LIFO queue).

You are absolutely right ... I got confused by the EnQueue and DeQueue method names lol (I'm more used to the conventional push and pop heh) ... my apologies :)
Avatar of PMG76

ASKER

Thank you!  Now, I'm trying to test my copy constructor and I get the following compile error with the following code:

case 7: //assign one queue to another
                {
                q1=q2;
                cout << "Original queue = " << endl;
                q1.Print();
                cout << "Test of copy constructor: New queue: " << endl;
                q2.Print();
                }
                break;


queue.h: In member function `QueueType<ItemType>& QueueType<ItemType>::operator=(const QueueType<ItemType>&) [with ItemType = int]':
prog5a.cpp:73:   instantiated from here
queue.h:214: warning: control reaches end of non-void function

Add this line at the end of the operator= :

        return *this;
>>>> q1=q2;

I suppose that is the statement which is wrong as q2 wasn't defined yet.

You would need to create an empty queue q2 first and then make the assignment:

    QueueType<int> q2;  // empty queue
    q2 = q1;   // now assign q1

>>>> return *this;        

The return value of operator= is  a reference to the 'this' object. With that you could do


    QueueType<int> q2, q3, q4;  // empty queues
    q2 = q3 = q4 = q1;

cause each of these operations returns a valid 'QueueType<int>&'  (beginning from the right).