Thread: Issues and questions about queues

Yes, that's a good summary.

When you set queue->last->next to x the first time around, queue->last and queue->first point the same thing. So queue->first->next is set to x. Next time, queue->first->next->next is being set, but it's not using this convoluted method, but rather the simple method of setting queue->last->next = x;

--
Mats

Originally Posted by Nazgulled

1) Why exactly do I need a queue with a pointer to the beginning and end of the queue? In what is this method helpful?

First, it's quicker. You only beed to do q->first or q->last to find the last or first node in the list.
Otherwise you have to do q->first->next->next->next, etc until next is NULL, at which point you have found the end. It's simpler.
Second it's also faster because you don't have to walk the list to the end. You can just jump to the end directly.

Originally Posted by Nazgulled

@MacNilly
It doesn't matter if there is a need for a circular buffer or not, this is not an exercise or a school project, I just want to know how things work. And a circulary linked list is one of those things that I would like to know how it works and how it's coded. Can you provide any link explaining the whole thing? I tried to look for an example on google but couldn't find anything.

Well, an easy way would be to do q->last->next = q->first. Why? Because it would mak the last node in the list point to the first, so when you reach the end, and try to move further, you get back to the beginning again! Thus it's circular.

About your pseudo-code:
Why define p as as type pointer-to-node and assign the head of queue to p? Why can't I just traverse q->first directly?

