I am attempting to edit this Queue class to only use myBack pointer, i began having errors and now I am lost....

LQueue.cpp is as follows

/*--- LQueue.cpp ----------------------------------------------------------
             This file implements LQueue member functions.
-------------------------------------------------------------------------*/
 
#include <new>
using namespace std;

#include "LQueue.h"

//--- Definition of Queue constructor
Queue::Queue()
: myBack(0)
{}

//--- Definition of Queue copy constructor
Queue::Queue(const Queue & original)
{
  
   if (!original.empty())
   {
      // Copy first node
	  Queue::NodePointer origPtr = original.myBack->next;
	  myBack = new Queue::Node(origPtr->data);
	  myBack = myBack -> next;
	  origPtr = origPtr -> next;
   		   

      // Set pointer to run through original's linked list
      
      while (origPtr != original.myBack->next)
      {

         Queue::NodePointer temp= new Queue::Node(origPtr->data);
		 temp->next = myBack->next;
		 myBack->next = temp;
		 myBack = temp;
         origPtr = origPtr->next;
      }
   }
}

//--- Definition of Queue destructor
Queue::~Queue()
{ 
  // Set pointer to run through the queue
  Queue::NodePointer ptr = myBack->next;

  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 (myBack == 0); 
}

//--- Definition of enqueue()
void Queue::enqueue(const QueueElement & value)
{
	Queue::NodePointer newptr = new Queue::Node(value);
	if (empty())
	{
		myBack = newptr;
		myBack->next = myBack;
	}
	else 
	{
		newptr->next = myBack->next;
		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"; **/
}

driver.cpp as follows

/*---------------------------------------------------------------------
                  Driver program to test the Queue class.
  ----------------------------------------------------------------------*/

#include <iostream>
using namespace std;
	
#include "LQueue.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();
}

LQueue.h as follows:

/*-- LQueue.h -------------------------------------------------------------

  This header file defines a Queue data type.
  Basic operations:
    constructor:  Constructs an empty queue
    empty:        Checks if a queue is empty
    enqueue:      Modifies a queue by adding a value at the back
    front:        Accesses the top queue value; leaves queue unchanged
    dequeue:      Modifies queue by removing the value at the front
    display:      Displays all the queue elements
    Note: Execution terminates if memory isn't available for a queue element.
---------------------------------------------------------------------------*/

#include <iostream>

#ifndef LQUEUE
#define LQUEUE

typedef int QueueElement;

class Queue
{
 public:
 /***** Function Members *****/
 /***** Constructors *****/

  Queue();
  /*-----------------------------------------------------------------------
    Construct a Queue object.

    Precondition:  None.
    Postcondition: An empty Queue object has been constructed.
        (myFront and myBack are initialized to null pointers).
  -----------------------------------------------------------------------*/

  Queue(const Queue & original);
  /*-----------------------------------------------------------------------
    Copy Constructor 

    Precondition:  original is the queue to be copied and is received 
        as a const reference parameter.
    Postcondition: A copy of original has been constructed.
  -----------------------------------------------------------------------*/

 /***** Destructor *****/
  ~Queue(); 
  /*-----------------------------------------------------------------------
    Class destructor 

    Precondition:  None.
    Postcondition: The linked list in the queue has been deallocated.
  -----------------------------------------------------------------------*/

 /***** Assignment *****/
 const Queue & operator= (const Queue & rightHandSide);
  /*-----------------------------------------------------------------------
    Assignment Operator 

    Precondition:  rightHandSide is the queue to be assigned and is 
        received as a const reference parameter.
    Postcondition: The current queue becomes a copy of rightHandSide 
        and a reference to it is returned.
  -----------------------------------------------------------------------*/

  bool empty() const;
  /*-----------------------------------------------------------------------
    Check if queue is empty.

    Precondition:  None.
    Postcondition: Returns true if queue is empty and false otherwise.
  -----------------------------------------------------------------------*/

  void enqueue(const QueueElement & value);
  /*-----------------------------------------------------------------------
    Add a value to a queue.

    Precondition:  value is to be added to this queue.
    Postcondition: value is added at back of queue.               
  -----------------------------------------------------------------------*/

  void display(ostream & out) const;
  /*-----------------------------------------------------------------------
    Display values stored in the queue.

    Precondition:  ostream out is open.
    Postcondition: Queue's contents, from front to back, have been 
        output to out.
  -----------------------------------------------------------------------*/

