Not fully understanding Queue???

[Jimmy Rose]

Hello,
I have a problem with my understanding with a queue, the problem does not lie in my understanding what a queue is and how to create one but I've tried to create one without using arrays and the problem I have with it is keeping track of the data. I understand how to find the front, the front->next, the rear, and the rear->next but keeping track of the values in between is what I'm finding hard to grasp on.
I've researched a simple queue program that works but I don't understand how it's able to retain its values more appropriately how one section seems to address values magically.

void Queue::add( int num )
{
	Node *temp = new Node;
	temp->data = num;
	temp->next = NULL;
	if( front == NULL )
		front = temp;
	else
		back->next = temp;
	back = temp;
}

int main()
{
Queue que;

	que.add(5);
	que.add(7);
	que.add(10);
	que.add(4);
	que.display();

return 0;
}

When add is called the first time front and back receive the value 5 from temp which I could follow but when add is called a second time back->next = temp assigns front->next the temp value of 7 which is the only way I could explain it before the code reaches back->next = temp front->next is equal to NULL right after the code passes back->next = temp front->next changes but on the third and fourth call front->next stays the same. How is this happening?

Any help is appreciated.
Thanks!

[Disch]

The idea is each node points to the next node in the queue.

It might make more sense it you walk through it...

que.add(5);

// queue is empty
//  front = NULL
//  back = NULL

	Node *temp = new Node;  // temp = 5->NULL
	temp->data = num;       //  that is... temp->data is 5 and
	temp->next = NULL;      //  temp->next is NULL

	if( front == NULL )     // since we don't already have a front
		front = temp;   //  make 'temp' the new front

	back = temp;            // temp is also the new back

//  now:
//  front = 5->NULL
//  back  = 5->NULL 

que.add(7);

//  front = 5->NULL
//  back  = 5->NULL

	Node *temp = new Node;   // temp = 7->NULL

	else                       // back = 5->NULL   previously
		back->next = temp; // back = 5->7      now it points to temp (7)

	back = temp;             // back = 7->NULL

//  now:
//  front = 5->7
//  back  = 7->NULL 

que.add(10);

//  front = 5->7
//  back  = 7->NULL

	Node *temp = new Node;   // temp = 10->NULL

	back->next = temp;       // back = 7->10

	back = temp;             // back = 10->NULL

//  now:
//  front =  5->7
//           7->10
//  back  = 10->NULL 

que.add(4);

	Node *temp = new Node;   // temp =  4->NULL

	back->next = temp;       // back = 10->4

	back = temp;             // back =  4->NULL

//  now:
//  front =  5->7
//           7->10
//          10->4
//  back  =  4->NULL 

Does that help clarify it?

[Jimmy Rose]

Thanks for the response and great explanation.
What's getting me right now is when seven is added what exactly assigns front->next to seven.
I see that back->next = 7 but how exactly does front->next inherit those values.

[mcrist]

Your initial value of front is equivalent to NULL because it is not assigned a value. You evaluate for NULL against the variable front in the add() method. When that evaluates true, front is assigned to the initial value added to the queue. After that initial value (int this case you add 5 to the queue to 5 is assigned to front), when you evaluate front to be equivalent to NULL, it evaluates to false, thus not assigning the front value over again and continuing with the rest of the code.

[Disch]

What's getting me right now is when seven is added what exactly assigns front->next to seven.
I see that back->next = 7 but how exactly does front->next inherit those values.

in that case, front and back both point to the same node. Remember that when you change back->next, you are not actually changing back. You're changing what back points to. There's a big difference.

Since front and back both point to the same node at that time, when you change that node, the changes will be visible via both pointers.

Consider the below trivial example:

int var = 5;  // an actual variable
int* ptr1 = &var;  // a pointer that points to var
int* ptr2 = &var;  // another pointer .. also points to var

// these all print '5' as you'd expect
cout << var << endl;
cout << *ptr1 << endl;
cout << *ptr2 << endl;

var = 6;  // change var to 6

// now print them all again:
cout << var << endl;    // prints 6
cout << *ptr1 << endl;  // also prints 6 (even though we never changed ptr1)
cout << *ptr2 << endl;  // also prints 6 ( "" ) 

because ptr1 and ptr2 "point to" var, printing *ptr1 prints the contents of var.


With your nodes it's the same idea...

que.add(7);

//  front points to the '5' node
//  back points to the '5' node

Node *temp = new Node;   // temp points to the '7' node

