RaviTej310 RaviTej310 - 1 month ago 6
C++ Question

Circular implementation of queue data structure using C++

I have written the following C++ code to implement a queue data structure. However, i have two problems:


  1. Whenever i delete the front element, it works fine. However, when i press 2 to delete the front element even when the queue is empty, i get a message saying
    "Queue empty" followed by a 5 on the next line. How can i prevent the 5 from appearing and why is it coming?

  2. When i completely fill the queue and want to display the contents, the queue is being printed infinitely without stopping. I think there is something wrong in the for loop in the display function. When the queue is not full, the display function works fine. How can i fix this?



My code:

#include<iostream>
using namespace std;
int data;
class queue {

private:
int front,rear,capacity,a[100];

public:
queue(int n)
{
rear=front=-1;
capacity=n;
}

void enqueue(int n)
{
if(front==-1)
{
front++;
rear=front;
a[front]=n;
return;
}
if(rear%capacity==(front-1)%capacity)
{
cout<<"Queue is full\n";
return;
}
rear=(rear+1)%capacity;
a[rear]=n;

}

int dequeue()
{
if(front==rear&&front==-1)
{
cout<<"Queue is empty";
return 0;
}
if(front==rear&&front!=-1)
{
data=a[front];
front=rear=-1;
return data;
}

data=a[front];
front=(front+1)%capacity;
return data;
}

void display()
{
int i;
for(i=front;i!=rear+1;i=(i+1)%capacity)
cout<<a[i]<<endl;
}

};

main()
{
int x,y,c;
cout<<"Enter capacity\n";
cin>>c;
queue q(c);

while(1)
{
cout<<"Select option 1.insert 2.delete 3.display 4.exit\n";
cin>>x;
switch(x)
{
case 1: cout<<"Enter the element\n";
cin>>y;
q.enqueue(y);
break;
case 2: q.dequeue();
break;
case 3: q.display();
break;
case 4: exit(0);
}
}
return 0;
}


Thanks!!

Answer

1.Display of empty queue

The deletion of elements even in the empty queue works well. However the display of the empty queue has a problem:

When the queue is empty, front and rear are both -1.

The for loop starts with i=front so i is -1

The condition is i != rear + 1; , which is true the first time (as -1 != 0), so the loop executes one time printing a[-1], which is undefined behaviour. THerefore a garbage output.

2.Filled queue

When the queue is full, front is 0 and rear is capactity-1.

So you start your for loop with i being 0, you then loop and print out every element. The last element being with i being rear which is capacity-1

When iterating one step further, you do i = (i + 1) % capacity With the current value of i, this is equivalent to i= (capacity-1 + 1)% capacity which will be 0 and here you start looping again !

With your increment, you'll never reach an end of loop condition.

How to fix it ?

Here a working version

void display()
{
    int i;
    if (front == -1)  // This is a special case
        cout << "No elements" <<endl;
    else              // now the general case: do the module in the loop body (i.e. uppon increment and success
        for (i = front; i != rear + 1; i++) 
            cout << a[i% capacity] << endl;
}