If you want to traverse a node and you don't know the end, then you need a temporary pointer which you can use to traverse with. You can do quene->first->next->next->next, but how do you know where the end is? Further, if you actually try to walk further than the end, you try to dereference NULL, which will lead to a crash.
Therefore, we use a temporary variable, assign that to quene->first, and then check if p == NULL (in which case there's only one node in the list, since q->first is the first node and if the first node points to NULL, there is no second node, no node after the first node).

@Elysia
But why do I need to access directly to the end of the queue? I will only have one element the end and the next pointer will be pointing to null, why would I need only this last element to use a method like his instead of the trivial q->next->next->next... that I'm used to? Why would I need to access the last element?

Because you get to the end of the list quickly!
When you want to insert something at the end of the list, you need to set the last node's next to the new last, right? So you need to traverse the list to find the last node so you can assign its next!
But with a end pointer, you can simply use it to skip to the end directly. No need to traverse the list to get to the end. It's more efficient too.

Which method do you find more efficient - say you have a bunch of papers and you don't know which one is the last, but each paper points to the paper that comes next and you know which paper is the first. Would you examine all the papers to eventually get to the end or would you just check in a last or ask someone which paper is the last and get it directly?
It's the same thing.

Originally Posted by MacNilly

Circular buffers are implemented using arrays, not linked lists. You could implement using a circularly linked list, where the last node's next pointer goes back to the front... but they are two entirely different beasts. Actually you can have constant-time enqueue and dequeue operations if you code everything correctly, there is no need for a circular buffer or a circularly-linked list. Just keep it the way it is.

I would completely agree with this: A circular buffer is a way to implement a FIFO[1], where a queue is a different implementation to solve a FIFO. There are different advantages with each of those solutions: a circular buffer is [usually] implemented as an array, where you have an "in" and an "out" index, so "stuff" is put into the "in" index, and the index is progressed to the next entry, and "stuff" is taken out at the "out" index and the index progressed to the next entry. The drawback of a array based FIFO is that it's limited to a certain size. You have to use the correct checks to make sure that the circular buffer doesn't overflow, and if you get into that situation, things can go very wrong.

A queue FIFO requires allocation to insert, and freeing when you remove items from the list, but has an "unlimited"[2] size. You can of course add some sort of counter to track the number of entries in the queue, and "refuse" when it gets too long.

Which is better depends a lot on what the exact problem is.

[1] FIFO means "First in, first out", as opposed to a LIFO - last in, first out -> a stack.

[2] Obviously, there is a limit, but it's determined by the amount of memory, rather than something compiled into the code at build-time.

--
Mats

A circular linked list just uses "first" as a marker for end, rather than NULL. It can be practical for certain types of implementations, as you can be guaranteed to NEVER hit a NULL pointer - but you still need to compare with "first" instead for most places where you now compare with NULL. And set the next pointer to "first" instead of NULL whenever you set up a new link.

As to your code example, you can not dereference queue->first->something if queue->first == NULL - that will crash.

--
Mats

Originally Posted by Nazgulled

That's what I thought but that leaves me to another question. Let's say I do that (q->last->next = q->first) and in my print list I would "loop" until q->last->next != NULL, this would mean that I would be "looping" through all the queue elements over and over again right? There would be no real way to know which element is the first and which one is the last, right?

The best way would be to keep track of the end of and the start of the list (those start and end pointer we're talking about). So you check to see if p->next is q->first. That would mean you found the last node because the last node points to the first!

So, you are saying that this:

Code:

do{ ... } while(q->first->next);

would crash? But wouldn't crash if I used a temporary variable?

As matsp points out, if q->first is NULL, then yes, it will crash.
But you also need to advance in the list, so you need to store p->first first, then keep on looping while p->next is not NULL. Then you assign p->next to p and you get the next node. And so on.

About the crashing/listing the elements, I have a few questions as I did some testing using the same structures defined as in the first post.

I used the following code with a temporary variable just like you guys said like this:

Code:

void listQueue(Queue *q) {
	Node *ptr;
	ptr = q->first;
	
	while(ptr) {
		printf("%d", ptr->elem);
		ptr = ptr->next;
	}
}

This works, I can call this function over and over and it works fine. Then I tested the way you said it would crash, like this:

Code:

void listQueue(Queue *q) {
	while(q->first) {
		printf("%d", q->first->elem);
		q->first = q->first->next;
	}
}

This also works, it didn't crash. Well, for some part. I mean, I called listQueue() once and it listed everything without crashing, however, calling it again, crashed with segmentation fault. This was the crashing you were talking about right?

But, this happens because we are passing the queue argument as a pointer and I decided to do it like this instead:

Code:

void listQueue(Queue q) {
	while(q.first) {
		printf("%d", q.first->elem);
		q.first = q.first->next;
	}
}

For this to work, I would have to call the function like this, listQueue(*q), instead of, listQueue(q) as in the previous examples. So, isn't this a better way? I have a feeling you are going to say it's not and I should opt for the method with a temporary variable. But why is that method better? What are the differences?

Why is that code doing? It's overwriting the previous variable.
It's like erasing your index pointer to the first element and replacing it with first->next.
So when the function is complete q.first will be NULL. Oops! Yes. You lost track of the first element in the list.

While the second approach works, it's not necessarily the best and to me it looks like a very poor workaround. Basically you're just creating a copy of the Queue pointer for the function to mess around with. But it's also copying the entire Queue structure, which is larger than a single pointer. Your structure is currently 8 bytes, while a pointer is a mere 4 bytes.

Also, note that a for loop might be better for this purpose:

Code:

void listQueue(const Queue *q)
{
	for (Node* ptr = q->first; p != NULL; p = p->next)
	{
		printf("%d", ptr->elem);
	}
}

Also, since it's a pointer, the function can modify the data you passed it and it will reflect from the function that calls it. In this case, you would probably not want it to modify the memory because it's just listing the contents. So make it const. It tells the compiler that the function can't modify the memory it points to. And thus you get a compile error with the second of your examples because you modify the memory.

Originally Posted by Nazgulled

Isn't that more like a syntax choice? That code and the code I posted earlier is basically the same thing isn't it?

Yes, it's the same thing.

What do you mean by that (the text in bold)? Are you telling me to declare some variable as 'const'? I'm used to that in another languages but I don't know how to do it C nor which variable you were talking about. Can you be more specific and also tell me how do I use 'const' in C or you meant something different?

Let me show you with an example:

Code:

void foo(const int* pNum)
{
	*pNum = 50; /* Compile error! Not allowed to modify variable because it's const */
}

void foo2(int* pNum)
{
	*pNum = 50;
}

int main()
{
	int myint;
	foo(&myint);
	foo2(&myint);
	/* myint is now 50 */
	return 0;
}

And I'm still confused about this!

Code:

void listQueue(const Queue *q)
{
	for (Node* ptr = q->first; p != q->first; p = p->next)
	{
		printf("%d", ptr->elem);
	}
}

Remember: in a circular list, the last node will point to the first node. q->first will also keep track of the first node in the list, so if they match... then it means that the pointer is pointing to the first node in the list!