QUEUE11 - Editorial

editorial
, ,
1

Problem Link - Enqueue and Dequeue Functions

Problem Statement:

Enqueue(int item) Function:

  • Adds an element to the rear of the queue.
  • If the queue is full, it prints an error message and does not enqueue the element.
  • Otherwise, it circularly increments the rear index, assigns the item to the updated rear index, and increments currentSize.

Dequeue() Function:

  • Removes an element from the front of the circular queue.
  • If the queue is empty, it prints an error message and returns a sentinel value (-1 in this case, which can be considered as an error value).
  • Otherwise, it retrieves the item at the front index, circularly increments the front index, decrements currentSize, and returns the removed item.

Approach:

The key idea is to use an array to store elements and manage the front and rear indices effectively, enabling a circular structure. Here’s how it works:

  • Initialization: We create an array a of size maxSize and initialize front, rear, and currentSize to track the queue’s state.

  • Check if Empty or Full:

    • isEmpty() returns true if currentSize is 0.

    • isFull() checks if currentSize equals maxSize.

  • Enqueue Operation: In enqueue(int item), we check if the queue is full. If not, we update the rear index with (rear + 1) % maxSize, add the item, and increment currentSize.

  • Dequeue Operation: In dequeue(), we check if the queue is empty. If not, we save and return the item at the front, then update the front index with (front + 1) % maxSize and decrement currentSize.

By managing the front and rear indices this way, the circular queue efficiently uses the array space and maintains the FIFO (First In, First Out) order of elements.

Time Complexity:

Both the enqueue and dequeue operations have a time complexity of O(1) since they involve simple index updates.

Space Complexity:

The space complexity is O(maxSize) due to the storage allocated for the array.