DSASTQ - Editorial

editorial
1

Problem Link - Implement CircularQueue using Array

Problem Statement

You are tasked with implementing a circular queue using an array. A circular queue allows for efficient use of space by reusing the empty slots that are created when elements are dequeued. Your implementation should support the following operations:

  1. Enqueue: Add an element to the rear of the queue.

  2. Dequeue: Remove an element from the front of the queue.

  3. Display: Print all elements in the queue.

  4. Exit: Terminate the program.

Approach

  1. Full and Empty Checks:

    • isFull: The queue is full if front == (rear + 1) % capacity, meaning no space is left.

    • isEmpty: The queue is empty if front == -1, indicating no elements.

  2. Enqueue:

    • Check if the queue is full using isFull. If full, no element can be added.

    • If empty, set front and rear to 0.

    • Otherwise, increment rear circularly using (rear + 1) % capacity and insert the new value.

  3. Dequeue:

    • Check if the queue is empty using isEmpty. If empty, no element can be removed.

    • Retrieve the element at front, then increment front circularly using
      (front + 1) % capacity.

    • If the queue becomes empty (front == rear), reset front and rear to -1.

  4. Display:

    • If the queue is empty, print a message.

    • Otherwise, traverse and print the elements from front to rear circularly.

Time Complexity

  • Enqueue/Dequeue/Is Full/Is Empty: O(1) - Constant time operations.

  • Display: O(n) - Linear time to display all elements.

Space Complexity

  • O(capacity) - Linear space, as we use a fixed-size array to store elements.