Issues and questions about queues

**Nazgulled** · 12-11-2007

Hi there,
Recently, on some class I'm having at university, the teacher talked about "queues" using the well known linked-list format but with another structure added to the problem. I bet you are already familiar with this stuff so you probably know more than me (that's why I'm posting this here in the first place). Anyway, the structures are these:

Code:

typedef struct sNode {
	int elem;
	struct sNode *next;
} Node;

typedef struct {
	Node *first;
	Node *last;
} Queue;

Then, I have the "enqueue" function which was coded like this:

Code:

void enQueue(Queue *q, int elem) {
	if(!q) return;
	
	Node *x = (Node*)malloc(sizeof(Node));
	
	if(!x) return;
	
	x->elem = elem;
	x->next = NULL;
	
	if(q->last) q->last->next = x; // This line is important to my post!
	else q->first = x; // This line is important to my post!
	
	q->last = x; // This line is important to my post!
}

Please note the lines with a comment. Then, on main, I randomize 5 numbers and call the function enQueue with a pre-initialized (with NULL values on 'first' and 'last') queue and the number generated. I also have a function that lists the values on the queue, separated by the linked lists 'first' and 'last'.

After adding 5 numbers to the queue and calling the function that prints the list, the output is this:

Code:

FIRST: 52 -> 38 -> 93 -> 65 -> 27
LAST: 27

Remember the commented lines in the second snippet of code posted? Well, those are the lines that I don't get how they work. I don't understand why the linked-list 'first' has all the numbers generated and why 'last' as only one number which is the last one.

In case it's important, here's the code that prints the "queue":

Code:

void listQueue(Queue q) {
	printf("\n\nFIRST: ");

	do {
		printf("&#37;d", q.first->elem);
		q.first = q.first->next;
		
		if(q.first) printf(" -> ");
	} while(q.first);
	
	printf("\nLAST: ");

	do {
		printf("%d", q.last->elem);
		q.last = q.last->next;
		
		if(q.last) printf(" -> ");
	} while(q.last);
}

Can somebody explain me as easy as possible how those [commented] lines work and what are they doing exactly?

I also have another question but I'll leave that after I understand this bit of code otherwise I'll be much more confused. Home my post is detailed and not confusing...

**tabstop** · 12-11-2007

I don't see any commented lines in your first snippet, so we'll move right along to the second.

Code:

if (q->last)
  q->last->next = x;
else
  q->first = x;

