The post shows you about Circular Queue Data Structure in Java and how to implement Circular Queue Data Structure in Java. Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.
Circular queue saves the space more than a normal queue implementation using arrays. In normal queue , once queue becomes full, we can not insert the next element even if there is a space in front of queue.
How Circular Queue Works
Circular Queue works by the process of circular increment i.e. when we try to increment any variable and we reach the end of queue, we start from the beginning of queue by modulo division with the queue size.
Queue operations work as follows:
- Two pointers called FRONT and REAR are used to keep track of the first and last elements in the queue.
- When initializing the queue, we set the value of FRONT and REAR to -1.
- Enqueue an element, we circularly increase the value of REAR index and place the new element in the position pointed to by REAR. Before enqueing, we check if queue is already full.
- Dequeue an element, we return the value pointed to by FRONT and circularly increase he FRONT index. Before dequeuing, we check if queue is already empty.
- When enqueing the first element, we set the value of FRONT to 0.
- When dequeing the last element, we reset the values of FRONT and REAR to -1.
Implement Circular Queue Data Structure in Java using array.
The most common queue implementation is using arrays, but it can also be implemented using lists, eg: ArrayList, LinkedList.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
//A programm implements Circular Queue using array class CircularQueue { int size; int rear; int front; int qArray[]; CircularQueue(int size) { this.size = size; this.qArray = new int[size]; this.rear = -1; this.front = -1; } void enQueue(int item) { if (((rear + 1) % size) == front) { System.out.println("Queue is full"); } else { if (rear == front && front == -1) { front = 0; } rear = (rear + 1) % size; qArray[rear] = item; } } void deQueue() { if (rear == front && rear == -1) { System.out.println("Queue is empty."); } else { int item = qArray[front]; qArray[front] = 0;//reset data if (rear == front) {//Queue is empty rear = -1; front = -1; } else { front = (front + 1) % size; } System.out.println(item + " is dequeued from the Queue"); } } public String toString(){ StringBuffer buf = new StringBuffer(); for (int item: qArray){ if (item !=0){ buf.append(item); buf.append(","); } } return buf.toString(); } // Display the queue void display() { int tmpfront = front; if (rear == front && rear == -1) { System.out.println("Queue is empty."); } else { System.out.println(toString()); } } public static void main(String[] args) { int size = 3; CircularQueue queue = new CircularQueue(size); queue.enQueue(5); queue.display(); queue.enQueue(10); queue.display(); queue.enQueue(20); queue.display(); queue.enQueue(40); queue.display(); queue.deQueue(); queue.display(); } } |
Here is output of the above program
Time Complexity: Time complexity of enQueue(), deQueue() operation is O(1) time because there is no loop in any of the operations.
Use of Circular Queue
- Memory Management: The unused memory locations in the case of normal queues can be utilized in circular queues. It saves spaces.
- Traffic system: Circular queues are used to switch on the traffic lights one by one repeatedly as per the time set in the traffic system.
- CPU Scheduling: Operating systems (e.g: Windows, Linux) often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.
That’s all about Circular Queue Data Structure in Java.
References
Queue Data Structure in Java
Data Structures and Algorithms Tutorial in Java
