Which Data Structure May Produce an Overflow Error?

Overview

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:

Output

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,

We have first inserted elements into the queue till it's full.
Then we have removed an element, which means that the queue now has an empty space.
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).
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:

Linear Queue	Circular Queue
A linear queue contains elements sequentially.	A circular queue contains elements sequentially in which the last element of the queue is connected to its first element.
In a linear queue, insertion is done from the rear and deletion from the front only.	In a circular queue, we can insert and delete elements from either front or rear.
It requires more memory space.	It requires less memory space.
The usage of memory is inefficient in a linear queue.	Circular queue utilizes memory efficiently.

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.