queue array based implementation

Question

This is my program to implement queue using array. I am not getting the correct output when I am calling dequeue for the first time, but it is showing the correct output for the rest of the dequeue operations (again after showing some weird value).

The output for this program is as follows:

This is what I have tried:

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

struct queue {
  int capacity;
  int rear;
  int front;
  int *array;
};

struct queue* createqueue(int capacity)
{
  struct queue* nque = (struct queue*)malloc(sizeof(struct queue));
  nque->capacity = capacity;
  nque->front = -1;
  nque->rear = -1;
  nque->array = (int*)malloc(sizeof(int)*capacity);
  return nque;

}

int isempty(struct queue* amp)
{
  return(amp->front == -1 && amp->rear == -1);
}

int  isfull(struct queue* amp)
{
  return (((amp->rear) + 1) % (amp->capacity) == amp->front);

}

void enqueue(struct queue* amp, int x)
{
  if (isfull(amp))
    return;
  else if (isempty(amp))
  {
    amp->rear = 0;
    amp->front = 0;
  }
  else
  {
    amp->rear = (amp->rear + 1) % (amp->capacity);

  }
  amp->array[amp->rear] = x;
}

int dequeue(struct queue* amp)
{
  if (isempty(amp))
    return -1;
  else if (amp->front == amp->rear)
  {
    amp->front = -1;
    amp->rear = -1;
    return(amp->array[amp->front]);
  }
  else
  {
    amp->front = ((amp->front) + 1) % (amp->capacity);
    return(amp->array[amp->front]);
  }
}

int main() {
  struct queue* queue = createqueue(10);
  enqueue(queue, 12);
  enqueue(queue, 136);
  enqueue(queue, 14);
  enqueue(queue, 13);
  enqueue(queue, 16);

  printf("\n%d", dequeue(queue));
  printf("\n%d", dequeue(queue));
  printf("\n%d", dequeue(queue));

  printf("\n%d", dequeue(queue));
  printf("\n%d", dequeue(queue));
  printf("\n%d", dequeue(queue));
  printf("\n%d", dequeue(queue));
}

How to fix this issue?

If you program in C then please use only that language-tag.

Some programmer dude
– Some programmer dude

2018-08-15 13:11:18 +00:00
Commented Aug 15, 2018 at 13:11 — Some programmer dude
– Some programmer dude, Commented Aug 15, 2018 at 13:11
Do you know how to use debugger?

unalignedmemoryaccess
– unalignedmemoryaccess

2018-08-15 13:12:38 +00:00
Commented Aug 15, 2018 at 13:12 — unalignedmemoryaccess
– unalignedmemoryaccess, Commented Aug 15, 2018 at 13:12

Jabberwocky · Accepted Answer · 2018-08-15 13:26:13Z

Your dequeue contains bugs.

This is a corrected version:

int dequeue(struct queue* amp)
{
  if (isempty(amp))
    return -1;
  else if (amp->front == amp->rear)
  {
    int value = amp->array[amp->front];  // get value before modifying front
    amp->front = -1;
    amp->rear = -1;
    return value;
  }
  else
  {
    int value = amp->array[amp->front];  // get value before modifying front
    amp->front = ((amp->front) + 1) % (amp->capacity);
    return value;
  }
}

or more elegant:

int dequeue(struct queue* amp)
{
  int value;

  if (isempty(amp))
    return -1;
  else 
  {
    value = amp->array[amp->front];

    if (amp->front == amp->rear)
    {
      amp->front = -1;
      amp->rear = -1;
    }
    else
    {
      amp->front = ((amp->front) + 1) % (amp->capacity);
    }
  }

  return value;
}

or even more elegant:

int dequeue(struct queue* amp)
{
  int value = -1;

  if (!isempty(amp))
  {
    value = amp->array[amp->front];

    if (amp->front == amp->rear)
    {
      amp->front = -1;
      amp->rear = -1;
    }
    else
    {
      amp->front = ((amp->front) + 1) % (amp->capacity);
    }
  }

  return value;
}

Some programmer dude · Accepted Answer · 2018-08-15 13:14:56Z

Lets take a look at these lines from your dequeue function:

else if(amp->front==amp->rear)
{
  amp->front=-1;
  amp->rear=-1;
  return(amp->array[amp->front]);
}

If the condition is true, then you first assign the value -1 to amp->front. Then a couple of lines later you use amp->front (which is -1 remember?) as index into your array.

While using negative indexes is okay, because all array indexing really is simple pointer arithmetic, in this case it leads to the index being out of bounds which in turn leads to undefined behavior.

This could easily have been found with a very little amount of debugging your own code, so please attempt that first next time.

As for how to solve this, you should probably get and save the value of amp->array[amp->front] before you "reset" the front and rear members. Then return the saved value.

Collectives™ on Stack Overflow

queue array based implementation

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related