linked list queue?

[flclempire]

Hi. I've been studying c++ for a couple months now, and I've ran into a snag in the book I am using for study, "C++ Primer 5th edition". Its the concept of a linked list used to form a queue. The explanations in the book for this section are jibberish so I've come here for help.

The following is the code copied from the book with my thought process in the notes.

class Queue
{
private:
struct Node {Item item; struct Node * next;};
enum{Q-SIZE = 10};
Node* front;
Node* rear;
int Items;
public:
Queue(int qs = Q-SIZE);
~Queue();
bool isempty() const;
bool isfull() const;
int queuecount() const;
bool enqueue(const Item &item);
bool dequeue(Item &item);
};

////////This method, "enqueue" is where I get confused. This is how I understand it working the first time it is used on an empty queue object/////

bool Queue::enqueue (const Item& item)
{
if (isfull())    ///////if queue is full (10) then stop operation
	return false;
Node * add = new Node;  ////////new Node* structure is created, uninitialized

if (add == NULL)   ////if the new allocation failed, stop operation
	return false;
add->item = item;    ///the passed reference is copied to add's item data member

add->next = NULL;    ///add's next pointer is initialized to NULL

items++;   ///the items counter is increased to keep track of the queue size

if (front == NULL) //front would initially be set to NULL upon object creation

	front = add;  //the first use of "enqueue" on an empty queue object
                      //will always copy add to front
else
	rear->next = add;
rear = add;  ///add is currently copied to both front and rear...
             ///wtf, the next pointer is always NULL?  why have it?
return true;
}

Now, the second use of enqueue is where I get lost~

bool Queue::enqueue (const Item& item)
{
if (isfull())   ///same as the first run
	return false;
Node * add = new Node;   ///new Node* created, uninitialized

if (add == NULL)   ///stop if new allocation failed
	return false;
add->item = item;  //copy passed reference to add's item member

add->next = NULL;  //add's next* is set to NULL

items++; //item count is increased

if (front == NULL) //first run applied an address to front, its no longer NULL

	front = add; 
else
	rear->next = add; //rear previously set to the first run's "add"
                         //parameters, the pointer is now set to the 2nd
                         //run's add's next address

rear = add;   //rear gets completely overwritten to copy the 2nd run's add...
              //wtf is the point of this?
return true;
}

Aaaaannnd yeah, I can't seem to wrap my head around why this would result in a functioning linked list. Hell, it doesn't even seem that this class could hold more than 2-3 nodes, nothing here makes sense to me.

ANY help would be appreciated. I've checked some other linked list examples via google and they are all pretty terrible-they expect that you are already a pointer master.
Thanks.

[ne555]

Simplifying your code (assuming that everything is ok)

bool Queue::enqueue (const Item& item)
{
Node * add = new Node( item ); //allocate the new item, the next pointer is null

if (front == NULL) //front is from where you pop the items. If you only got one, you must point it
	front = add;
else //your queue already has nodes. You are making the link
	rear->next = add; 

rear = add; //the last one is the one that you just inserted.
return true;
}

Another version

bool Queue::enqueue (const Item& item){
  if( empty() )
    front = rear = new Node( item ); //next is set to NULL
  else{
    rear->next = new Node( item ); //creating the link
    rear = rear->next; //updating the last element
  }
}

The next field of the rear element is always set to NULL (actually, it is not used). However when you push an item, rear->next will link it to your list

[flclempire]

Thanks for the reply. I'm starting to get it. For linked lists, recursive function, and other similar ideas I find it helps to visually draw the sequence out to get a visual idea in my head.