A queue using structs and dynamic memory allocation

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?

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

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.

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

You are passing myqueue by value so the allocation happened at init() is for the copy of myqueue not to myqueue.

So the correct version is:

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

and you can call init() from main

init(&myqueue);

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

Minor nitpick, but your init function has no return value so perhaps change it to:

void init(Queuepointer *q) {

or

int init(Queuepointer * qp){ 
    Queuepointer q = (Queuepointer)malloc(sizeof(struct queue));
    q->front = NULL;
    q->back = NULL;
    *qp = q;
    if(q) {
        return 1;
    } else return 0;
}

Adjust according to how you want to perform error checking.