0

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!!

3
  • Question 1 says "when i press 3 to delete the front element" but 2 is the delete command, 3 is display. Is this an error in the description, or does it mean that if you delete until the queue is empty then you display you see a '5' that is leftover data? That would indicate another problem with the display loop. Aug 11, 2015 at 14:00
  • Yeah sorry. Fixed it!
    – RaviTej310
    Aug 11, 2015 at 14:01
  • The difficulty of telling apart a full queue and an empty queue reminds us of the fine line between genius and insanity.
    – Zhuoran He
    Oct 26, 2016 at 19:34

2 Answers 2

3

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;
}
2
  • Nice. The problem is partially fixed. But suppose i do this - Add the elements 1, 2, 3, 4, 5 to the queue and then delete 1 and 2. After this if i again insert 5 and 6, and display, the queue is printed infinitely again. How can i fix this?
    – RaviTej310
    Aug 11, 2015 at 14:45
  • I solved the problem in the above comment. Here: for (i = front; i != rear; i=(i+1)%capacity) cout << a[i] << endl; cout<<a[rear]<<endl;
    – RaviTej310
    Aug 11, 2015 at 15:16
1

A simpler implementation of a circular queue (for integers in this case) in C++ is:

CircularQueue.h:

class CircularQueue
{
public:
    CircularQueue(int n);
    ~CircularQueue();
    bool Empty();
    bool Full();
    void push(int i);
    bool front(int& i);
    void pop();
private:
    int N;
    int Capacity;
    int* buffer;
    int head;
    int tail;
};

CircularQueue.cpp:

#include "CircularQueue.h"

CircularQueue::CircularQueue(int n) : N(n) {
    Capacity = N + 1;
    buffer = new int[Capacity];
    head = 0;
    tail = 0;
}

CircularQueue::~CircularQueue()
{
    delete[] buffer;
}

bool CircularQueue::Empty()
{
    return head == tail;
}

bool CircularQueue::Full()
{
    return (head + 1) % Capacity == tail;
}

void CircularQueue::push(int i)
{
    if (!Full()) {
        buffer[head] = i;
        head = (head + 1) % Capacity;
    }
}

bool CircularQueue::front(int& i)
{
    if (!Empty()) {
        i = buffer[tail];
        return true;
    }
    else
        return false;
}

void CircularQueue::pop()
{
    if (!Empty())
        tail = (tail + 1) % Capacity;
}

Reference: http://www.drdobbs.com/thread-safe-circular-queue/184401814

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.