Applications of Queue in Data Structure

Queue

A queue is basically a linear data structure that works on the principle of FIFO (First in First out) which means an element that is enqueued first will be dequeued first. Element is enqueued from the rear end of the queue and dequeued from the front end. The insertion operation in the queue is known as enqueue and the deletion operation in the queue is known as dequeue.

The queue is used when the operations are to be performed in the manner of First in First out order just like Breadth-First Search.

For example, there is a line of people in front of the counter in the bank. They will visit the counter by following the queue property i.e. the person who is standing in front will visit the counter first.

Basic Operations of Queue:

  • Enqueue: This function is used to add an element to the rear end of the queue. If the queue is completely filled, then it will be in an overflow condition. The time complexity of the enqueue is O(1).
  • Dequeue: This function is used to remove an element from the front end of the queue. If the queue is empty, then it will be in an underflow condition. The time complexity of the dequeue is O(1).
  • Front: This function returns the front element of the queue. The time complexity of this function is O(1).
  • Rear: This function returns the last element of the queue. The time complexity of this function is O(1).
  • Peek(): This operation is used to get the value of the element from the front of the queue.

Here are some scenarios for the usage of Queue:

  1. When any resource is shared among multiple consumers. Then the process of using the resource is done using the queue. For example, CPU scheduling, Disk scheduling etc.
  2. The queue is used in the implementation of various other data structures deque, priority queue, doubly ended priority queue.
  3. In networks, there are mail queues and queues in routers/switches.
  4. In operating systems, queues are used in
    • Semaphores
    • Spooling in printers
    • FCFS (First come First serve) scheduling, example: FIFO queue
    • Buffer for devices like keyboards.
  5. In the case of transferring the data asynchronously (i.e. it is not necessary to receive and send the data at the same rate) between two processes. For example, IO Buffers, pipes, file IO, etc.

Some other applications of queue data structure:

  • Applied as buffers on playing music in the mp3 players or CD players.
  • Applied on handling the interruption in the operating system.
  • Applied to add a song at the end of the playlist.
  • Applied as the waiting queue for using the single shared resources like CPU, Printers, or Disk.
  • Applied to the chat application when someone sends messages to us and we don’t have an internet connection then the messages are stored in the server of the chat application.

Types of queues:

  • Simple Queue: In a Simple queue, insertion of the element takes place at the rear end i.e. ENQUEUE, and removal of the element takes place at the front end i.e. DEQUEUE. The simple queue is also called a linear queue.
  • Circular Queue: In a circular queue, the elements act like circular rings. The working of a circular queue is similar to a simple queue but in a circular queue, the element in the last position is connected to the element in the first position. The main advantage of a circular queue is that the memory will be utilized in a better way.
  • Priority Queue: In a priority queue, the elements are stored according to their priority, Based on the priority of elements we’ll set our queue accordingly i.e. in ascending order or in descending order.
  • Dequeue: Dequeue is known as a double-ended queue. In dequeue, the elements can be inserted or removed from both ends.Due to this property, the dequeue may not follow the first in first out property.

Queue implementation using Array:

For the implementation of queue, we need to initialize two pointers i.e. front and rear, we insert an element from the rear and remove the element from the front, and if we increment the rear and front pointers we may occur error, Due to this, the front pointer may reach the end.
The solution to the above problem is to increase the front and rear pointers in a circular manner.

Enqueue Operation / Insertion:

  • First, check if the queue is full or not.
  • For the first element, set the FRONT pointer to 0.
  • Increment the REAR index by 1.
  • Add the new element in the position which was pointed by REAR.

Dequeue Operation / Remove:

  • First, check if the queue is empty or not.
  • Return the value which was pointed by FRONT.
  • Increment the FRONT index by 1.
  • For the last element, reset the values of FRONT and REAR to -1.
#include 
#include 
#include 
 
struct Queue {
	int front, rear, size;
	unsigned capacity;
	int* array;
};
struct Queue* createQueue(unsigned capacity)
{
	struct Queue* queue = (struct Queue*)malloc(
		sizeof(struct Queue));
	queue->capacity = capacity;
	queue->front = queue->size = 0;
 
 
	queue->rear = capacity - 1;
	queue->array = (int*)malloc(
		queue->capacity * sizeof(int));
	return queue;
}
 
int isFull(struct Queue* queue)
{
	return (queue->size == queue->capacity);
}
 
int isEmpty(struct Queue* queue)
{
	return (queue->size == 0);
}
 
void enqueue(struct Queue* queue, int item)
{
	if (isFull(queue))
		return;
	queue->rear = (queue->rear + 1)
				% queue->capacity;
	queue->array[queue->rear] = item;
	queue->size = queue->size + 1;
	printf("%d enqueued to queue\n", item);
}
 
int dequeue(struct Queue* queue)
{
	if (isEmpty(queue))
		return INT_MIN;
	int item = queue->array[queue->front];
	queue->front = (queue->front + 1)
				% queue->capacity;
	queue->size = queue->size - 1;
	return item;
}
 
int front(struct Queue* queue)
{
	if (isEmpty(queue))
		return INT_MIN;
	return queue->array[queue->front];
}
 
int rear(struct Queue* queue)
{
	if (isEmpty(queue))
		return INT_MIN;
	return queue->array[queue->rear];
}
 
int main()
{
	struct Queue* queue = createQueue(1000);
 
	enqueue(queue, 1);
	enqueue(queue, 2);
	enqueue(queue, 3);
	enqueue(queue, 4);
 
	printf("%d dequeued from queue\n\n",
		dequeue(queue));
 
	printf("Front item is %d\n", front(queue));
	printf("Rear item is %d\n", rear(queue));
 
	return 0;
}


