Question

In: Computer Science

Why a circular queue is more benefiting than a single dimension array queue? How to do...

Why a circular queue is more benefiting than a single dimension array queue? How to do indexing in a circular queue? (In java)

Solutions

Expert Solution

Circular queue avoids the wastage of space in a regular queue implementation using arrays.

Limitation of the regular Queue

As you can see in the above image, after a bit of enqueuing and dequeuing, the size of the queue has been reduced.

The indexes 0 and 1 can only be used after the queue is reset when all the elements have been dequeued.

How Circular Queue Works

Circular Queue works by the process of circular increment i.e. when we try to increment the pointer and we reach the end of the queue, we start from the beginning of the queue.

Here, the circular increment is performed by modulo division with the queue size. That is,

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Circular queue representation

Circular Queue Operations

The circular queue work as follows:

  • two pointers FRONT and REAR
  • FRONT track the first element of the queue
  • REAR track the last elements of the queue
  • initially, set value of FRONT and REAR to -1

1. Enqueue Operation

  • check if the queue is full
  • for the first element, set value of FRONT to 0
  • circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue)
  • add the new element in the position pointed to by REAR

2. Dequeue Operation

  • check if the queue is empty
  • return the value pointed by FRONT
  • circularly increase the FRONT index by 1
  • for the last element, reset the values of FRONT and REAR to -1

However, the check for full queue has a new additional case:

  • Case 1: FRONT = 0 && REAR == SIZE - 1
  • Case 2: FRONT = REAR + 1

The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.

Enque and Deque Operations

// Circular Queue implementation in Java

public class CQueue {
  int SIZE = 5; // Size of Circular Queue
  int front, rear;
  int items[] = new int[SIZE];

  CQueue() {
    front = -1;
    rear = -1;
  }

  // Check if the queue is full
  boolean isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    if (front == rear + 1) {
      return true;
    }
    return false;
  }

  // Check if the queue is empty
  boolean isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  // Adding an element
  void enQueue(int element) {
    if (isFull()) {
      System.out.println("Queue is full");
    } else {
      if (front == -1)
        front = 0;
      rear = (rear + 1) % SIZE;
      items[rear] = element;
      System.out.println("Inserted " + element);
    }
  }

  // Removing an element
  int deQueue() {
    int element;
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return (-1);
    } else {
      element = items[front];
      if (front == rear) {
        front = -1;
        rear = -1;
      } /* Q has only one element, so we reset the queue after deleting it. */
      else {
        front = (front + 1) % SIZE;
      }
      return (element);
    }
  }

  void display() {
    /* Function to display status of Circular Queue */
    int i;
    if (isEmpty()) {
      System.out.println("Empty Queue");
    } else {
      System.out.println("Front -> " + front);
      System.out.println("Items -> ");
      for (i = front; i != rear; i = (i + 1) % SIZE)
        System.out.print(items[i] + " ");
      System.out.println(items[i]);
      System.out.println("Rear -> " + rear);
    }
  }

  public static void main(String[] args) {

    CQueue q = new CQueue();

    // Fails because front = -1
    q.deQueue();

    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);

    // Fails to enqueue because front == 0 && rear == SIZE - 1
    q.enQueue(6);

    q.display();

    int elem = q.deQueue();

    if (elem != -1) {
      System.out.println("Deleted Element is " + elem);
    }
    q.display();

    q.enQueue(7);

    q.display();

    // Fails to enqueue because front == rear + 1
    q.enQueue(8);
  }

}

Circular Queue Complexity Analysis

The complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array implementations).


Related Solutions

Why a circular queue is more benefiting than a single dimension array queue? How to do...
Why a circular queue is more benefiting than a single dimension array queue? How to do indexing in a circular queue? (explain briefly in java)
Implementation of a a queue with a "circular" array or a "regular" array. (a) "circular" array:...
Implementation of a a queue with a "circular" array or a "regular" array. (a) "circular" array: consider using the smallest number of fields/variables in a struct/class. List the fields/variables that support the enqueue and dequeue operations in O(1) time in the worst case. Explain why the list is the smallest and the two operations are O(1) time. (b) "regular" array: explain the worst-case time complexity in big-O for the operations (queue size is at most n).
Describe how Java creates a single dimension array and a double dimension array. Describe and explain...
Describe how Java creates a single dimension array and a double dimension array. Describe and explain how Java processes the contents of a single dimension array. Describe and explain how Java saves values to a single dimension array, and to a double dimension array.
JAVA: Implement a Queue ADT using a circular array with 5 string elements. Create a Queue...
JAVA: Implement a Queue ADT using a circular array with 5 string elements. Create a Queue object and try various operations below. Queue myQueue = new Queue(); myQueue.enqueue(“CPS 123”); myQueue.enqueue(“CPS 223”); myQueue.enqueue(“CPS 323”); myQueue.dequeue(); myQueue.enqueue(“CPS 113”); myQueue.enqueue(“CPS 153”); string course = myQueue.front(); // course should be CPS 223 size = myQueue.size(); // size should be 4 // output course and size
Explain how do you do indexing in a circular queue? (java programing)
Explain how do you do indexing in a circular queue? (java programing)
Show how circular linked list can be useful to implement Circular Queue (CQ) ADT (Abstract Data...
Show how circular linked list can be useful to implement Circular Queue (CQ) ADT (Abstract Data Type). Compare and contrast with array based implementation. Which one would you recommend to implement CQ and why
Do you consider political dimension to have a greater impact than economic dimension to organizational change?
Do you consider political dimension to have a greater impact than economic dimension to organizational change?
Discussion Why is migration more difficult to measure than fertility and mortality? How do changes in...
Discussion Why is migration more difficult to measure than fertility and mortality? How do changes in fertility, mortality, and migration affect population composition?
Why do some people crave drugs more than others?
Why do some people crave drugs more than others?
how a single gene can result in more than one RNA product? and What is the...
how a single gene can result in more than one RNA product? and What is the GU-AG rule and how does it contribute to this process?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT