A queue using structs and dynamic memory allocation

Question

I am tasked with making a queue data structure in C, as a linked list. Our lecturer gave us a large amount of code to implement a stack, but we have to adapt it to create a queue. The code our lecturer gave us ends up not compiling and segfaulting at the exact same point as the code I wrote for the queue. I'm very new to structs, malloc and C in general, so there could be something painfully obvious I've overlooked.

Here is the code I am using:

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;               //contains the actual data
    struct node *prev;      //pointer to previous node (Closer to front)
    struct node *next;      //pointer to next node (Closer to back)
};

typedef struct node *Nodepointer;

struct queue{
    Nodepointer front;
    Nodepointer back;
};

typedef struct queue *Queuepointer;

main(){
    Queuepointer myqueue;       //create a queue called myqueue
    init(myqueue);              //initialise the queue
    Nodepointer new = (Nodepointer)malloc(sizeof(struct node));
    myqueue->front = new;
}

int init(Queuepointer q){ 
    q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
}

The idea is that the queue struct 'contains' the first and last nodes in a queue, and when a node is created, myqueue is updated. However, I cannot even get to that part (pop and push are written but omitted for brevity). The code is segfaulting at the line

myqueue->front = new;

with the following gdb output:

Program received signal SIGSEGV, Segmentation fault.
0x08048401 in main () at queue.c:27
27  myqueue->front = new;

Any idea what I'm doing wrong?

Solution 1

When you call init:

int init(Queuepointer q){ 
    q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
}

You're passing a pointer to a queue into the function, and initializing where that pointer points (in memory) within the function. By setting q = ..., you're assigning a new value to q.

Unfortunately, the calling function does not see this. You need to pass a pointer to a pointer instead:

int init(Queuepointer * qp){ 
    Queuepointer q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
    // Set qp:
    *qp = q;
}

Then change the calling function:

init(&myqueue);

Solution 2

init(myqueue); passes by value a pointer to unallocated memory. init does nothing on it, consequently (instead, writing random things at random location).

Then, myqueue->stuff does it again.

You should have used pointer to pointer.

Init will receive queue**, and called as init(&myqueue). Inside, *myqueue=()malloc stuff

Also, I recommend you against these typedefs. They are rather bad style.

Solution 3

The first problem I see is that the "init" function writes the allocated pointer in "q", that is NOT your original "myqueue". Remember that C passes its arguments by value. A possible correction (not perfect, just a hint) is

Queuepointer init(void)
    Queuepointer q; 
    q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
    return q;
}
`

And in "main":

myqueue = init();

Also beware that in your program you don't initialize the element allocated by malloc. malloc doesn't in general clean the memory it allocates.

Regards

Comments

[Martin Pugh]

Thank you very much. Both yours and Pavel's answers were very good. I think I understand the code much better now :)