Thread: Queues

  1. #1
    Registered User
    Join Date
    Sep 2013
    Location
    Jamaica
    Posts
    134

    Queues

    I'm having a problem with removing an item from a queue. At first in the debugger I got SIGTRAP but I don't get it anymore but the problem still exists. When you try to remove an item from the queue the first nothing happens. Here's the code below compile it and you see what I'm talking about.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    struct Node
    {
        char let;
        struct Node *nextNode;
    };
    
    
    typedef struct Node queueNode;
    typedef struct Node *Queue;
    
    
    void enqueue(Queue *headNode, Queue *tailNode, char letter);
    char dequeue(Queue *headNode, Queue *tailNode);
    int Empty(Queue headNode);
    void printQueue(Queue headNode);
    
    
    int main(void)
    {
        Queue headNode = NULL;
        Queue tailNode = NULL;
        
        int option;
        char letter;
        
        printf("%s\n%s\n%s\n\n%s\n", "1) Add letter", "2) Remove letter", "3) list queue", "4) End");
        scanf("%d", &option);
        while(option != 4)
        {
            switch(option)
            {
                case 1:
                    printf("Enter a letter to added: ");
                    scanf("%c", &letter);
                    enqueue(&headNode, &tailNode, letter);
                    break;
                case 2:
                    if(!Empty(headNode))
                    {
                        letter = dequeue(&headNode, &tailNode);
                        printf("Node containing \'%c\' was removed\n", letter);
                    }
                    else
                    {
                        printf("The queue is already empty!\n");
                    }
                    break;
                case 3:
                    printQueue(headNode);
                    break;
                case 4:
                    printf("\nExiting....\n");
                    break;
                default:
                    printf("Invalid Entry!!!\n");
                    printf("Enter a new option: ");
                    break;
            }
            scanf("%d", &option);
        }
        
        return 0;
    }
    
    
    void enqueue(Queue *headNode, Queue *tailNode, char letter)
    {
        Queue newNode;
        
        newNode = malloc(sizeof(queueNode));
        if(newNode != NULL)
        {
            newNode->let = letter;
            newNode->nextNode = NULL;
            if(Empty(*headNode))
            {
                *headNode = newNode;
            }
            else
            {
                (*tailNode)->nextNode = newNode;
            }
            *tailNode = newNode;
        }
        else
        {
            printf("Could NOT update queue!\n");
        }
    }
    
    
    char dequeue(Queue *headNode, Queue *tailNode)
    {
        Queue Temp;
        
        char let;
        
        let = (*headNode)->let;
        Temp = *headNode;
        *headNode = (*headNode)->nextNode;
        if(*headNode == NULL)
        {
            *tailNode = NULL;
        }
        free(Temp);
        
        return let;
    }
    
    
    int Empty(Queue headNode)
    {
        return headNode == NULL;
    }
    
    
    void printQueue(Queue curNode)
    {
        if(curNode == NULL)
        {
            printf("Queue is empty!\n");
        }
        else
        {
            printf("\nItems in queue:\n\t");
            while(curNode != NULL)
            {
                printf("%c --> ", curNode->let);
                curNode = curNode->nextNode;
            }
            printf("\nQueue listing complete.\n");
        }
    }

    EDIT: I corrected the typedef and I still get the problem.
    Code:
    typedef struct Node queueNode;
    typedef queueNode *Queue;
    Last edited by BIGDENIRO; 08-17-2014 at 11:24 PM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,929
    Instead of:
    Code:
    typedef struct Node *Queue;
    
    /* ... */
    
    Queue headNode = NULL;
    Queue tailNode = NULL;
    I suggest:
    Code:
    struct Queue
    {
        struct Node *head;
        struct Node *tail;
    };
    
    /* ... */
    
    struct Queue queue = {NULL, NULL};
    Then these:
    Code:
    void enqueue(Queue *headNode, Queue *tailNode, char letter);
    char dequeue(Queue *headNode, Queue *tailNode);
    int Empty(Queue headNode);
    void printQueue(Queue headNode);
    will become:
    Code:
    void enqueue(struct Queue *queue, char letter);
    char dequeue(struct Queue *queue);
    int Empty(const struct Queue *queue);
    void printQueue(const struct Queue *queue);
    EDIT:
    In enqueue, this is confusing:
    Code:
    Queue newNode;
    
    newNode = malloc(sizeof(queueNode));
    A reader reading this would wonder why you created a new Queue and called it newNode when it seems you want a new node, not a new queue. Furthermore, the reader will have to check to be sure that Queue is indeed a pointer to queueNode, which means that the typedef hinders rather than helps readability. Rather, you could have written:
    Code:
    struct Node *newNode = malloc(sizeof(*newNode));
    Then with my suggestion, at some point you might write:
    Code:
    queue->head = newNode;
    Last edited by laserlight; 08-17-2014 at 11:54 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Sep 2013
    Location
    Jamaica
    Posts
    134
    OK thanks for the tips, ill let you know what happens

  4. #4
    Registered User
    Join Date
    Sep 2013
    Location
    Jamaica
    Posts
    134
    OK, laserLight I did what you said and I get one error when I complie. The error is at the free() when deleting node form queue.

    Code:
    #include <stdio.h>#include <stdlib.h>
    
    
    struct Node
    {
        char let;
        struct Node *nextNode;
    };
    
    
    struct line
    {
        struct Node *headNode;
        struct Node *tailNode;
    };
    
    
    void enqueue(struct line *Queue, char letter);
    void dequeue(struct line *Queue);
    void printQueue(struct line Queue);
    
    
    int main(void)
    {
        struct line Queue = {NULL, NULL};
        
        int option;
        char letter;
        
        printf("%s\n%s\n%s\n\n%s\n", "1) Add letter", "2) Remove letter", "3) list queue", "4) End");
        do
        {
            scanf("%d", &option);
            switch(option)
            {
                case 1:
                    printf("Enter a letter to add to the queue: ");
                    scanf("%c", &letter);
                    enqueue(&Queue, letter);
                    break;
                case 2:
                    if(Queue.headNode == NULL)
                    {
                        printf("Queue is already empty.\n");
                    }
                    else
                    {
                        dequeue(&Queue);
                    }
                    break;
                case 3:
                    printQueue(Queue);
                    break;
                default:
                    printf("Invalid entry!\n");
                    printf("Enter new choice: ");
                    break;
            }
        }while(option != 4);
        
        return 0;
    }
    
    
    void enqueue(struct line *Queue, char letter)
    {
        struct Node *newNode;
        
        newNode = malloc(sizeof(struct Node));
        if(newNode == NULL)
        {
            printf("Could NOT update queue.\n");
        }
        else
        {
            newNode->let = letter;
            newNode->nextNode = NULL;
            if(Queue->headNode == NULL)
            {
                Queue->headNode = newNode;
            }
            else
            {
                Queue->tailNode->nextNode = newNode;
                Queue->tailNode = newNode;
            }
        }
    }
    
    
    void dequeue(struct line *Queue)
    {
        struct Node Temp;
        
        char value;
        
        value = Queue->headNode->let;
        Temp = *Queue->headNode;
        Queue->headNode = Queue->headNode->nextNode;
        if(Queue->headNode == NULL)
        {
            Queue->tailNode = NULL;
        }
        free(Temp);
        printf("Node containing \'%c\' was removed.\n", value);
    }
    
    
    void printQueue(struct line Queue)
    {
        if(Queue.headNode == NULL)
        {
            printf("Queue is empty.\n");
        }
        else
        {
            printf("Listing elements in queue:\n\t");
            while(Queue.headNode != NULL)
            {
                printf("%c --> ", Queue.headNode->let);
                Queue.headNode = Queue.headNode->nextNode;
            }
            printf("NULL\n");
            printf("Queue listing complete.\n");
        }
    }
    EDIT: I edited to code and got to compile still getting the same problem. correct me if I'm I think its accepting new line as a entry because it keeps deleting and adding it
    Last edited by BIGDENIRO; 08-18-2014 at 02:25 PM.

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,877
    Something I noticed here:
    Code:
    printf("Enter a letter to add to the queue: ");
    scanf("%c", &letter);
    Code:
    printf("Enter a letter to add to the queue: ");
    
    fflush(stdout);           //If a printf does not end in a '\n', it's a good idea to force a flush
    
    scanf(" %c", &letter);  //Adding a space before the %c consumes any white characters, 
                                    //such as \n left on the input buffer
    Fact - Beethoven wrote his first symphony in C

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    You might want to consider adding code to dequeue to check for headNode == NULL (currently you check for this in main). You could have dequeue return a pointer to the node removed from the queue or NULL (if headNode == NULL), and check that returned pointer in main to see if it's NULL. The "printf" in dequeue to show which node was deleted could also be moved to main, using the returned pointer (either NULL or returned pointer ->value).
    Last edited by rcgldr; 08-18-2014 at 06:41 PM.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,929
    Quote Originally Posted by BIGDENIRO
    The error is at the free() when deleting node form queue.
    In dequeue, Temp should be a pointer to struct Node, not a struct Node object.

    Quote Originally Posted by rcgldr
    You could have dequeue return a pointer to the node removed from the queue or NULL (if headNode == NULL), and check that returned pointer in main to see if it's NULL.
    Problem with that is then the freeing of the memory for the node must be handled outside of dequeue, which is likely to be error prone.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    Quote Originally Posted by rcgldr View Post
    You could have dequeue return a pointer to the node removed from the queue
    Quote Originally Posted by laserlight View Post
    Problem with that is then the freeing of the memory for the node must be handled outside of dequeue, which is likely to be error prone.
    True, most of my experience with using queues / linked lists / nodes is as part of (multi-threaded) messaging system, where there is a one time allocation of nodes that initially go into a free pool, and the nodes end up returned to that free pool as opposed to being actually free'd. With this messaging usage, it's also common for enqueue to return a count of elements in the queue after it returns, which is really only used when the returned count is one, meaning that a queue went from empty to non-empty, which could be used to initiate some type of hardware and/or software interrupt driven or call back sequence that feeds off that queue (and goes idle if the queue goes empty).

    As an alternative, the caller could have a local copy of the node, and enqueue and dequeue would be a copy interface, using a pointer to the caller's local node. This would be similar to how the C++ STL push_back functions work, and I think a template could be use to create a pop_front template that takes a pointer as a parameter and uses the STL peek_front and pop_front functions. However, there would need to be some type of synchronization code added if being used for inter-thread communication.
    Last edited by rcgldr; 08-19-2014 at 05:36 AM.

  9. #9
    Registered User zub's Avatar
    Join Date
    May 2014
    Location
    Russia
    Posts
    104
    Tip: Create a dummy element in each list. It point to the first element. This greatly simplifies inserting and deleting. For example, to insert an element at the beginning of the list, we just insert it after the dummy.
    Our goals are clear, tasks are defined! Let's work, comrades! -- Nikita Khrushchev

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    Quote Originally Posted by zub View Post
    Tip: Create a dummy element in each list. It point to the first element. This greatly simplifies inserting and deleting. For example, to insert an element at the beginning of the list, we just insert it after the dummy.
    There's already a structure with a head and tail node pointers. With or without a dummy element, the code will still need to check for an empty list, either for NULL head or tail pointer (no dummy element used), or head == tail pointer (only dummy element on list). Where a dummy element helps is if there is no structure with a head or tail pointer, but only node structures.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,929
    Quote Originally Posted by rcgldr
    As an alternative, the caller could have a local copy of the node, and enqueue and dequeue would be a copy interface, using a pointer to the caller's local node. This would be similar to how the C++ STL push_back functions work
    BIGDENIRO's enqueue function already copies the value. The function corresponding to dequeue in the C++ standard library's queue container adapter does not do copying: rather, it is expected that the front member function will be called to examine the front of the queue, so the pop member function's sole task is to destroy the element at the front of the queue.

    Quote Originally Posted by rcgldr
    I think a template could be use to create a pop_front template that takes a pointer as a parameter and uses the STL peek_front and pop_front functions.
    This is C, not C++, so BIGDENIRO presumably would not be writing a C++ template.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Apr 2013
    Posts
    1,656
    Quote Originally Posted by rcgldr View Post
    As an alternative, the caller could have a local copy of the node, and enqueue and dequeue would be a copy interface, using a pointer to the caller's local node. This would be similar to how the C++ STL push_back functions work, and I think a template could be use to create a pop_front template that takes a pointer as a parameter and uses the STL peek_front and pop_front functions. However, there would need to be some type of synchronization code added if being used for inter-thread communication.
    Quote Originally Posted by laserlight View Post
    This is C, not C++, so BIGDENIRO presumably would not be writing a C++ template.
    Forgot about that, so not a template, but a modified or alternate dequeue function. If synchronization is needed for queue and dequeue operations, then a function that would combine something like peek_front and pop_front could be used. It would return a copy of the first node in the queue (via a pointer passed as a parameter), and the return value would indicate if the queue was non-empty (and a copy peformed) or empty (nothing to copy). In this case the "nodes" only contain a single member, which is a single letter.
    Last edited by rcgldr; 08-19-2014 at 04:50 PM.

  13. #13
    Registered User
    Join Date
    Sep 2013
    Location
    Jamaica
    Posts
    134
    Well the problem was that it was accepting the newline entry. the queue won't be filled by user anyways for its not a problem, but thanks guyz for all the help. BTW i one write C, C++ looks easier and more flexible but the transition would be a bit difficult so I'm sticking to grandpa.


    BTW, quick question is it possible to keep track of nodes in the queue? I've been searching ending up with nothing.
    Last edited by BIGDENIRO; 08-20-2014 at 09:01 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. queues
    By ashrrey in forum C Programming
    Replies: 3
    Last Post: 11-21-2010, 07:58 AM
  2. queues
    By rebelfirst in forum C++ Programming
    Replies: 9
    Last Post: 12-02-2007, 05:33 AM
  3. Regarding queues!!
    By coolkarthik20 in forum C Programming
    Replies: 2
    Last Post: 06-13-2007, 05:08 AM
  4. Queues
    By ramayana in forum C Programming
    Replies: 22
    Last Post: 01-01-2006, 02:08 AM
  5. queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 10-11-2001, 05:19 PM