Operating System Process Scheduler PCBS and Queueing

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.
1. Create a new node and insert the value of the item in it.
2. Check if front==NULL, if this condition is true then front = rear = (new node).
3. 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.
1. Check whether the queue is empty or not i.e. front == NULL.
2. If the above condition is true then the display queue is empty.
3. 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));

displayQueue(q);

enQueue(q, 9);

enQueue(q, 20);

displayQueue(q);

return 0;

}

#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; }

#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));

displayQueue(q);

enQueue(q, 9);

enQueue(q, 20);

displayQueue(q);

}

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); } }

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))

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)

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

Circular Queue | Set 2 (Circular Linked List Implementation)

Circular Queue

Operations on Circular Queue

Leave a Reply Cancel reply

Integrated Services Digital Network (ISDN)

VLAN ACL (VACL) in Computer Networks

Inter-VLAN Routing Using a Layer 3 Switch

Access and Trunk Ports in Computer Networks

Role-Based Access Control (RBAC) in Computer Networks

Display Processor in Computer Graphics

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

Circular Queue

Operations on Circular Queue

Leave a Reply Cancel reply