cstructcircular-queue

Front and rear pointers of circular queue exceed the size of array


front and rear pointers of circular queue are exceeding the size of array which can be seen in the print statement the input given for size was 3 where pointers go till the value 4 and 6.It would be helpful if someone could point out where I am going wrong. The input on which I tested was 20 (size of number ), 3(size of queue) ,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 (numbers) . output should be page fault - 15 and hit - 5 but it was 9 and 11.

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

struct queue{
    int size;
    int f;
    int r;
    int *arr;
};

int isEmpty(struct queue *q)
{
    if(q->f == -1 || q->r == -1)
    {
        return 1;
    }
    return 0;  
}

int isFull(struct queue *q)
{
    if(q->r == q->f-1 || (q->f == 0 && q->r == q->size - 1))
    {
        return 1;
    }
    return 0;  
}

void enqueue(struct queue *q ,int data)
{
    // if(isFull(q))
    // {
    //     printf("Queue Overflow\n");
    //     return;
    // }
    if(isEmpty(q))
    {
        q->f=0;
        q->r=0;
    }
    else if(q->r == q->size-1 && q->f !=0)
    {
        q->r = 0;
    }
    else
    {
        q->r = q->r + 1;
    }
    q->arr[q->r] = data;
    // printf("%d\n",q->arr[q->r]);
}

void dequeue(struct queue *q)
{
    // int val = -1;

    // if(isEmpty(q))
    // {
    //     printf("Queue Underflow\n");
    //     return val;
    // }

    // val = q->arr[q->f];

    if(q->r == q->f)
    {
        q->f = -1;
        q->r = -1;
    }
    else if(q->f == q->size-1)
    {
        q->f = 0;
    }
    else
    {        
        q->f = q->f + 1;
    }    
    // return val;
}

int isPresent(struct queue *q ,int data)
{
    for(int i=q->f;i!=q->r;i++)
    {
        if(i == q->size-1)
        {
            if(data == q->arr[i])
            {
                return 1;
            }
            i = -1;
            continue;
        }
        if(data == q->arr[i])
        {
            return 1;
        }
    }
    if(data == q->arr[q->r])
    {
        return 1;
    }

    return 0;
}

int main(void)
{
    int m,n;
    int hit=0,miss=0;
    struct queue *q;
    q->f = -1;
    q->r = -1;

    printf("Enter the amount of numbers:\n");
    scanf("%d",&n);
 
    printf("Enter the Frame no.:\n");
    scanf("%d",&m);
    
    int num[n];
    q->size = m;
    q->arr = (int *)malloc(q->size*sizeof(int));
    
    
    printf("Enter the numbers:\n");
    for(int i=0;i<n;i++)
    {
        scanf("%d",&num[i]);
    }
    
    
    for(int i=0;i<n;i++)
    {
        printf("\n%d\n",q->f);
        printf("%d\n",q->r);
        if(!isFull(q))
        {
            enqueue(q,num[i]);
            // miss++;
        }
        else if(isPresent(q,num[i]))
        {
            hit++;
        }
        else
        {
            dequeue(q);
            enqueue(q,num[i]);
            miss++;
        }
    }

    printf("Page Fault:%d\n",miss);
    printf("Hit:%d\n",hit);
    return 0;
}

Solution

  • Compiling the code in the question with warnings enabled reveals that q is used uninitialized in line 113, q->f = -1;. In the prior line, struct queue *q;, q is defined but not given any value. Because of this, the behavior of the program is not defined by the C standard, and there is no reason the “output should be page fault.“

    You must initialize q by setting it to point to suitable memory, perhaps allocated with malloc, or otherwise redesign your program so that q is not used before it is initialized.

    Enable warnings in your compiler and elevate warnings to errors. With Clang, start with -Wmost -Werror. With GCC, start with -Wall -Werror. With MSVC, start with /W3 /WX.