(I've rearranged so it looks all nice) The if statement checks to see if there is a last element in the queue. If so, we put x at the end of the line (set a link from the previously last element to this one). If not, then the queue is empty, so we put x at the front of the line (which is also the end of the line, since x is the only person in line). The q->last = x moves the end of the line to point at x.

I don't know what your print function does, so I don't know why it prints. But the point of the queue, is that you should be able to get from the front of the queue to the back just by following the links, but you can't get from the back to the front at all. (No jumping in line! in other words)

**Nazgulled** · 12-11-2007

Sorry, it was in fact the second snippet, my bad. That's exactly what I wanted to know but I'm still confused...

My print function is the following (sorry for missing it):

Code:

void listQueue(Queue q) {
	printf("\n\nFIRST: ");

	do {
		printf("%d", q.first->elem);
		q.first = q.first->next;
		
		if(q.first) printf(" -> ");
	} while(q.first);
	
	printf("\nLAST: ");

	do {
		printf("%d", q.last->elem);
		q.last = q.last->next;
		
		if(q.last) printf(" -> ");
	} while(q.last);
}

Most of the things you said about the commented lines, I get, most of them. Now that you have the print function here, what I don't understand is how the 'first' linked-list as all the numbers inserted in the order they were generated. To my understanding of the code, the 'last' linked-list is the one that should have all the numbers and not just the last one. I don't understand how the 'q->first' has pointers to the next number when I say that 'q->last->next = x;'. If I'm creating a new node element which is 'x' and then I say that the 'next' element in the 'last' linked-list is equal 'x', why is it that 'q->first' has all the pointers to the next number?

That's what I don't understand...

**tabstop** · 12-11-2007

Originally Posted by Nazgulled

Most of the things you said about the commented lines, I get, most of them. Now that you have the print function here, what I don't understand is how the 'first' linked-list as all the numbers inserted in the order they were generated. To my understanding of the code, the 'last' linked-list is the one that should have all the numbers and not just the last one. I don't understand how the 'q->first' has pointers to the next number when I say that 'q->last->next = x;'. If I'm creating a new node element which is 'x' and then I say that the 'next' element in the 'last' linked-list is equal 'x', why is it that 'q->first' has all the pointers to the next number?

That's what I don't understand...

Last is not a linked list. First is not a linked list. q is the linked list. Last is the last element of q. First is the first element of q.

ASCII picture time!

Code:

q:
+-----+  +-----+  +-----+  +-----+  +-----+
|     |->|     |->|     |->|     |->|     |->NULL
+-----+  +-----+  +-----+  +-----+  +-----+
   ^                                   ^
   |                                   |
q.first                             q.last

The boxes are nodes, and all the nodes belong to the linked list called q. Use the picture and trace through the code for inserting and printing.

**Nazgulled** · 12-12-2007

I'm still confused how 'q->first' has all the elements added to the queue. We only set one element one time in the code to 'q->first', and that is when q->last is null. After that, we will never add any new elements to 'q->first' how the hell looping through q->first prints all the elements?

I'm going to my second question even though I'm still confused, maybe it will me understand the whole thing. Well, what's the point of having a structure with a 'first' and 'last' pointer? I suppose it's to make easier looping through all the elements? Or maybe not?
Last year, I learned linked lists using only the first structure you see on the first post, this year, I'm learning to use them with the second structure with a 'first' and 'last' pointer and I didn't get the idea. Why do we do it like this? What's the purpose? And using this 2 structures, how would you loop through the linked-list? What advantages do we get by using a structure with a 'first' and 'last' pointers?

**tabstop** · 12-12-2007

Originally Posted by Nazgulled

I'm still confused how 'q->first' has all the elements added to the queue. We only set one element one time in the code to 'q->first', and that is when q->last is null. After that, we will never add any new elements to 'q->first' how the hell looping through q->first prints all the elements?

Look at the pretty picture again. The links are in the nodes themselves. Neither q.first or q. last "know" anything about anybody else in the list. q.first points at the first node. The first node points at the second node. The second node points at the third node. The third node points at the fourth node. And so on, until you get to the last node, which doesn't point at anything.

And just to make the point, I'll pick nits about terminology: you're not looping through q.first. q.first is just a pointer. But each node has a pointer in it, so you can follow the nodes, starting at q.first. q.first is not a linked list. q.last is not a linked list. q is the linked list; you're looping through q. q.first (or q.last) just give you a place to start.

Originally Posted by nazgulled

I'm going to my second question even though I'm still confused, maybe it will me understand the whole thing. Well, what's the point of having a structure with a 'first' and 'last' pointer? I suppose it's to make easier looping through all the elements? Or maybe not?
Last year, I learned linked lists using only the first structure you see on the first post, this year, I'm learning to use them with the second structure with a 'first' and 'last' pointer and I didn't get the idea. Why do we do it like this? What's the purpose? And using this 2 structures, how would you loop through the linked-list? What advantages do we get by using a structure with a 'first' and 'last' pointers?

Remember what happens at a queue: people enter at the back of the line, but are removed from the front. You don't need a q.last, if you really don't want it; however, if your only access is to the front, to insert a member you have to walk the whole list to find the end of it. So, we keep an extra pointer around that points to the end of the line so we don't have to find it every time we need it. And again, you don't have two structures. You have one structure, one list, one queue, one ring to bring them ... oh never mind. You've seen how to get through the queue: start at the front, and chase links.

**Nazgulled** · 12-12-2007

Sorry, but I still don't get it... And I already know how to "get through the queue: start at the front, and chase links". I've already done that last year using only this:

Code:

typedef struct sNode {
	int elem;
	struct sNode *next;
} Node;

But this year, the teacher thrown into the mix this:

Code:

typedef struct {
	Node *first;
	Node *last;
} Queue;

And I know we are talking about pointers, I just used "looping" because it's easier for me to talk like that as English is not my main language so I'll keep using "loop" because that's how I know how to explain my self.

We are "looping" through q->first, like, you print q->first->element and then we set q->first = q->first->next and then print the next element and we do this until q->first is null. I don't understand why this doesn't happen in q->last instead of q->first.

I know these are all pointers that point to something, to the next element. But as my understanding of the code involved, "looping" through q->last until it's null, is the one that should be listing all the elements and not just the last one.

Code:

if (q->last)
  q->last->next = x;
else
  q->first = x;

We are always saying that q->last->next will be equal x and for me this is what should happen with that code:

Insert element 5:

Code:

q->first->element = 5;
q->first->next = NULL;

q->last->element = 5;
q->last->next = NULL;

Insert element 7:

Code:

q->first->element = 5;
q->first->next = NULL;

q->last->element = 5;
q->last->next = NULL;

q->last->next->element = 7;
q->last->next->next = NULL;

Insert element 2:

Code:

q->first->element = 5;
q->first->next = NULL;

q->last->element = 5;
q->last->next = NULL;

q->last->next->element = 7;
q->last->next->next = NULL;

q->last->next->next->element = 2;
q->last->next->next->next = NULL;

But this is not what's happening, or maybe I'm missing something, but with the code above, this is what I understand it's happening. But the print function shows me a different thing... I don't know how better I can explain what I don't understand.

**matsp** · 12-12-2007

Because you also have:

Code:

	q->last = x; // This line is important to my post!

So every time you insert somrthing, q->last is changed to point to the most recently inserted element [which, the first time is the same as q->first, but later on points to something else].

So after your "insert 2", it would look like this:

Code:

q->last->element = 2;
q->last->next = NULL;

Can I also point out that your print function modifies last, which is probably not such a great idea - use a temporary pointer instead. [Although you get away with it because you are passing Queue as a copy of the original, so you don't actually modify the original code].

--
Mats

**tabstop** · 12-12-2007

Originally Posted by Nazgulled

Sorry, but I still don't get it... And I already know how to "get through the queue: start at the front, and chase links". I've already done that last year using only this:

Code:

typedef struct sNode {
	int elem;
	struct sNode *next;
} Node;

But this year, the teacher thrown into the mix this:

Code:

typedef struct {
	Node *first;
	Node *last;
} Queue;

Well. Everything that was there, is still there, isn't it? So walking through the list isn't going to change, since each node points to the next, and first still points to the head of the line.

Alright (I'm tired of drawing ASCII boxes, so hopefully this is clear):

Start: q.first = NULL; q.last = NULL
Insert 5: q.first = [5] = q.last ([5] points to NULL)
Insert 7: q.first = [5] -> [7] = q.last ([7] points to NULL)
Insert 2: q.first = [5] -> [7] -> [2] = q.last ([2] points to NULL)

Look at how things are inserted (ignoring the empty-queue special case): we find the element q.last points to, set it to point to the new last element, set the new element to point to NULL, and change q.last to point to the new last element. So always always always always always q.last->next == NULL, because we set q.last to be the new element which points to NULL (except when q.last is NULL itself when the queue is empty). But q.first points to the head of the line, so q.first->next is the second element, q.first->next->next is the third element, etc.

**Nazgulled** · 12-12-2007

I must be really dumb because I still don't get it...

I understand why q->last as only one element because of the line outside the if statement is basically "resetting" the value of q->last, no matter what are the q->last value, that line after the if statement will always assign it a different value which is the last one. I got that!

I still don't understand how q->first has all the elements.

In this code:

Code:

if (q->last)
  q->last->next = x;
else
  q->first = x;

The 'q->first = x' assignment will be performed only once. How come q->first has all the elements? That's what I don't understand and I must be very very stupid or everyone is failing in explaining this to me across every board I posted this question. And it's driving me crazy! :/

@matsp
The first version of the print function was in fact changing the queue cause I was passing it as a pointer but then I *fixed* it by passing the value.

**Elysia** · 12-12-2007

So, let's say you have written a big essay or something. It's many pages long. So you put all those papers on a desktop and each paper has a number to identify it. Let's say each paper has a number, 1, 2, 3, etc. Each paper tells you what paper comes next, so in paper one it says paper 2 is the continuation of the paper. This is so that you will know what paper comes after the next.
So page 2 comes after page 1. Okay? Get me?
That is the basics of a linked list.
Now.
Even though the first paper is numbered 1, we don't know it's the first paper, so we have another list. An index paper. In that index, there are two lines: first and last. For first, it says 1. Why? Because 1 is the first paper on the essay. So first actually tells you the position (or index) of the first paper of your essay. But it only says WHICH paper is first first paper of your essay.
The last tells you what paper is the last paper of your essay. If the essay is 10 pages, then it will say 10. The index or id of the last paper.

Remember now: each paper also holds information about which paper comes next. So if you read first and find it's paper 1, you pick up paper 1 and it says next comes paper 2 and paper 2 says next comes paper 3 and so on until the end.

If you read the last in the index and it says 10, you pick up the 10th paper and read it. But no paper comes next, because it's the last in the essay, so we can't go forward through there.

If you find that you want to change something, maybe add a paper to the essay at the beginning, you give it a unique id. Let's just say for sakes, 11. Then you must update the index so that it says the first paper in the essay is 11. Right? So paper 11 says that paper 1 is the continuation.

You can also add a paper as the last paper of the essay. Let's give it id 12. Now you look up in the index which paper is the current last paper. It says id 10. So we take paper 10 and add a line that says after this page comes page 12. Then you updated the index to mention that page 12 is the last in the essay.

Does all of that make any sense?

**tabstop** · 12-12-2007

Originally Posted by Nazgulled

The 'q->first = x' assignment will be performed only once. How come q->first has all the elements? That's what I don't understand and I must be very very stupid or everyone is failing in explaining this to me across every board I posted this question. And it's driving me crazy! :/

Do you still have your code from last term? Find a linked-list implementation without last, with insertions in the middle of the list (in sorted position or whatever) (if you have one, and if you don't someone just posted some not that long ago). I'll wait.

..
..
..

OK. Now notice that, in that case, you also only set list->first once, when you put the first element in the list. Every other time you inserted, you walked the list to find the spot. Yet, you can still walk the list. You start at first, and each node itself tells you where to go.

The point I'm trying (and failing) to make here is that q.first and q.last are not separate from each other or from q; q is the linked list and they each are just holding an end of it. You keep saying that you're adding things to q.first or to q.last, but that is not true. You add things to the list q (the links keep the order straight), and then you update the pointers if necessary. (So dequeue, if we ever get there, is going to leave q.last alone and change the value of q.first.)

Maybe another analogy, it might help: you can think of q as the usual linked list (each element knows who comes behind it). q.first answers the question "Who's next?" by pointing at the person who's at the front of the line. q.last points to the end of the line, so when a new person comes in, he lines up behind everyone else. Since each person knows who came in directly *after* themselves, we can start at q.first, q.first knows who came in next, that person knows who came in next, etc.

**brewbuck** · 12-12-2007

Originally Posted by Nazgulled

But this year, the teacher thrown into the mix this:

Code:

typedef struct {
	Node *first;
	Node *last;
} Queue;

Well, don't let it confuse you. Think back to your last course -- how did you keep track of the beginning of the list? Probably just some variable somewhere. This is just an extension of that. It keeps track of both the beginning and the end. And for clarity, these two variables are grouped together in a structure. That's all it is.

The only reason to remember the end of the list is to make tail-insertion more efficient. It's not strictly needed.

**MacNilly** · 12-12-2007

But this year, the teacher thrown into the mix this:

Code:

typedef struct 
{
	Node *first;
	Node *last;
} Queue;

I can tell you the reason for these two pointers. They give the EnQueue and DeQueue operations a O(1) complexity. In other words, constant-time access to the front and back of the queue. This means that, unlike your single-pointer queue which only has access to the front item in constant time, and has to "chase links" until it finds the last item, with large numbers of items in your queue this version will be more efficient.

The first pointer could be the "head" pointer of a linked list of nodes, while last could be an external pointer that is explicitly set each time an item is enqueued. At least that is how I would do it if I was given that structure and told to write operations.

**Nazgulled** · 12-12-2007

I think I'm almost getting the picture but not entirely... We already know that q->first has the first element that points to the next one and so on, correct? But that's exactly what I'm failing to understand, how does the q->first->next pointer points to the next element when in my code, I never do that. The enQueue() function creates a new element a new node named 'x' and I say that this new node will be the next one on q->last->next.

Is this because 'x' and 'q->first' and 'q->last' are all pointers and that's why it works that way and that's what I am failing to see/understand?

Thread: Issues and questions about queues

Thread Tools

Search Thread

Display

Issues and questions about queues

Similar Threads

Memory Questions

A very long list of questions... maybe to long...

Trivial questions - what to do?

Interview questions

Borland command line compiler issues.