Traversing queue in C++

Question

I have a C++ queue that I need to print. It's easy to print the first node and then delete it, then print the first node again which would then be the second node. But that would erase the entire list just to print it once... As a work around I created a temporary queue object which I passed to my print method and did the same thing as the first object, this would have been great except it's using pointers to make the queue dynamic, so deleting them from any object copied from the first is still deleting the same data. I'm not good with pointers yet but I'm sure there must be an easy way to do this, any suggestions?

Here's the code:

queue2 = queue1; // Temporary queue is assigned values of main queue
queue2.printQueue(); // Temporary queue is passed to print method

Here's my print method:

int numberPrinted = 0;
while (!isEmptyQueue())
{
 cout << numberPrinted + 1 << ": " << front() << "\n";
 deleteQueue();    
 numberPrinted++;
 }

Queue class file:

#ifndef H_linkedQueue
#define H_linkedQueue

#include <iostream>
#include <cassert>
#include "queueADT.h"

using namespace std;

//Definition of the node
template <class Type>
struct nodeType
{
    Type info;
    nodeType<Type> *link;
};


template <class Type>
class linkedQueueType: public queueADT<Type>
{
public:
    bool operator==
                    (const linkedQueueType<Type>& otherQueue); 

    bool isEmptyQueue() const;
      //Function to determine whether the queue is empty. 
      //Postcondition: Returns true if the queue is empty,
      //               otherwise returns false.

    bool isFullQueue() const;
      //Function to determine whether the queue is full. 
      //Postcondition: Returns true if the queue is full,
      //               otherwise returns false.

    void initializeQueue();
      //Function to initialize the queue to an empty state.
      //Postcondition: queueFront = NULL; queueRear = NULL

    Type front() const;
      //Function to return the first element of the queue.
      //Precondition: The queue exists and is not empty.
      //Postcondition: If the queue is empty, the program 
      //               terminates; otherwise, the first 
      //               element of the queue is returned. 

    Type back() const;
      //Function to return the last element of the queue.
      //Precondition: The queue exists and is not empty.
      //Postcondition: If the queue is empty, the program 
      //               terminates; otherwise, the last 
      //               element of the queue is returned.

    void addQueue(const Type& queueElement);
      //Function to add queueElement to the queue.
      //Precondition: The queue exists and is not full.
      //Postcondition: The queue is changed and queueElement
      //               is added to the queue.

    void deleteQueue();
      //Function  to remove the first element of the queue.
      //Precondition: The queue exists and is not empty.
      //Postcondition: The queue is changed and the first 
      //               element is removed from the queue.
    int numberOfNodes();
    // Return number of nodes in the queue.
    void printQueue();
    //Print the queue.

    linkedQueueType(); 
      //Default constructor

    linkedQueueType(const linkedQueueType<Type>& otherQueue); 
      //Copy constructor

    ~linkedQueueType(); 
      //Destructor

private:
    nodeType<Type> *queueFront; //pointer to the front of 
                                //the queue
    nodeType<Type> *queueRear;  //pointer to the rear of 
                                //the queue
    int count;
};

    //Default constructor
template<class Type>
linkedQueueType<Type>::linkedQueueType() 
{
    queueFront = NULL; //set front to null
    queueRear = NULL;  //set rear to null
} //end default constructor

template<class Type>
bool linkedQueueType<Type>::isEmptyQueue() const
{
    return(queueFront == NULL);
} //end 

template<class Type>
bool linkedQueueType<Type>::isFullQueue() const
{
    return false;
} //end isFullQueue

template <class Type>
void linkedQueueType<Type>::initializeQueue()
{
    nodeType<Type> *temp;

    while (queueFront!= NULL)  //while there are elements left
                               //in the queue
    {
        temp = queueFront;  //set temp to point to the 
                            //current node
        queueFront = queueFront->link;  //advance first to  
                                        //the next node
        delete temp;    //deallocate memory occupied by temp
    }

    queueRear = NULL;  //set rear to NULL
} //end initializeQueue


template <class Type>
void linkedQueueType<Type>::addQueue(const Type& newElement)
{
    nodeType<Type> *newNode;

    newNode = new nodeType<Type>;   //create the node

    newNode->info = newElement; //store the info
    newNode->link = NULL;  //initialize the link field to NULL

    if (queueFront == NULL) //if initially the queue is empty
    {
        queueFront = newNode;
        queueRear = newNode;
    }
    else        //add newNode at the end
    {
        queueRear->link = newNode;
        queueRear = queueRear->link;
    }
    count++;
}//end addQueue

template <class Type>
Type linkedQueueType<Type>::front() const
{
    assert(queueFront != NULL);
    return queueFront->info; 
} //end front

template <class Type>
Type linkedQueueType<Type>::back() const
{
    assert(queueRear!= NULL);
    return queueRear->info;
} //end back

template <class Type>
void linkedQueueType<Type>::deleteQueue()
{
    nodeType<Type> *temp;

    if (!isEmptyQueue())
    {
        temp = queueFront;  //make temp point to the 
                            //first node
        queueFront = queueFront->link; //advance queueFront 

        delete temp;    //delete the first node

        if (queueFront == NULL) //if after deletion the 
                                //queue is empty
            queueRear = NULL;   //set queueRear to NULL
        count--;
    }
    else
        cout << "Cannot remove from an empty queue" << endl;
}//end deleteQueue


    //Destructor
template <class Type>
linkedQueueType<Type>::~linkedQueueType() 
{
    //Write the definition of the destructor
} //end destructor

template <class Type> 
bool linkedQueueType<Type>::operator==
                    (const linkedQueueType<Type>& otherQueue)
{
    bool same = false;

    if (count == otherQueue.count)
        same = true;

    return same;

} //end assignment operator

    //copy constructor
template <class Type>
linkedQueueType<Type>::linkedQueueType
                 (const linkedQueueType<Type>& otherQueue) 
{
    //Write the definition of the copy constructor
}//end copy constructor
template <class Type> 
int linkedQueueType<Type>::numberOfNodes()
{
    return count;

} 

template <class Type> 
void linkedQueueType<Type>::printQueue()
{
    int numberPrinted = 0;
while (!isEmptyQueue())
{
 cout << numberPrinted + 1 << ": " << front() << "\n";
 deleteQueue();    
 numberPrinted++;
 }
}
#endif

Solution 1

Your queue's printQueue method already has access to the private internals of the queue. Instead of using the public interface to print the queue, just use the internal queueFront pointer and walk the list, printing each element.

Something like (pseudocode since this homework):

for(node* n = queueFront; n; n = n->next)
{
    // Print data from node n.
}

Solution 2

If you're using a queue class you wrote yourself, add an iterator to it. If you're using a queue class that already has an iterator, iterate through it to print it. If you're using a queue class that doesn't have an iterator, switch to a different queue class that does.

If you're using std::queue, switch to std::list or std::deque.

There's an example on cplusplus.com that shows how to iterate through a deque:

#include <iostream>
#include <deque>

int main ()
{
  std::deque<int> mydeque;

  for (int i=1; i<=5; i++) mydeque.push_back(i);

  std::cout << "mydeque contains:";

  std::deque<int>::iterator it = mydeque.begin();

  while (it != mydeque.end())
    std::cout << ' ' << *it++;

  std::cout << '\n';
  return 0;
}

Or:

for (std::deque<int>::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
  // print *it here

Solution 3

If the queue is your own code, and assuming you can iterate over its elements internally, you could give it a friend ostream& operator<<(ostream&, const your_queue_type&) and write the elements to the output stream.

class Queue
{
 public:
  // methods
 friend ostream& operator<<(ostream& o, const Queue& q)
 {
   // iterate over nodes and stream them to o: o << some_node and so on
 }
};

Then

Queue q = ....;
std::cout << q << std::endl; // calls your ostream& operator<<

Solution 4

I do not know how useful this is but since you attach each node to the next using nodeType<Type>.link then you may want to do something like this:

int numberPrinted = 1;
nodeType<Type> *temp;
if (queueFront != NULL) 
{
    temp = queueFront;
    do
    {
        cout << numberPrinted << ": " << temp->info << "\n";
        numberPrinted++;
    }while(temp->link!=NULL);
}

This way you can just follow the pointers without changing you queue.

View more solutions