Hi all,

So I'm working on this program to use a circular doubly linked list to implement a queue class. It went fairly well, but I'm stuck on the copy constructor, which causes runtime errors whenever I try to test it. Nonetheless, I really don't see what I am doing wrong.

Here's the header/implementation file for the class (all one file because I'm using g++):

//#include "CharQueueTemplate.h"
#include <cassert>
#include <new>
#include <cstddef>

using namespace std;

template <typename T>
class CharQueue
{
   public:
       virtual bool isEmpty() const = 0;
       virtual void enqueue(const T & newItem) = 0;
       virtual void dequeue(void) = 0;  // dequeue an item and return its value
       virtual T getFront(void) const = 0;  // return the value of the first item in the queue (but do not dequeue it)
};

template <typename T> class Queue : public CharQueue<T>
{
    private:
    struct qNode {
    T element;
    qNode *next;
    qNode *prev;
    };//end qNode
    qNode *front;
    qNode *back;
    qNode *head;

    public:

    Queue();//default constructor
    Queue(const Queue<T>& q);//copy constructor
    virtual ~Queue();//destructor

    virtual bool isEmpty() const;//checks to see if the queue is empty

    virtual void enqueue(const T & value);//places value at the back of the queue (prior to the head pointer in this case)

    virtual void dequeue();//removes the front value from the queue

    //virtual void dequeue(T& head);

    virtual T getFront() const;

    bool operator==(const Queue & source);

};//end Queue


template <typename T> Queue<T>::Queue()
{
    head = NULL;

}//end default constructor



//evil copy constructor
template <typename T> Queue<T>::Queue(const Queue & aq)
{
    /*if(!aq.isEmpty())
    {
        qNode *original = aq.head;
        qNode *newhead = new qNode;//points to the head of the list
        newhead->element = original->element;
        qNode *oldh = original;
        qNode *newh = newhead;
        while(original != oldh->prev) {
            //newhead->next = original->next;
            newhead=newhead->next;
            original=original->next;
            newhead->element = original->element;
        }//end while
        cout << "list copied" << endl;
        head = newh;
        //front = newhead;

        //qNode *nCurrent = newhead;
        //qNode *temp = new qNode;

        /*while(original != aq.back)
        {
            original = original->next;
            nCurrent->next= new qNode;
            nCurrent = nCurrent->next;
            nCurrent->element = original->element;
            nCurrent->next = NULL;
            back=nCurrent;//possible error
        }//end while

    }//end if
*/
    T value;
    qNode * orig = aq.head;
    do{
        value = orig->element;
        qNode *temp = new qNode;
        temp->element = value;
        //temp->next = head;
        //temp->prev = head->prev;
        //head->prev->next = temp;



        //back = temp;
        if(isEmpty()) {
            //front = temp;
            head= temp;
            head->next=head;
            head->prev =head;
        }//end if

        else{
            //back->next = temp;
            head->prev->next=temp;
            temp->prev=head->prev;
            head->prev=temp;
            head->prev->next=head;
        }
        cout << "smurf" << endl;
        orig = orig->next;
    }
    while(orig->next!=aq.head);


}//end copy constructor

template <typename T> Queue<T>::~Queue()
{
    while(!isEmpty())
    {
        dequeue();
    }
 }//end destructor

template <typename T> bool Queue<T>::isEmpty() const
{
    return (head == NULL);
}//end isEmpty

template <typename T> void Queue<T>::enqueue(const T& value)
{
    try
    {
        //make new node
        qNode *temp = new qNode;
        temp->element = value;
        //temp->next = head;
        //temp->prev = head->prev;
        //head->prev->next = temp;



        //back = temp;
        if(isEmpty()) {
            //front = temp;
            head= temp;
            head->next=head;
            head->prev =head;
        }//end if

        else{
            //back->next = temp;
            head->prev->next=temp;
            temp->prev=head->prev;
            head->prev=temp;
            head->prev->next=head;
        }
        //back = temp;
    }//end try
    catch (bad_alloc e)
    {
        throw string("Memory cannot be allocated.");
    }//end catch

}//end enqueue

