Why is this queue implementation in C giving segmentation fault?

Question

I have implemented a simple queue in C but its giving segmentation fault when I try to access Q.front after dequeuing (See int main() for example).

To be more precise, the problem occurs when I -

1. Enqueue a single element.
2. Dequeue it.
3. Enqueue one or more elements.
4. Try to access Q.front

However the program doesn't give segmentation fault or any error when I -

1. Enqueue more than one element.
2. Dequeue one time.
3. Enqueue more elements (optional)
4. Access Q.front successfully.

So this is my complete program -

#include <stdio.h>
#include <stdlib.h> //for malloc

struct qnode
{
    int r;
    struct qnode *link;
};

typedef struct qnode qNode;

typedef struct
{
    qNode *front;
    qNode *rear;
    int qsize;
}QUEUE;

QUEUE initializeQueue(void)
{
    QUEUE q;
    q.front = NULL;
    q.rear = NULL;
    q.qsize = 0;
    return q;
}


qNode *createQueueNode(int e)
{
    qNode *temp;
    temp = (qNode *) malloc(sizeof(qNode));
    if(temp == NULL)
    {
        printf("INSUFFICIENT MEMORY\n");
        exit(0);
    }
    temp->r = e;
    temp->link = NULL;
    return temp;
}
QUEUE enqueue(QUEUE q, int e)
{
    if(q.rear == NULL)
    {
        q.rear = createQueueNode(e);
        q.front = q.rear;
        q.qsize++;
    }
    else
    {
        q.rear->link = createQueueNode(e);
        q.rear = q.rear->link;
        q.qsize++;
    }
    return q;
}

QUEUE dequeue(QUEUE q)
{
    qNode *temp;
    if(q.front == NULL)
    {
        printf("queue is empty\n");
        exit(0);
    }
    else
    {
        temp = q.front;
        q.front = q.front->link;
        free(temp);
    }

    q.qsize--;
    return q;
}



int main(){

    QUEUE Q = initializeQueue();
    Q = enqueue(Q, 2);
    printf("%d\n",Q.front->r);
    Q = dequeue(Q);
    Q = enqueue(Q,4);
    printf("%d\n",Q.front->r); // This line is giving segmentation fault 

    return 0;
}

Answer 1

dequeue sets q.front to NULL (from q.front->link, which was previously set to NULL in createQueueNode) and leaves a trash pointer (to free()'d memory) in q.rear. Since q.rear is not NULL, the 2nd block in the if statement in enqueue gets executed on the 2nd call to enqueue. Which writes to free()'d memory (q.rear->link), then dereferences that into q.rear. I'm surprised it doesn't crash right there, actually, with the write to free()'d memory. Quick fix would probably be to set q.rear to NULL in dequeue if queue is empty. You should also add a sanity check so dequeue won't run on an empty queue.

Also, you've got an interesting way of passing that structure around like a hot potato. Why not pass it by reference and modify it in place instead of returning it?