Segmentation Fault(core dumped) Queue Operation using linked list-CodePudding

I have written a code in c to implement queue operations using linked list, like insertion, deletion, peek and display.

I use vscode to run and compile my codes.

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
    int data;
    struct Node *next;
}node;
typedef struct Queue{
    node *front;
    node *rear;
}queue;
queue *q=NULL;
int isempty(queue *);
void create(queue *);
queue *insert(queue *);
queue *delete(queue *);
void display(queue *);
void peek(queue *);
int main(){
    int o;
    create(q);
    do{
        printf("\nQueue Operations");
        printf("\n1. Insert");
        printf("\n2. Delete");
        printf("\n3. Peek");
        printf("\n4. Display");
        printf("\n5. Exit");
        printf("\nEnter Option : ");
        scanf("%d",&o);
        switch(o){
            case 1:
                insert(q);
                break;
            case 2:
                delete(q);
                break;
            case 3:
                peek(q);
                break;
            case 4:
                display(q);
                break;
            case 5:
                break;
            default:
                printf("Invalid Option");
                break;
        }
    }
    while(o!=5);
}
void create(queue *q)
{
    q->front=NULL;
    q->rear=NULL;
}
queue *insert(queue *q){
    node *p;
    p=(node *)malloc(sizeof(node));
    printf("Enter Data : ");
    scanf("%d",&p->data);
    if(q->front=NULL){
        q->front=p;
        q->rear=p;
        q->front->next=q->rear->next=NULL;
    }
    else{
        q->rear->next=p;
        q->rear=p;
        q->rear->next=NULL;
    }
    return q;
}
int isempty(queue *q){
    if(q->front==NULL)
        return 1;
    else 
        return 0;
}
queue *delete(queue *q){
    node *p;
    int t;
    p=q->front;
    t=isempty(q);
    if(t==1)
        printf("Queue Empty");
    else{
        q->front=q->front->next;
        printf("Value Deleted : %d",p->data);
        free(p);
    }
    return q;
}
void peek(queue *q){
    int t;
    t=isempty(q);
    if(t==1)
        printf("Queue Empty");
    else
        printf("Peek:%d",q->front->data);
}
void display(queue *q){
    node *p;
    p=q->front;
    if(p==NULL)
        printf("Queue is Empty");
    else{
        while(p!=q->rear){
            printf("%d\t",p->data);
            p=p->next;
        }
        printf("%d\t",p->data);
    }
}

I am not understanding why i am getting a segmentation fault in this question.

This code was in my book i Just blindly copied this one but still i am getting the error. I tested the code in online compilers as well to be sure that my machine is not having any fault but still getting the same issue.

If anyone can help me out.

CodePudding user response：

q is not pointing to anything. When you deference it in create() you are writing to random memory which will usually cause a crash.

You should define q as type queue (no pointer) and pass the address of it to the sub functions.

CodePudding user response：

Whenever pointer is dereferenced, it should be allocated fair amount of memory through malloc before its usage. Hence, while creation of linked list, queue pointer should be allocated and passed back to main for using it. Attached modified queue creation code below for reference,

queue* create(queue *q)
{
q= (queue*)malloc(sizeof(queue));
q->front=NULL;
q->rear=NULL;
return q;
}

Update calling function in main as well.

CodePudding user response：

The create function needs allocating memory you can't create without allocating memory whenever you allocate it inside create function or pass queue with already allocated memory (you can't do both solutions at same time just one of them) and the first one is preferred for making organized code.

queue* create(queue *q)
{
q= (queue*)malloc(sizeof(queue));
q->front=NULL;
q->rear=NULL;
return q;
}

