CircularQueue.
md 2025-12-22
To implement a circular queue that can handle multiple queries for enqueueing and dequeueing elements,
we need to design a class that maintains the necessary properties of a queue while allowing for efficient
operations. A circular queue wraps around when it reaches the end, making it efficient in terms of space
and time.
Problem Explanation
. Queries:
Enqueue (X): Add element X to the end of the queue. If successful, return true; otherwise,
return false.
Dequeue: Remove and return the element at the front of the queue. If the queue is empty,
return -1.
. Structure:
We can implement the circular queue using an array and maintain two pointers: front and
rear to track the start and end of the queue.
Circular Queue Implementation in Java
Here's a simple implementation of a circular queue:
class CircularQueue {
private int[] queue; // Array to store the elements of the queue
private int front; // Front pointer
private int rear; // Rear pointer
private int size; // Current number of elements in the queue
private int capacity; // Maximum capacity of the queue
// Constructor to initialize the circular queue
public CircularQueue(int capacity) {
[Link] = capacity;
queue = new int[capacity];
front = 0;
rear = 0;
size = 0;
}
// Enqueue operation
public boolean enqueue(int x) {
if (size == capacity) { // Check if the queue is full
return false;
}
queue[rear] = x; // Add the element at the rear
rear = (rear + 1) % capacity; // Move rear pointer to the next
position
size++; // Increment the size
return true;
}
1/3
[Link] 2025-12-22
// Dequeue operation
public int dequeue() {
if (size == 0) { // Check if the queue is empty
return -1;
}
int dequeuedElement = queue[front]; // Get the front element
front = (front + 1) % capacity; // Move front pointer to the next
position
size--; // Decrement the size
return dequeuedElement;
}
// Method to get the current size of the queue
public int getSize() {
return size;
}
// Method to check if the queue is empty
public boolean isEmpty() {
return size == 0;
}
// Method to check if the queue is full
public boolean isFull() {
return size == capacity;
}
}
public class Main {
public static void main(String[] args) {
CircularQueue queue = new CircularQueue(5); // Create a circular
queue of capacity 5
// Sample queries
[Link]([Link](10)); // Output: true
[Link]([Link](20)); // Output: true
[Link]([Link](30)); // Output: true
[Link]([Link](40)); // Output: true
[Link]([Link](50)); // Output: true
[Link]([Link](60)); // Output: false (Queue is
full)
[Link]([Link]()); // Output: 10
[Link]([Link]()); // Output: 20
[Link]([Link](60)); // Output: true (Added
after dequeuing)
[Link]([Link]()); // Output: 30
[Link]([Link]()); // Output: 40
[Link]([Link]()); // Output: 50
[Link]([Link]()); // Output: -1 (Queue is
empty)
}
}
2/3
[Link] 2025-12-22
Explanation of the Code
. Data Members:
queue: An array that holds the elements of the circular queue.
front: Points to the front of the queue.
rear: Points to the next position for insertion.
size: Tracks the current number of elements in the queue.
capacity: The maximum number of elements the queue can hold.
. Enqueue Method:
Checks if the queue is full. If so, it returns false.
Adds the element to the rear and adjusts the rear pointer using modulo to wrap around.
. Dequeue Method:
Checks if the queue is empty. If so, it returns -1.
Removes the element from the front and adjusts the front pointer similarly.
. Main Method:
Demonstrates the enqueue and dequeue operations with sample queries.
Complexity Analysis
Time Complexity:
Enqueue: (O(1)) - Constant time for adding an element.
Dequeue: (O(1)) - Constant time for removing an element.
Space Complexity:
(O(N)) - Where (N) is the capacity of the queue, as we use an array of size capacity.
Conclusion
This implementation of a circular queue efficiently handles enqueue and dequeue operations while ensuring
that it wraps around when reaching the end of the array. The code is straightforward and can be expanded
or modified based on specific requirements or additional functionalities.
3/3