Issues and questions about queues

This is a discussion on Issues and questions about queues within the C Programming forums, part of the General Programming Boards category; 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 ...

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #17
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Nazgulled View Post
    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.
    Except for when you do do it. Let's say the first node gets address 0x1000. We set the pointer in this node to NULL, and set q.first = q.last = 0x1000.
    We then allocate another node; let's say it it gets address 0x1008. We need to hook it onto the chain, so we find q.last = 0x1000 and set the pointer in that node to point to 0x1008. The pointer in 0x1008 gets set to NULL and then q.last gets set to 0x1008. The situation is now:
    q: 0x1000 -> 0x1008 -> NULL
    q.first = 0x1000
    q.first->next = pointer of 0x1000 = 0x1008
    q.last = 0x1008

    Note that when there was only one element in the queue, q.last = q.first. So setting q.last->next also sets q.first->next in this case, since q.last and q.first point to the same object. Just because it was referred to as q.last in your code, doesn't mean it can't equal q.first.

    And if we added another one (say 0x1008 now points at 0x1010), so that
    q: 0x1000 -> 0x1008 -> 0x1010 -> NULL
    q.first = 0x1000
    q.first->next = pointer of 0x1000 = 0x1008
    q.first->next->next = pointer of (pointer of 0x1000) = pointer of 0x1008 = 0x1010.

    Better?

    (You know, I would think someone, somewhere, has turned this into a movie. I wonder who and where.)

  3. #18
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    That's somewhat the kind of explanation I was waiting for... I think I get a better picture of the whole thing now. Now that I got most of this whole thing... Thank you very much, all of you!

    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?

    2) How would you code (in the most simple form) the print queue function?

    3) Using this structure for the queue, how would you implement a circular buffer? Taking advantage of the first and last pointers. Or do I need another pointer to point to the next free space? I can't see how would I do this...

  4. #19
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    326
    Quote Originally Posted by Nazgulled View Post
    That's somewhat the kind of explanation I was waiting for... I think I get a better picture of the whole thing now. Now that I got most of this whole thing... Thank you very much, all of you!

    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?

    2) How would you code (in the most simple form) the print queue function?

    3) Using this structure for the queue, how would you implement a circular buffer? Taking advantage of the first and last pointers. Or do I need another pointer to point to the next free space? I can't see how would I do this...
    I just posted a response that will answer your first question, look near the end of page 1.

    In the simplest form, to print a queue (from front to back) heres some pseudo-code:

    Code:
    define p as type pointer-to-node
    let p = head of queue
    while (p != NULL)
        print data
        let p = p->next
    end while
    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.

  5. #20
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,918
    Quote Originally Posted by Nazgulled View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    @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.

    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?

    @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?

  7. #22
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,918
    Quote Originally Posted by Nazgulled View Post
    @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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #23
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by MacNilly View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #24
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Quote Originally Posted by Elysia View Post
    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.
    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?

    Quote Originally Posted by Elysia View Post
    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).
    So, you are saying that this:
    Code:
    do{ ... } while(q->first->next);
    would crash? But wouldn't crash if I used a temporary variable?

    Quote Originally Posted by Elysia View Post
    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.
    Got it!

    @matsp
    I only asked about Circularly Linked Lists because I saw something about them in Wikipedia:
    Quote Originally Posted by http://en.wikipedia.org/wiki/Linked_list#Singly-circularly-linked_list
    In a singly-circularly-linked list, each node has one link, similar to an ordinary singly-linked list, except that the next link of the last node points back to the first node. As in a singly-linked list, new nodes can only be efficiently inserted after a node we already have a reference to. For this reason, it's usual to retain a reference to only the last element in a singly-circularly-linked list, as this allows quick insertion at the beginning, and also allows access to the first node through the last node's next pointer.
    And after reading this again, besides the point that Elysia pointed I'm not seeing how would I implement the insert, delete and print functions. And I would really like to know that. It's not for an exercise or something, I just want to know how things work so I have more knowledge on the subject.

  10. #25
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #26
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,918
    Quote Originally Posted by Nazgulled View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #27
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    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?
    Last edited by Nazgulled; 12-13-2007 at 11:35 AM.

  13. #28
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,918
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #29
    Registered User
    Join Date
    Mar 2006
    Posts
    158
    Quote Originally Posted by Elysia View Post
    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.
    You are right... I'm stupid and confusing everything that I missed that. What you stated here it's so obvious that I feel ashamed. :x

    Quote Originally Posted by Elysia View Post
    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);
    	}
    }
    Isn't that more like a syntax choice? That code and the code I posted earlier is basically the same thing isn't it?

    Quote Originally Posted by Elysia View Post
    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.
    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?

    Quote Originally Posted by Elysia View Post
    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!
    And I'm still confused about this!

  15. #30
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,918
    Quote Originally Posted by Nazgulled View Post
    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!
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory Questions
    By John_L in forum Tech Board
    Replies: 11
    Last Post: 10-07-2008, 07:35 PM
  2. A very long list of questions... maybe to long...
    By Ravens'sWrath in forum C Programming
    Replies: 16
    Last Post: 05-16-2007, 06:36 AM
  3. Trivial questions - what to do?
    By Aerie in forum A Brief History of Cprogramming.com
    Replies: 23
    Last Post: 12-26-2004, 09:44 AM
  4. Interview questions
    By Stony in forum Tech Board
    Replies: 0
    Last Post: 11-11-2002, 08:10 PM
  5. Borland command line compiler issues.
    By NinePin in forum C Programming
    Replies: 5
    Last Post: 09-05-2002, 06:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21