Last Updated on December 14, 2022 by Prepbytes
Circular Queue
It is a linear data structure that works on the principle of FIFO (First in First out). In this type of queue element can be added in any position or can be deleted from any position in the array but we have to maintain the pointers which will point towards the front and rear end of the queue. In this queue, the rear end can be at any point in the array.
Operations on Circular Queue
-
Front: This function returns the front item from the queue.
-
Rear: This function returns the last item from the queue.
-
Enqueue(item): This function is used to insert the item into the circular queue. In this type of queue, we always insert the new item at the Rear position.
- Create a new node and insert the value of the item in it.
- Check if front==NULL, if this condition is true then front = rear = (new node).
- If the above condition is false then rear = (new node) and rear node always contains the address of the front node.
-
Dequeue(): This function is used to remove the item from the circular queue. In this type of queue, the item present on the front position will be deleted.
- Check whether the queue is empty or not i.e. front == NULL.
- If the above condition is true then the display queue is empty.
- If the above condition is false then Check if (front == rear) if this condition is true then set front = rear = NULL else move the front pointer forward in the queue, update address of front in rear node and return the element.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* link;
};
struct Queue {
struct Node *front, *rear;
};
void enQueue(Queue* q, int value)
{
struct Node* temp = new Node;
temp->data = value;
if (q->front == NULL)
q->front = temp;
else
q->rear->link = temp;
q->rear = temp;
q->rear->link = q->front;
}
int deQueue(Queue* q)
{
if (q->front == NULL) {
printf("Queue is empty");
return INT_MIN;
}
int value;
if (q->front == q->rear) {
value = q->front->data;
free(q->front);
q->front = NULL;
q->rear = NULL;
}
else
{
struct Node* temp = q->front;
value = temp->data;
q->front = q->front->link;
q->rear->link = q->front;
free(temp);
}
return value;
}
void displayQueue(struct Queue* q)
{
struct Node* temp = q->front;
printf("\nElements in Circular Queue are: ");
while (temp->link != q->front) {
printf("%d ", temp->data);
temp = temp->link;
}
printf("%d", temp->data);
}
int main()
{
Queue* q = new Queue;
q->front = q->rear = NULL;
enQueue(q, 14);
enQueue(q, 24);
enQueue(q, 26);
displayQueue(q);
printf("\nDeleted value = %d", deQueue(q));
printf("\nDeleted value = %d", deQueue(q));
displayQueue(q);
enQueue(q, 9);
enQueue(q, 20);
displayQueue(q);
return 0;
}
import java.util.*;
class Solution {
static class Node {
int data;
Node link;
}
static class Queue {
Node front, rear;
}
static void enQueue(Queue q, int value)
{
Node temp = new Node();
temp.data = value;
if (q.front == null)
q.front = temp;
else
q.rear.link = temp;
q.rear = temp;
q.rear.link = q.front;
}
static int deQueue(Queue q)
{
if (q.front == null) {
System.out.printf("Queue is empty");
return Integer.MIN_VALUE;
}
int value;
if (q.front == q.rear) {
value = q.front.data;
q.front = null;
q.rear = null;
}
else
{
Node temp = q.front;
value = temp.data;
q.front = q.front.link;
q.rear.link = q.front;
}
return value;
}
static void displayQueue(Queue q)
{
Node temp = q.front;
System.out.printf("\nElements in Circular Queue are: ");
while (temp.link != q.front) {
System.out.printf("%d ", temp.data);
temp = temp.link;
}
System.out.printf("%d", temp.data);
}
public static void main(String args[])
{
Queue q = new Queue();
q.front = q.rear = null;
enQueue(q, 14);
enQueue(q, 24);
enQueue(q, 26);
displayQueue(q);
System.out.printf("\nDeleted value = %d", deQueue(q));
System.out.printf("\nDeleted value = %d", deQueue(q));
displayQueue(q);
enQueue(q, 9);
enQueue(q, 20);
displayQueue(q);
}
}
class Node:
def __init__(self):
self.data = None
self.link = None
class Queue:
def __init__(self):
front = None
rear = None
def enQueue(q, value):
temp = Node()
temp.data = value
if (q.front == None):
q.front = temp
else:
q.rear.link = temp
q.rear = temp
q.rear.link = q.front
def deQueue(q):
if (q.front == None):
print("Queue is empty")
return -999999999999
value = None
if (q.front == q.rear):
value = q.front.data
q.front = None
q.rear = None
else:
temp = q.front
value = temp.data
q.front = q.front.link
q.rear.link = q.front
return value
def displayQueue(q):
temp = q.front
print("Elements in Circular Queue are: ",
end = " ")
while (temp.link != q.front):
print(temp.data, end = " ")
temp = temp.link
print(temp.data)
if __name__ == '__main__':
q = Queue()
q.front = q.rear = None
enQueue(q, 14)
enQueue(q, 24)
enQueue(q, 26)
displayQueue(q)
print("Deleted value = ", deQueue(q))
print("Deleted value = ", deQueue(q))
displayQueue(q)
enQueue(q, 9)
enQueue(q, 20)
displayQueue(q)
Time Complexity: The time complexity of Enqueue() and Dequeue() functions will be O(1) as there is no loop in any of the functions.
Note: In case of linked list implementation, a queue is easily implemented without being circular. However, in case of array implementation, we need a circular queue for saving the space.
This article tried to discuss the concept of Circular Queue, Circular Linked List Implementation. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes