How can I implement a basic queue in C?

Question

I am trying to learn data structures and I am struggling with getting this code to work. Problem is I am getting segmentation fault(core dumped) with gcc C compiler. It is supposed to be a queue. The code:

#include <stdio.h>
#include <stdlib.h>

#define STACK_SIZE 50

struct node{
    int data;
    struct node * next;
};

struct queue{
    int count;
    struct node * rear ,* front;
};

void create (struct queue * q) {
    q -> front = NULL;
    q -> rear = NULL;
    q -> count = 0;
}

int isempty(struct queue * q) {
    if(q -> count == 0)
        return 1;
    return 0;
}

int full(struct queue * q) {
    if(q -> count == STACK_SIZE) {
        return 1;
    }
    return 0;
}

void enqueue(struct queue * q , int x) {
    struct node * temp;
    temp = (struct node*) malloc(sizeof(struct node));

    temp -> data = x;
    temp -> next = NULL;

    if (full(q)) {
        printf("Not possible. Overflow.");
    }
    else if(isempty(q)) {
        q -> front = q -> rear = temp;
    } else {
        q -> rear -> next = temp;
        q -> rear = temp;
    }
    q -> count++;
}

int dequeue (struct queue * q) {
    struct node * p;
    p = (struct node*) malloc (sizeof(struct node));
    p = q -> front;

    if(isempty(q)) {
        printf("Not possible. Underflow.");
    } else {
        q -> front = q -> front -> next;
        q -> count--;
    }
    int x = (p -> data);
    return x;
}

int main (void) {
    struct queue *q;
    create (q);
    enqueue(q, 5);
}

The problem is most probably usage of pointers. I've reviewed it a few times but no solution. Valgrind and gdb debuggers weren't much of a help, either.

you have to allocate memory before accessing q in create — IrAM
– IrAM, Commented Dec 2, 2020 at 9:06
Try replacing struct queue *q; create(q); in the main with struct queue q; create(&q);. — Stef
– Stef, Commented Dec 2, 2020 at 9:08
Does this answer your question? Crash or "segmentation fault" when data is copied/scanned/read to an uninitialized pointer — Stef
– Stef, Commented Dec 2, 2020 at 9:11

August Karlstrom · Accepted Answer · 2020-12-02 09:42:54Z

3

As mentioned by OctaveL, in the function create you try to set the fields of the queue but the pointer passed to the function does not point to a queue, it is uninitialized. If you add the option -Wall to gcc it will actually warn you about this:

$ gcc -o test -Wall test.c
test.c: In function 'main':
test.c:71:5: warning: 'q' is used uninitialized in this function [-Wuninitialized]
     create (q);
     ^~~~~~~~~~

Solution 1: Declare q as a record and pass the address of q to the function create:

struct queue q;
create (&q);

Solution 2: Declare q as a pointer and allocate a new queue variable:

struct queue *q;
q = malloc(sizeof *q);
create(q);

I would also advice you to rename the function create to init or clear since it doesn't create a new queue, it only initializes (or clears) it.

To make memory allocation easier and to handle errors properly it is convenient to introduce two macros:

#define NEW_ARRAY(ptr, n) \
    (ptr) = malloc((n) * sizeof (ptr)[0]); \
    if ((ptr) == NULL) { \
        fprintf(stderr, "Memory allocation failed: %s\n", strerror(errno)); \
        exit(EXIT_FAILURE); \
    }

#define NEW(ptr) NEW_ARRAY(ptr, 1)

With these in place and if create is renamed to init you can write solution 2 as

struct queue *q;
NEW(q);
init(q);

answered Dec 2, 2020 at 9:42

August Karlstrom

11.4k8 gold badges45 silver badges70 bronze badges

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

3 Comments

Ali A Over a year ago

Much obliged. Thanks for in-depth answer.

Stef Over a year ago

The gcc warning advice is great. But the answer should maybe emphasize that solution 1 is a priori preferable to solution 2.

August Karlstrom Over a year ago

@Stef Indeed! I mentioned the macros since Ali A uses memory allocation in other parts of the code.

OctaveL · Accepted Answer · 2020-12-02 09:07:58Z

2

You didn't allocate memory for q in your main(), so it crashes when attempting to access q->front in create().

int main (void) {
    struct queue *q; // No allocation here
    ...
}

You probably wanted this, which works just fine:

int main (void) {
    struct queue q;
    create (&q);
    enqueue(&q, 5);
}

answered Dec 2, 2020 at 9:07

OctaveL

1,0451 gold badge9 silver badges20 bronze badges

2 Comments

Ali A Over a year ago

Thank you so much. I hope I won't get some people angry by asking a basic question but it happens, right?

OctaveL Over a year ago

@AliA Hah, StackOverflow is home to many questions a lot less advanced than yours - you're hardly angering anyone :P

Collectives™ on Stack Overflow

How can I implement a basic queue in C?

2 Answers 2

3 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related