template <typename T> void Queue<T>::dequeue()
{
    if(!isEmpty())
    {
        qNode *temp = head;
        if(head->next == head)
        {
            head=NULL;
        }
        else
        {
            head->prev->next = head->next;
            head->next->prev = head->prev;
            head=head->next;
            delete temp;
        }//end else
    }//end if
}//end dequeue

template <typename T> T Queue<T>::getFront() const
{
    if(!isEmpty())
    {
        return head->element;
    }//end if
}//end getFront

template <typename T> bool Queue<T>::operator == (const Queue & source)
{
    if(head==NULL && source.head!=NULL)
    {
        return false;
    }//end if
    qNode * newone = head;
    qNode * oldone = source.head;
    while(newone->next != head && oldone->next != source.head)
    {
        if(newone->element != oldone->element)
        {
            return false;
        }//end if
    }//end while
    return true;
}//end operator overload

//end q.h

If anyone could point out what I'm doing wrong, it would be greatly appreciated. This has me climbing the walls.

There are a couple issues... First, you still need to create a new nodes inside your while loop for your new copied list. The only thing you copy from the original is 'element'. You are not allowed to use the original's node pointer for your new list. Second thing is that your while loop should be (while original != oldh). In this case, your last node will be copied. Third, you need to keep track of your last new created node for your new list inside the loop. Once you finish from the loop, you then can link it back to the new list head node.

Edited 6 Years Ago by Taywin: n/a

Take a look at this... it may inspire you

#include <iostream>
#include <cassert>
#include <string>
//------------------------------llist.h
template <typename type=std::string> class llist {
   struct node {
      type data;
      node* next;
      node* prev;

      node ();
      node (type);
      node (node*,node*,type);
      type Data();
      node& operator= (const node&);
      bool operator== (const node&);
      friend std::ostream& operator<< (std::ostream& o,const node& t)  {
         return o << t.data;
       }
    };
   typedef struct node* pnode;
public:
   struct iterator  {
      pnode parser;
      iterator ();
      iterator (pnode);
      iterator& operator= (const iterator&);
      bool operator!= (const iterator&);
      bool operator== (const iterator&);
      node operator* ();
      pnode operator++ ();
      pnode operator-- ();
      pnode operator-> ();
      friend std::ostream& operator<< (std::ostream& o,const iterator& t)  {
         return o << *t.parser;
       }
    };
private:
   node _empty,_head,_tail;
   pnode head;
   pnode tail;
   pnode last;
   unsigned long size;
  public:
   llist ();
   llist (unsigned long,type);
   llist (const llist&); // copy constructor
   void insert (const type&);
   void remove (const type&);
   void clear ();
   unsigned long lsize ();
   iterator begin () const;
   iterator end () const;
   iterator front () const;
   iterator back () const;   
   bool empty () const;
   node operator [] (unsigned long);
 };
//-----------------------------llist.cpp
template <typename type> llist<type> :: node :: node () {}
template <typename type> llist<type> :: node :: node (node* _last,node* _tail,type _data)
     : prev (_last), next (_tail), data(_data) {}
template <typename type> llist<type> :: node :: node (type _data) : data(_data) {}
template <typename type> llist<type> :: node& llist<type> :: node :: operator= (const node& cp)  {
   this->next=cp->next;
   this->prev=cp->prev;
   this->data=cp->data;
   return *this;
 }
template <typename type> type llist<type> :: node :: Data () {
   return data;
 }
template <typename type> bool llist<type> :: node :: operator== (const node& n)  {
   return this->data==n.data;
 }
 //----------------------------
template <typename type> llist<type> :: iterator :: iterator()  {}
template <typename type> llist<type> :: iterator :: iterator(pnode nd) : parser(nd) {}
template <typename type> llist<type> :: pnode llist<type> :: iterator :: operator ++ () {
   return parser=parser->next;
 }
template <typename type> llist<type> :: pnode llist<type> :: iterator :: operator -- () {
   return parser=parser->prev;
 }
template <typename type> llist<type> :: iterator& llist<type> :: iterator :: operator= (const iterator& it)  {
   this->parser=it.parser;
   return *this;
 }
template <typename type> llist<type> :: pnode llist<type> :: iterator :: operator-> ()  {
   return this->parser;
 }
template <typename type> bool llist<type> :: iterator :: operator!= (const iterator& a)  {
   return this->parser!=a.parser;
 }
template <typename type> bool llist<type> :: iterator :: operator== (const iterator& a)  {
   return this->parser==a.parser;
 }
template <typename type> llist<type> :: node llist<type> :: iterator :: operator* ()  {
   return *parser;
 }
//------------------------------
template <typename type> llist<type> :: llist ()
   : head(&_head),tail(&_tail),last(&_empty), size(0)  {          

   head->next=tail;          head->prev=tail;
   tail->next=head;          tail->prev=last;
   last=head;
 }
template <typename type> llist<type> :: llist (unsigned long qty,type obj)
   : head(&_head),tail(&_tail),last(&_empty), size(0)  {          

   head->next=tail;          head->prev=tail;
   tail->next=head;          tail->prev=head;
   last=head;
   for (;qty>0;qty--)  {
      insert(obj);      
    }
 }
template <typename type> llist<type> :: llist (const llist<type>& lst)  //copy constructor
   : head(&_head),tail(&_tail),last(&_empty), size(0)  {          

   head->next=tail;          head->prev=tail;
   tail->next=head;          tail->prev=head;
   last=head;
   for (llist<type>::iterator i=lst.begin();i!=lst.end();++i)  {
      this->insert(i->Data());
    }
 }
template <typename type> void llist<type> :: insert (const type& thing)  {      
   pnode p=new node (last,tail,thing);
   assert (p);
   last->next=p;
   if (!size) head->next=p;
   last=p;
   tail->prev=p;
   size++;
 }
template <typename type> unsigned long llist<type> :: lsize() {
   return size;
 }
template <typename type> llist<type> :: iterator llist<type> :: begin() const {
   return iterator(llist::head->next);
 }
template <typename type> llist<type> :: iterator llist<type> :: end() const {
   return iterator(llist::tail);
 }
template <typename type> llist<type> :: iterator llist<type> :: front () const  {
   return !empty() ? head->next : NULL;
 }
template <typename type> llist<type> :: iterator llist<type> :: back () const  {
   return !empty() ? tail->prev : NULL;
 }
template <typename type> bool llist<type> :: empty () const  {
   return head->next==tail;
 }
template <typename type> void llist<type> :: clear ()  {
   for (llist<type>::iterator it=this->begin();it!=this->end();++it)  {
      delete &it;
      size--;
    }
   this->head->next=this->tail;
   this->tail->prev=this->head;
 }
template <typename type> void llist<type> :: remove (const type& t)  {
  for (llist<type>::iterator it=this->begin();it!=this->end();++it) {
     if (*it==t)  {
        last=it->prev;
        it->next->prev=it->prev; 
        it->prev->next=it->next;        
        delete &it;
        size--;
      }
    }
 }
template <typename type> llist<type>::node llist<type> :: operator [] (unsigned long pos) {
  node* start;
  if (pos <= size)  {
    switch (pos<size/2)  {  
       case true:
          for (;pos >0;pos--)  {
            start=head;
            start=start->next;
        }
       break;
       case false:
          for (;pos >0;pos--)  {
            start=tail;
            start=start->prev;
         }
      }
   }
  return *start;
 }
//-----------------------
int main ()  {
   llist<> z(5,"zeroth");
   llist<> d(z);
   d.insert ("first");
   d.insert ("second");
   d.insert ("third");
   d.remove ("third");
   d.insert ("fourth");
   d.insert ("fifth");
   
   
   for (llist<>::iterator it=d.begin();it!=d.end();++it) std::cout << *it << "\n";
   //std::cout << d.lsize();
   std::cout << d[3];
   d.clear();
 }
This article has been dead for over six months. Start a new discussion instead.