#include <bits/stdc++.h>
using namespace std;


class Queue {
public:
	int front, rear, size;
	unsigned capacity;
	int* array;
};

Queue* createQueue(unsigned capacity)
{
	Queue* queue = new Queue();
	queue->capacity = capacity;
	queue->front = queue->size = 0;

	queue->rear = capacity - 1;
	queue->array = new int[queue->capacity];
	return queue;
}

int isFull(Queue* queue)
{
	return (queue->size == queue->capacity);
}

int isEmpty(Queue* queue)
{
	return (queue->size == 0);
}

void enqueue(Queue* queue, int item)
{
	if (isFull(queue))
		return;
	queue->rear = (queue->rear + 1)
				% queue->capacity;
	queue->array[queue->rear] = item;
	queue->size = queue->size + 1;
	cout << item << " enqueued to queue\n";
}

int dequeue(Queue* queue)
{
	if (isEmpty(queue))
		return INT_MIN;
	int item = queue->array[queue->front];
	queue->front = (queue->front + 1)
				% queue->capacity;
	queue->size = queue->size - 1;
	return item;
}

int front(Queue* queue)
{
	if (isEmpty(queue))
		return INT_MIN;
	return queue->array[queue->front];
}

int rear(Queue* queue)
{
	if (isEmpty(queue))
		return INT_MIN;
	return queue->array[queue->rear];
}

int main()
{
	Queue* queue = createQueue(1000);

	enqueue(queue, 1);
	enqueue(queue, 2);
	enqueue(queue, 3);
	enqueue(queue, 4);

	cout << dequeue(queue)
		<< " dequeued from queue\n";

	cout << "Front item is "
		<< front(queue) << endl;
	cout << "Rear item is "
		<< rear(queue) << endl;

	return 0;
}


class Queue {
	int front, rear, size;
	int capacity;
	int array[];

	public Queue(int capacity)
	{
		this.capacity = capacity;
		front = this.size = 0;
		rear = capacity - 1;
		array = new int[this.capacity];
	}

	boolean isFull(Queue queue)
	{
		return (queue.size == queue.capacity);
	}

	boolean isEmpty(Queue queue)
	{
		return (queue.size == 0);
	}

	void enqueue(int item)
	{
		if (isFull(this))
			return;
		this.rear = (this.rear + 1)
					% this.capacity;
		this.array[this.rear] = item;
		this.size = this.size + 1;
		System.out.println(item
						+ " enqueued to queue");
	}


	int dequeue()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		int item = this.array[this.front];
		this.front = (this.front + 1)
					% this.capacity;
		this.size = this.size - 1;
		return item;
	}

	int front()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		return this.array[this.front];
	}

	int rear()
	{
		if (isEmpty(this))
			return Integer.MIN_VALUE;

		return this.array[this.rear];
	}
}

class Test {
	public static void main(String[] args)
	{
		Queue queue = new Queue(1000);

		queue.enqueue(1);
		queue.enqueue(2);
		queue.enqueue(3);
		queue.enqueue(4);

		System.out.println(queue.dequeue()
						+ " dequeued from queue\n");

		System.out.println("Front item is "
						+ queue.front());

		System.out.println("Rear item is "
						+ queue.rear());
	}
}

class Queue:

	# __init__ function
	def __init__(self, capacity):
		self.front = self.size = 0
		self.rear = capacity -1
		self.Q = [None]*capacity
		self.capacity = capacity

	def isFull(self):
		return self.size == self.capacity
	

	def isEmpty(self):
		return self.size == 0

	def EnQueue(self, item):
		if self.isFull():
			print("Full")
			return
		self.rear = (self.rear + 1) % (self.capacity)
		self.Q[self.rear] = item
		self.size = self.size + 1
		print("% s enqueued to queue" % str(item))


	def DeQueue(self):
		if self.isEmpty():
			print("Empty")
			return
		
		print("% s dequeued from queue" % str(self.Q[self.front]))
		self.front = (self.front + 1) % (self.capacity)
		self.size = self.size -1
		
	def que_front(self):
		if self.isEmpty():
			print("Queue is empty")

		print("Front item is", self.Q[self.front])
		
	def que_rear(self):
		if self.isEmpty():
			print("Queue is empty")
		print("Rear item is", self.Q[self.rear])


if __name__ == '__main__':

	queue = Queue(30)
	queue.EnQueue(1)
	queue.EnQueue(2)
	queue.EnQueue(3)
	queue.EnQueue(4)
	queue.DeQueue()
	queue.que_front()
	queue.que_rear()

Time complexity:

  • Enqueue: O(1)
  • Dequeue: O(1)
  • Front: O(1)
  • Rear: O(1)

Space complexity:
O(N) where N is the size of the array.

We tried to discuss Applications of queue in this article. We hope this article gives you a better understanding of Applications of queue data structures. Prepytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.

Queue Data structures: FAQs

  1. What is the queue Data structure?
    A queue is defined as the ordered list in which insertion and deletion are performed at two different ends i.e. REAR and FRONT end.

  2. What are the types of queue data structures?
    There are four types of queue data structures:
    Simple queue
    Circular queue
    Priority queue
    Dequeue

  3. What are the REAR and FRONT end?
    A queue is a collection of elements that are added at one end called “REAR” and removed from the other end called “FRONT”.

This article tried to discuss Applications of Queue Data Structure. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.

Leave a Reply

Your email address will not be published. Required fields are marked *