What is a circular queue?

A circular queue is an array-based queue in which the last position connects back to the first. When the rear reaches the end of the array, it wraps around to index 0 and reuses the slots freed by earlier dequeues.

How do the front and rear indexes wrap around?

Both move forward with the modulo operator, so after the last index they return to 0:

Write a circular queue in Java.

Java example: public class CircularQueue { private final int[] items; private int front = 0; private int size = 0; public CircularQueue(int capacity) { items = new int[capacity]; } public boolean enqueue(int value) { if (size == items.length) { return false; // full } items[(front + size) % items.length] = value; // rear position size++; return true; } public int dequeue() { if (size == 0) { throw new IllegalStateException("Queue is empty"); } int value = items[front]; front = (front + 1) % items.length; size--; return value; } public static void main(String[] args) { CircularQueue q = new Cir

How do you tell a full circular queue from an empty one?

In both cases front and rear can point to the same slot, so the indexes alone are not enough. Common solutions: Keep a size counter: empty when size is 0, full when size equals capacity. Leave one slot unused: full when (rear + 1) % capacity == front.

Why is a circular queue better than a simple array queue?

In a simple array queue, dequeued slots at the front are never reused, so the queue can report full while the array is mostly empty. A circular queue reuses those slots, so it uses the whole array, and every operation stays O(1) without shifting elements.

What is the time complexity of circular queue operations?

Enqueue, dequeue, peek, isEmpty and isFull are all O(1). The space is O(capacity), fixed when the queue is created.

Write a Java method that returns all elements of a circular queue in order.

Java example: import java.util.ArrayList; import java.util.List; static List toList(int[] items, int front, int size) { List result = new ArrayList<>(); for (int i = 0; i < size; i++) { result.add(items[(front + i) % items.length]); } return result; }

Where are circular queues used?

Keyboard and network buffers. Audio and video streaming buffers. CPU round-robin scheduling. Traffic light controllers that repeat a fixed cycle. Logging the most recent N events.

Does Java provide a circular queue?

ArrayDeque is implemented as a resizable circular array, so it gives you a circular queue that grows when full. ArrayBlockingQueue is a fixed-size circular buffer for multi-threaded code.

Write a Java class that keeps only the last N values using a circular buffer.

Java example: public class LastNBuffer { private final int[] items; private int next = 0; private int count = 0; public LastNBuffer(int capacity) { items = new int[capacity]; } public void add(int value) { items[next] = value; // overwrite the oldest value when full next = (next + 1) % items.length; count = Math.min(count + 1, items.length); } public double average() { long sum = 0; for (int i = 0; i < count; i++) { sum += items[i]; } return count == 0 ? 0 : (double) sum / count; } public static void main(String[] args) { LastNBuffer buffer = new LastNBuffer(3); for (int v : new int[]{10, 20,

Circular Queue Data Structure

Q: Where are circular queues used?

Keyboard and network buffers. Audio and video streaming buffers. CPU round-robin scheduling. Traffic light controllers that repeat a fixed cycle. Logging the most recent N events.

Q: Does Java provide a circular queue?

ArrayDeque is implemented as a resizable circular array, so it gives you a circular queue that grows when full. ArrayBlockingQueue is a fixed-size circular buffer for multi-threaded code.

Q: Write a Java class that keeps only the last N values using a circular buffer.

Java example: public class LastNBuffer { private final int[] items; private int next = 0; private int count = 0; public LastNBuffer(int capacity) { items = new int[capacity]; } public void add(int value) { items[next] = value; // overwrite the oldest value when full next = (next + 1) % items.length; count = Math.min(count + 1, items.length); } public double average() { long sum = 0; for (int i = 0; i < count; i++) { sum += items[i]; } return count == 0 ? 0 : (double) sum / count; } public static void main(String[] args) { LastNBuffer buffer = new LastNBuffer(3); for (int v : new int[]{10, 20,

A Queue is a linear data structure to store and manipulate the data elements. A queue follows the concept of "First in, First out" (FIFO), where the first element inserted into the queue is the first one to be deleted from the queue.

A queue is open at both ends which enables insert operations to be performed at one end called REAR or TAIL and delete operations to be performed at another end called FRONT or HEAD.

What is Circular Queue in Data Structure?

A Circular Queue is another type of queue; it also follows the principle of First in, First out" (FIFO). In the circular queue, the last element is connected to the first element of the queue, forming a circle.

A circular queue solves the major limitation of a normal queue. In a normal queue, once a queue is full, we cannot insert a new element, even if there is a space in front of the queue.

A circular queue allows us to keep on inserting an element; if it reaches the end of the queue, then again insert from the start. Such types of queues are very efficient and useful for tasks like buffering data in a computer system, managing waiting lists, and making sure no memory space is wasted.

Circular queue is also called Ring Buffer.

Circular Queue Representation

Operations on Circular Queue

There are the following operations can be performed on the circular queue.

Front: Access the front or first element from the queue.
Rear: Access the last or rear element from the Queue.
enQueue(value): Insert a new element in the queue. An insert operation always performed at the end (rear) of the queue.
deQueue(): Delete an element from the Queue. The deletion operation is always performed from the front of the queue.

Example: Circular Queue Implementation in Java

CircularQueue.java

// Java Program to implement a Circular Queue
public class CircularQueue {

  int queue_size;       // size of the queue
  int[] queueArray;     // Array to store the circular queue elements
  int front;            // Index of the front element
  int rear;             // Index of the rear element

  // Constructor
  public CircularQueue(int size) {
    queue_size = size;
    queueArray = new int[queue_size];
    // Initializing front and rear with -1
    front = -1;
    rear = -1;
  }

  // Method to enqueue (add) an element in circular queue
  void enqueue(int item) {
    if (isEmpty()) {
      front = 0;
      rear = 0;
      queueArray[rear] = item;
    } else {
      // Circular increment of rear index
      rear = (rear + 1) % queue_size;
      if (rear == front) {
        System.out.println("Queue is full so Enqueue is not possible.");

        // Reset rear to its previous value
        rear = (rear - 1 + queue_size) % queue_size;
      } else {
        queueArray[rear] = item;
      }
    }
  }

  // Method to Dequeue (remove) an element from the circular queue
  int dequeue() {
    int item = -1; // Assuming -1 represents an empty value

    if (!isEmpty()) {
      item = queueArray[front];
      if (front == rear) {
        // Reset front and rear to -1 to indicate an empty queue
        front = -1;
        rear = -1;
      } else {
        // Circular increment of front index
        front = (front + 1) % queue_size;
      }
    } else {
      System.out.println("Queue is empty so Dequeue is not possible.");
    }

    return item;
  }

  // Method to peek at the front element of the circular queue
  int peek() {
    if (!isEmpty()) {
      return queueArray[front];
    } else {
      System.out.println("Queue is empty");
      return -1; // Assuming -1 represents an empty value
    }
  }

  // Method to check circular queue is empty
  public boolean isEmpty() {
    return front == -1 && rear == -1;
  }

  public static void main(String[] args) {
    // Create a Circular Queue
    CircularQueue circularQueue = new CircularQueue(5);

    // Adding elements in the circular queue
    circularQueue.enqueue(50);
    circularQueue.enqueue(20);
    circularQueue.enqueue(60);
    circularQueue.enqueue(30);

    // Peek element from the circular queue
    System.out.println("Front element: " + circularQueue.peek());

    // Delete element from the circular queue
    System.out.println("Dequeue: " + circularQueue.dequeue());

    // Peek element after dequeue operation
    System.out.println("Peek after dequeue: " + circularQueue.peek());

    // Adding more elements in the circular queue
    circularQueue.enqueue(90);
    circularQueue.enqueue(66);
    circularQueue.enqueue(72);
  }
}

Output

Front element: 50
Dequeue: 50
Peek after dequeue: 20
Queue is full so Enqueue is not possible.

Applications of Circular Queue

CPU scheduling
Memory management
Traffic management

Circular queues provide a biggest advantages in terms of space utilization and can improve performance in certain scenarios. However, they have some limitations, such as fixed size and slightly more complex implementation.

Here are some list of advantages and disadvantages of Circular queue.

Advantages of Circular Queue

Effectively utilize the available array space.
Minimize memory wastage, especially when dealing with fixed-size buffers.
Improved Performance
No Need for Shifting Elements
Useful in situations where cyclical resource management is required.
Consistent Time Complexity O(1) for Enqueue and dequeue operations.
Implementation is simple and understandable.

Diadvantages of Circular Queue

Compare the linear queue, circular queue implementation is complexity.
Fixed size.
Potential for Underflow/Overflow.

Help Us Improve