Reputation: 764
Traversing queue in C++
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
Upvotes: 2
Views: 16880
Answers (5)
Reputation: 1
here is an easy way to do it with just a pointer and a while loop
while(pointer != NULL) pointer.info pointer = pointer.next
Upvotes: 0
Reputation: 31
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.
Upvotes: 1
Reputation: 96233
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.
}
Upvotes: 3
Reputation: 227370
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<<
Upvotes: 1
Reputation: 182753
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
Upvotes: 2