Another bug in insert function if(q->front=NULL){ that will make q->front actually assigned to null and it will lead to segmentation fault , you should need checking == not assigning =

if(q->front==NULL){ will make it works more correctly

CodePudding user response：

For starters it is a bad idea when functions depend on a file scope variable as in your program where functions depend on the variable q.

queue *q=NULL;

Secondly, you are using a null pointer in the function create.

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

that invokes undefined behavior.

There is no great sense to declare a pointer of the type queue instead of declaring an object of the type queue.

So instead of this definition in the file scope

queue *q=NULL;

it is much better to write in main

queue q = { .front = NULL, .rear = NULL };

queue q;
create( &q );

The function isempty can be written simpler

int isempty( const queue *q )
{
    return q->front == NULL;
}

The function insert should not ask any question. The value that is added to the queue should be passed to the function as an argument.

It is the caller of the function that should provide the value.

Pay attention to that allocation of memory can fail, You should process such a situation in the function. Otherwise again the function can invoke undefined behavior.

Also instead of using comparison you are using assignment in this if statement

if(q->front=NULL){

The function can be written the following way

int insert( queue *q, int data )
{
    node *p = malloc( sizeof( *p ) );
    int success = p != NULL;

    if ( success )
    {
        p->data = data;

        if ( q->front == NULL )
        {
            q->front = p;
        }
        else
        {
            q->rear->next = p;
        }

        q->rear = p; 
    }

    return success;
}

In the function delete you are not updating q->rear if the queue contains only one node.

Again the function should not issue any message. It is the caller of the function that decides whether to output a message.

The function should be defined the following way

int delete( queue *q )
{
    int success = !isempty( q );

    if ( success )
    {
        node *p = q->front;
        q->front = q->front->next;

        if ( q->front == NULL ) q->rear = NULL;

        free( p );
    }

    return success;
}

The function peek should return by reference its data member data because the user of the function can want to process the value.

The function can look the following way

int peek( queue *q, int *data )
{
    int success = !isempty( q );

    if ( success )
    {
        *data = q->front->data;
    }

    return success;
}

The parameter of the function display should have the qualifier const because the queue is not changed within the function.

The function can be defined the following way

void display( const queue *q )
{
    if ( isempty( q ) )
    {
        puts( "Queue is Empty" );
    }
    else
    {
        for ( const node *p = q->front; p != NULL; p = p->next )
        { 
            printf( "%d", p->data );
            if ( p != q->rear ) putchar( '\t' );
        }
        putchar( '\n' );
    }
}

Here is your updated program.

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

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

typedef struct Queue
{
    node *front;
    node *rear;
} queue;

int isempty( const queue *q )
{
    return q->front == NULL;
}

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

int insert( queue *q, int data )
{
    node *p = malloc( sizeof( *p ) );
    int success = p != NULL;

    if ( success )
    {
        p->data = data;
        
        if ( q->front == NULL )
        {
            q->front = p;
        }
        else
        {
            q->rear->next = p;
        }

        q->rear = p; 
    }

    return success;
}

int delete( queue *q )
{
    int success = !isempty( q );

    if ( success )
    {
        node *p = q->front;
        q->front = q->front->next;

        if ( q->front == NULL ) q->rear = NULL;

        free( p );
    }

    return success;
} 

int peek( queue *q, int *data )
{
    int success = !isempty( q );

    if ( success )
    {
        *data = q->front->data;
    }

    return success;
}

void display( const queue *q )
{
    if ( isempty( q ) )
    {
        puts( "Queue is Empty" );
    }
    else
    {
        for ( const node *p = q->front; p != NULL; p = p->next )
        { 
            printf( "%d", p->data );
            if ( p != q->rear ) putchar( '\t' );
        }
        putchar( '\n' );
    }
}

int main( void ) 
{
    queue q;
    create( &q );
 
    int option = 5;
    
    do
    {
        printf("\nQueue Operations");
        printf("\n1. Insert");
        printf("\n2. Delete");
        printf("\n3. Peek");
        printf("\n4. Display");
        printf("\n5. Exit");
        
        printf("\nEnter Option : ");
        
        scanf( "%d", &option );
        
        switch( option )
        {
        case 1:
        {
            printf( "Enter Data : " );
            int data;
            
            if ( scanf( "%d", &data ) == 1 )
            {
                if ( !insert( &q, data ) )
                {
                    puts( "Error: not enough memory." );
                }
            }
            else
            {
                puts( "Invalid input." );
            }
            
            break;
        }

        case 2:
        {
            if ( !delete( &q ) )
            {
                puts( " Error: queue is empty." );              
            }
            else
            {
                puts( "First element of the queue has been deleted." );
            }
            
            break;
        }
        
        case 3:
        {
            int data;
            if ( peek( &q, &data ) )
            {
                printf( "The value is %d\n", data );
            }
            else
            {
                puts( "Error: the queue is empty." );
            }
            
            break;
        }
        
        case 4:
        {
            display( &q );
            break;
        }           
        
        case 5:
        {
            break;
        }
        
        default:
        {
            puts( "Invalid Option" );
            break;
        }
        }       
    } while( option != 5 );

    return 0;
}

The program output might look like

Queue Operations
1. Insert
2. Delete
3. Peek
4. Display
5. Exit
Enter Option : 1
Enter Data : 1

Queue Operations
1. Insert
2. Delete
3. Peek
4. Display
5. Exit
Enter Option : 1
Enter Data : 2

Queue Operations
1. Insert
2. Delete
3. Peek
4. Display
5. Exit
Enter Option : q
Enter Data : 3

Queue Operations
1. Insert
2. Delete
3. Peek
4. Display
5. Exit
Enter Option : 4
1   2   3

Queue Operations
1. Insert
2. Delete
3. Peek
4. Display
5. Exit
Enter Option : 5

Pay attention to that you need also to write a function that will clear the queue that is that will free all the allocated memory in the queue.