Thread: 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;

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;

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

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

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).

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.

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.

Originally Posted by rcgldr

You could have dequeue return a pointer to the node removed from the queue

Originally Posted by laserlight

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.

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.

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.

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.

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, 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.

Originally Posted by laserlight

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.

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.