Which Data Structure May Produce an Overflow Error?

Overflow error is an error that happens when a program receives a number, value or variable outside the scope of its ability to handle.

Takeaways

A linear queue can throw an Overflow error even if it has empty spaces for elements in it.

Which Data Structure May Produce an Overflow Error?

•  Linear Queue
•  Circular Queue
•  Stack
•  None of these

Correct Answer

a. A Linear Queue can produce an overflow error, even if its number of elements is less than its size.

Explanation

A Linear Queue implemented using a static array can throw an overflow error even if its number of elements is less than its size.

A Linear Queue is a linear data structure that works with the First In First Out (FIFO) approach, i.e., the first element to enter the queue will leave be the first element to leave the queue. The front of a linear queue is the end from which elements are dequeued from the queue, whereas the rear of a linear queue is the end from which new elements are enqueued into the queue.

The best way to understand how a linear queue can throw an Overflow Error even though it has empty spaces is to look at an example.

Example:

Let’s take a linear queue of size 4. At the start of the program, the front will be at -1 and the rear will be at 0, the rear will increase by one upon enqueueing an element into the queue, and the front will increase by one upon dequeueing an element from the queue.

Suppose we enqueue 4 elements into the queue, now that the queue is full, the rear will be 3 and the front will still be -1. After dequeuing an element from the queue, the front will become 0.

As of now, the queue has 3 elements, the rear is at 3 (maximum value of rear), and the front is 0. Even though the queue has an empty space, the rear cannot be incremented as it is maximum due to which we cannot enqueue any more elements into the queue.

Example of Overflow Error in Linear Queue

Code in C++17:

#include <iostream>
using std::cin;
using std::cout;

#define N 4 // Size of the Queue

int front = -1, rear = -1;
int queue[N];

// Function Prototypes
void Enqueue();
void Dequeue();
void Display();

// Driver code
int main()
{
    cout<<"Size of the Queue: 3 \n \n";
    int choice;

    cout << "1) Insert element to queue" << endl;
    cout << "2) Delete element from queue" << endl;
    cout << "3) Display all the elements of queue" << endl;
    cout << "4) Exit the program" << endl;
    do
    {
        cout << "Enter your choice : " << endl;
        cin >> choice;
        switch (choice)
        {
        case 1:
            Enqueue();
            break;
        case 2:
            Dequeue();
            break;
        case 3:
            Display();
            break;
        case 4:
            cout << "Exit" << endl;
            break;
        default:
            cout << "Invalid choice" << endl;
        }
    } while (choice != 4);

    return 0;
}

// Function to insert an element into the Queue
void Enqueue()
{
    int val;
    
    // If rear is equal to "Size of Queue - 1", then rear cannot be incremented as it is already maximum
    if (rear == N - 1)
        cout << "Overflow Error - Not enough space" << endl;
    else
    {
        if (front == -1)
            front = 0;
        cout << "Insert the element in queue : " << endl;
        cin >> val;
        rear++;
        queue[rear] = val;
    }
}

// Function to delete an element from the Queue
void Dequeue()
{
    // If front is equal to -1 or less than rear, there is no element to delete from the queue
    if (front == -1 || front > rear)
    {
        cout << "Queue Underflow - no elements in queue to delete";
        return;
    }
    else
    {
        cout << "Element deleted from queue is : " << queue[front] << endl;
        front++;
        ;
    }
}

// Function to display the elements of the Queue
void Display()
{
    // If front is equal to -1, then that means the queue is empty
    if (front == -1)
        cout << "Queue is empty" << endl;
    else
    {
        cout << "Queue elements are : ";
        for (int i = front; i <= rear; i++)
            cout << queue[i] << " ";
        cout << endl;
    }
}

Output

Size of the Queue: 4

1) Insert element to queue
2) Delete element from queue
3) Display all the elements of queue
4) Exit
Enter your choice : 
1
Insert the element in queue : 
10                                   // Queue: 10 <- __ <- __ <- __
Enter your choice : 
1
Insert the element in queue : 
20                                   // Queue: 10 <- 20 <- __ <- __
Enter your choice : 
1
Insert the element in queue : 
30                                   // Queue: 10 <- 20 <- 30 <- __
Enter your choice : 
1
Insert the element in queue : 
40                                   // Queue: 10 <- 20 <- 30 <- 40
Enter your choice : 
1
Overflow Error - Not enough space
Enter your choice : 
2
Element deleted from queue is : 10   // Queue: __ <- 20 <- 30 <- 40
Enter your choice : 
1
Overflow Error - Not enough space
Enter your choice : 

In the above example, we have implemented a Linear Queue of Size 4 in C++. To demonstrate that a linear queue can throw an Overflow Error even if it has empty spaces,

1. We have first inserted elements into the queue till it’s full.
2. Then we have removed an element, which means that the queue now has an empty space.
3. Even though the queue has an empty space, we still cannot insert an element into the queue as the rear is 3 (maximum for a Queue of size 4).
4. Trying to insert an element into the queue throws the Overflow Error as the rear is maximum.

Difference between Linear Queue and Circular Queue

This Overflow Error problem in Linear Queue, even though the queue is not full can be overcome using a Circular Queue.

A Circular Queue is similar to Linear Queue except for the fact that its last element is connected to its first element, i.e., we can go from the last element to the first element directly in a Circular Queue.
In this way, we can utilize the empty spaces of the front which was impossible in a Linear Queue. This is why we can use a circular queue to avoid getting Overflow Error

Let us look at some more differences between Linear Queue and Circular Queue:

Conclusion

• The rear of a linear queue can be n-1 at maximum (if the size of the queue is n).
• A circular queue’s last element is connected to its first element which helps in utilizing empty spaces of the front after removing element(s) from it.
• We can use a circular queue instead of a linear queue to avoid Overflow Errors.