troubleshooting Question

Circular linked Queue using 1 pointer

Avatar of PMG76
PMG76Flag for United States of America asked on
C++
17 Comments1 Solution818 ViewsLast Modified:
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;
}


ASKER CERTIFIED SOLUTION
itsmeandnobodyelse

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Join our community to see this answer!
Unlock 1 Answer and 17 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 17 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros