Convert Linked Queue to Circular Linked Queue

[netexhorn]

I am trying to learn C++ and I having some difficulty with this task. I need to take this code and convert it from a liked queue to a circular linked queue. Any help would be greatly appreciated.

CircularQueue.cpp

// CircularQueue.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <new>
#include <iostream>
using namespace std;
#include "Queue.h"




int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

 


Queue::Queue()
: myFront(0), myBack(0)
{}


Queue::Queue(const Queue & original)
{
   myFront = myBack = 0;
   if (!original.empty())
   {
      // Copy first node
      myFront = myBack = new Queue::Node(original.front());

      // Set pointer to run through original's linked list
      Queue::NodePointer origPtr = original.myFront->next;
      while (origPtr != 0)
      {
         myBack->next = new Queue::Node(origPtr->data);
         myBack = myBack->next;
         origPtr = origPtr->next;
      }
   }
}

//--- Definition of Queue destructor
Queue::~Queue()
{ 
  // Set pointer to run through the queue
  Queue::NodePointer prev = myFront,
                     ptr;
  while (prev != 0)
    {
      ptr = prev->next;
      delete prev;
      prev = ptr;
    }
}

//--- Definition of assignment operator
const Queue & Queue::operator=(const Queue & rightHandSide)
{
   if (this != &rightHandSide)         // check that not q = q
   {
      this->~Queue();                  // destroy current linked list
      if (rightHandSide.empty())       // empty queue
         myFront = myBack = 0;
      else
      {                                // copy rightHandSide's list
         // Copy first node
         myFront = myBack = new Queue::Node(rightHandSide.front());

         // Set pointer to run through rightHandSide's linked list
         Queue::NodePointer rhsPtr = rightHandSide.myFront->next;
         while (rhsPtr != 0)
         {
           myBack->next = new Queue::Node(rhsPtr->data);
           myBack = myBack->next;
           rhsPtr = rhsPtr->next;
         }
      }
   }
   return *this;
}

//--- Definition of empty()
bool Queue::empty() const
{ 
   return (myFront == 0); 
}

//--- Definition of enqueue()
void Queue::enqueue(const QueueElement & value)
{
   Queue::NodePointer newptr = new Queue::Node(value);
   if (empty())
      myFront = myBack = newptr;
   else
   {
      myBack->next = newptr;
      myBack = newptr;
   }
}

//--- Definition of display()
void Queue::display(ostream & out) const
{
   Queue::NodePointer ptr;
   for (ptr = myFront; ptr != 0; ptr = ptr->next)
     out << ptr->data << "  ";
   out << endl;

}

//--- Definition of front()
QueueElement Queue::front() const
{
   if (!empty())
      return (myFront->data);
   else
   {
      cerr << "*** Queue is empty "
              " -- returning garbage ***\n";
      QueueElement * temp = new(QueueElement);  
      QueueElement garbage = *temp;     // "Garbage" value
      delete temp;
      return garbage;
   }
}

//--- Definition of dequeue()
void Queue::dequeue()
{
   if (!empty())
   {
      Queue::NodePointer ptr = myFront;
      myFront = myFront->next;
      delete ptr;
      if (myFront == 0)     // queue is now empty
         myBack = 0;
   }   
   else
      cerr << "*** Queue is empty -- can't remove a value ***\n";
} 

Queue.h

#include <iostream>

#ifndef LQUEUE
#define LQUEUE

typedef int QueueElement;

class Queue

{
public:
	Queue();
    Queue(const Queue & original);
	~Queue(); 
	const Queue & operator= (const Queue & rightHandSide);
	bool empty() const;
	void enqueue(const QueueElement & value);
	void display(ostream & out) const;
	QueueElement front() const;
	void dequeue();



	 private:
   
   class Node
   {
    public:
      QueueElement data;
      Node * next;
      
      Node(QueueElement value, Node * link = 0)
    
      { data = value; next = link; }

  };

  typedef Node * NodePointer;

  NodePointer myFront,      // pointer to front of queue
              myBack;       // pointer to back of queue

}; // end of class declaration

#endif  

CircularQueueTest.cpp

#include "stdafx.h"
#include <iostream>
using namespace std;
	
#include "Queue.h"

void print(Queue q)
{ q.display(cout); }

int main()
{
   Queue q1;
   cout << "Queue created.  Empty? " << boolalpha << q1.empty() << endl;

   cout << "How many elements to add to the queue? ";
   int numItems;
   cin >> numItems;
   for (int i = 1; i <= numItems; i++) 
      q1.enqueue(100*i);

   cout << "Contents of queue q1 (via  print):\n";
   print(q1); cout << endl;

   Queue q2;
   q2 = q1;
   cout << "Contents of queue q2 after q2 = q1 (via  print):\n";
   print(q2); cout << endl;

   cout << "Queue q2 empty? " << q2.empty() << endl;

   cout << "Front value in q2: " << q2.front() << endl;

   while (!q2.empty())
   {
     cout << "Remove front -- Queue contents: ";
     q2.dequeue();
     q2.display(cout);
   }
   cout << "Queue q2 empty? " << q2.empty() << endl;
   cout << "Front value in q2?" << endl << q2.front() << endl;
   cout << "Trying to remove front of q2: " << endl;
   q2.dequeue();
} 

Thanks again.

[D80DSL3A]

I haven't done a circular link list but I think that the assignment
myBack->next = myFront; should do the trick. I think it needs to appear in 2 places in your enqueue().

It looks like this could also be done by passing myFront as the 2nd argument to the Node constructor (but only if the list isn't empty).

[kfmfe04]

@netexhorn

please make an effort to think it through

- conceptually, how may a linear linked list differ from a circular linked list
- in particular, think about how heads and tails may be dealt with, in both cases
- then look through each line of your code, keeping in mind the notes you collected from above

if you run into problems, post specific questions