// here, 'back' points to the 5 node, so by changing back->next
//  we're changing the 5 node's next pointer
//  note that since front also points to the 5 node, these changes
//  would be visible via front, as well
//
//  again note that this line *DOES NOT ACTUALLY CHANGE BACK*
//  it makes changes in the node that back *points to* (the 5 node)
else
	back->next = temp; // the 5 node's next ptr now points to the 7 node

// this, however, does actually change back.  It makes it point to a
//  different node.  So after this, back will no longer point to the 5 node
//  and instead it points to the 7 node:
back = temp;

// the end result:
//  the 5 node's next pointer points to the 7 node
//  the 7 node's next pointer is NULL
//  'front' points to the 5 node
//  'back' points to the 7 node 

EDIT:

I was bored so I made this diagram of what is going on. Hopefully it will clarify things:

http://i56.tinypic.com/21sbom.png

[Jimmy Rose]

Thanks for the help,
I know it's been a while but I need to add more to this.

I see now how front->next becomes back->next but what I don't get is how front->next->next become back->next and if back->next and front->next point to the samething then why when back->next changes the second time front->next doesn't change but front->next->next does.

Another question I have is:
If front is a pointer to a Node and front->next is a pointer to a Node then why when you change back->next it changes front->next but when you change back it doesn't change front even though they point to the same address.

Here is how I'm seeing it:

void Queue::add( int num ) // 5
{
	Node *temp = new Node; // address 0x01
	temp->data = num; // data = 5
	temp->next = NULL; // next->NULL
	if( front == NULL )
		front = temp; // front->0x01, front->data = 5, front->next->NULL
	else
		back->next = temp;
	back = temp; // back->0x01, back->data = 5, back->next->NULL
}

void Queue::add( int num ) // 7
{
	Node *temp = new Node; // address 0x02
	temp->data = num; // data = 7
	temp->next = NULL; // next->NULL
	if( front == NULL )
		front = temp; // front->0x01, front->data = 5
		// front->next->0x02, front->next->data = 7, front->next->next->NULL
	else
		back->next = temp; // back->next->0x02, back->next->data = 7, back->next->next->NULL
		// now wouldn't this code change front the same way back->next changed front->next
		back = temp; // back->data = 7, back->next->NULL, address0x02
}

[Disch]

I'll have to revisit this when I get home so I can add some diagrams to hopefully make it more clear. It's hard to explain in just words.

'back' and 'front' are two separate pointers. Each pointer holds the address of a Node.

Each node has a 'next' pointer that also holds an address.

Now, when you change back (back = whatever;) this does not change front because we are only changing the address stored in our pointer, back. Likewise if we change front, back will not change.

Changing front or back also will not change any nodes.

Now... when you say back->next = whatever;.. this is what's tricky:
- you're not changing front
- you're not changing back
- you're changing a node

Which node depends on whatever back points to. If back and front point to the same node, then changing back->next will also change front->next because they're both one and the same.

Like I said I'll try to get into it more when I get home.

[Jimmy Rose]

Thanks again for replying your input is great.

Right when I was writing this explaining on what I wasn't getting I was able to figure it out.
It made sense to me that instead of back = temp; that back should just equal back->next, it made perfect sense to me back->next would point where front->next is pointing to and assigning back to back->next would make back point to where front->next is and back->next would point to front->next->next is. But since back->next and temp is pointing to the same address it exactly the same thing.

Here's a diagram on how I'm visualizing it, am I visualizing it correctly?

http://5686297744816113738-a-1802744773732722657-s-sites.googlegroups.com/site/queuediagram/home/Queue%20Diagram.png?attachauth=ANoY7cqOnKGEv1XoE78Nhs-S0ZE3WFaBfLYp-IK84MKy_sWMW2P6roBDjbHlMmOpHSFh2GKJLz-bkgnMa9BZyF7qtUHz0WI6clLs4wujqQIzq_lpHTP19T3BeoFnz7n3HesV23xcbL2tzShp2loL10FJe4Z02WrjuDV1YmnDFeZTA-kAmrMp2_6hFnn7EHM96mZ04HEWXTdki7BOrvk9n4zMYiM9bYm1dQ%3D%3D&attredirects=0

[Disch]

Yes it looks like you have it. Although it's a little confusing that you drew the '5' node 3 times in the first part (there's only 1 node, and all 3 pointers are pointing to it. The way you have it drawn suggests there are 3 separate nodes, which isn't correct).