  QueueElement front() const;
  /*-----------------------------------------------------------------------
    Retrieve value at front of queue (if any).

    Precondition:  Queue is nonempty.
    Postcondition: Value at front of queue is returned, unless the queue 
        is empty; in that case, an error message is displayed and a 
        "garbage value" is returned.
  -----------------------------------------------------------------------*/

  void dequeue();
  /*-----------------------------------------------------------------------
    Remove value at front of queue (if any).

    Precondition:  Queue is nonempty.
    Postcondition: Value at front of queue has been removed, unless
        queue is empty; in that case, an error message is displayed 
        and execution allowed to proceed.
  -----------------------------------------------------------------------*/

 private:
   /*** Node class ***/
   class Node
   {
    public:
      QueueElement data;
      Node * next;
      //--- Node constructor
      Node(QueueElement value, Node * link = 0)
      /*-------------------------------------------------------------------
        Precondition:  value and link are received
        Postcondition: A Node has been constructed with value in its 
            data part and its next part set to link (default 0).
       ------------------------------------------------------------------*/
      { data = value; next = link; }

  };

  typedef Node * NodePointer;

  /***** Data Members *****/
  NodePointer myBack;       // pointer to back of queue

}; // end of class declaration

#endif

>>i began having errors and now I am lost..
Sometimes its better to just scrap what you have done and begin again. But the next time you change the code compile frequently so that errors don't accumulate.

It looks like you are using myBack as the queue's head pointer. Wouldn't it make more sense to name that pointer for what it does? Most programmers will name it "head" meaning that it is the beginning of the queue. The only other optional pointer that may be useful is "tail", which points to the last node of the queue. tail isn't really necessary, just convienent because the program can easily find it by iterating all through the queue searching for the last node.

Edited 6 Years Ago by Ancient Dragon: n/a

Yikes that is a lot of code. Can you try to simplify it down to < 40 lines or so? Also can you explain exactly what is wrong? Is it crashing? Is it giving an incorrect result?

Dave

it is crashing when i attempt to compile. how do i get myBack to point to the front of the queue?

>>i began having errors and now I am lost..
Sometimes its better to just scrap what you have done and begin again. But the next time you change the code compile frequently so that errors don't accumulate.

If you only have myBack pointer, which I assume means that it points to some previous node, now does the program know where the head of the queue is located?

no how do i make it point to the head?

Once myBack (or head) is set, never change it unless you want to add new node to the head of the queue.

And re-read my previous post because I changed it.

Edited 6 Years Ago by Ancient Dragon: n/a

i renamed it to head, how do i point it to the head? I am trying to modify the Queue class to use a circular linked-list

Look at enque() function, it already does it. If the queue is empty then it sets head to the new node.

Edited 6 Years Ago by Ancient Dragon: n/a

I attempted to display the queue and it had a assert failure...

Edited 6 Years Ago by smoothe19: n/a

First, I recommend you use a boost::shared_ptr for all "next" pointers and a boost::weak_ptr for all "prev" pointers, this will allow you to get rid of your destructor altogether.

Second, you should think whether you really need a copy-constructor for your queue. If you don't need it, make the class non-copyable (making the copy-constructor and assignment operator private with no implementation). This will get rid of the rather messy copy-constructor you have.

How do you hold a pointer to head? well you hold a pointer to head, that's all. You have to hold some starting pointer somewhere, either head or tail or both.

Edited 6 Years Ago by mike_2000_17: n/a

I didn't think this was a course exercise...

If it is an advanced exercise, they should allow, it is part of the new standard extension TR1.

Sir Saula, it's very easy man, the problem is in that code:

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

So, you see this is the default constructor, and it should initialize data members, and if you take a look into your header file, you will very very easy find the solution, the part for the default constructor in the header file is:

Queue();
  /*-----------------------------------------------------------------------
    Construct a Queue object.
 
    Precondition:  None.
    Postcondition: An empty Queue object has been constructed.
        (myFront and myBack are initialized to null pointers).
  -----------------------------------------------------------------------*/

got it, ... ok man I will write it, the previous code should be:

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

or you can simply write it in another way like this:

Queue::Queue()
{
myBack = 0;
myFront = 0;
}

This is it man, it's very easy.
Now, rule number one, consider it rule of thumb, when you declare variables, especially in stacks and queues, make sure you initialize them .... or .... believe it or not, your program will crash.. it's that easy.

Edited 6 Years Ago by Nick Evan: Added CODE-tags. Add them yourself by using the button that reads [CODE]

This article has been dead for over six months. Start a new discussion instead.