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 -

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

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

Enqueue more than one element.
Dequeue one time.
Enqueue more elements (optional)
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;
}

alex.forencich · Accepted Answer · 2016-09-01 02:24:41Z

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?

edited Sep 1, 2016 at 2:24

answered Sep 1, 2016 at 2:17

alex.forencich

1,44512 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

jacob · Accepted Answer · 2016-09-01 01:51:26Z

1

Program terminated with signal 11, Segmentation fault.
#0  0x0000000000400859 in main () at ./2.c:87
87          printf("%d\n",Q.front->r); // This line is giving segmentation fault 
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.80.el6.x86_64
(gdb) p Q
$1 = {front = 0x0, rear = 0x1636010, qsize = 1}

front is null and you access it. you just need a debuger like gdb to see what's going wrong with your program.

answered Sep 1, 2016 at 1:51

jacob

7116 silver badges15 bronze badges

1 Comment

Manish Sharma Over a year ago

But how is it null if I have enqueued one more element after dequeue operation ?

Collectives™ on Stack Overflow

Why is this queue implementation in C giving segmentation fault?

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related