Basic Operations of Queue in Data Structure
There are two basic operations of queue data structure:
-
Enqueue: This operation adds an element to the end of the queue
-
Dequeue: This operation removed an element from the front of the queue
-
Peek: The peek operation returns the element at the front of the queue without removing it
-
Size: The size operation returns the number of elements currently in the queue
- IsEmpty: The isEmpty operation returns a boolean value indicating whether the queue is empty or not
Types of Queues in Data Structure
Some of the common types of Queue data structures are:
Simple Queue
A simple queue is nothing but a standard queue that follows the FIFO (First In First Out) principle. This means that the first element added to the queue is the first element removed. Simple queues are often used to implement data structures such as stacks and priority queues.
Priority Queue
A priority queue is used to assign a priority value to each element in the queue. Elements with higher priority are dequeued before elements with lower priority, and it is of two types: min and max priority queue. A max priority queue is used to prioritize the maximum value element and min for the minimum value element. Priority queues are often used to implement scheduling algorithms and sorting algorithms.
Circular Queue
A circular queue is a type of queue in which the front and end of the queue are connected, forming a circle. This allows the operation to be more efficient because the elements do not need to be shifted when the queue is full. Circular queues are often used in operating systems to manage memory.
Dequeue
A double-ended queue, or deque, is a type of queue that allows elements to be inserted and removed from both the front and the end of the queue. This provides more flexibility than a simple queue, as elements do not need to be added to the end of the queue in order to be removed. Deques are often used in data structures such as queues and stacks.
Concurrent Queue
A concurrent queue is designed to be thread-safe and supports concurrent access by multiple threads. It ensures proper synchronization and handles issues related to data consistency in concurrent environments. Concurrent queues are often used in multithreaded applications to ensure that data is accessed in a consistent manner.
Some Common Applications of Queue Data Structure
1. Task Scheduling
A queue is an ideal data structure for task scheduling, which lets you perform all the tasks in order. Initially, all the tasks are pushed to the end of the queue. We can pick the task at the front of the queue and execute it. Once you complete the task, it is removed from the queue, and you select the next task. This process will continue until the queue is empty.
2. Batch Processing
Similar to task scheduling, you can use a queue data structure when you need to perform a large number of tasks in batches. Queue helps to complete all the tasks in order without leaving a task unprocessed.
3. Resource Allocation
The queue also helps to perform resource allocation. If a process requests a resource, it is pushed to the end of the queue. Then the system selects the first request and allocates the requested resource. You can remove this request from the queue once the process finishes the use of the requested resource. After that, the system selects further requests from the queue until the queue is empty.
4. Event Handling
In event handling, a queue data structure stores all the events that have occurred but are yet to be processed by the system. If a new event occurs, it is pushed to the end of the queue, and the system then processes the event from the front of the queue and removes it once handled.
5. Message Buffering
Message buffer stores the messages in the order they arrive and processes them one by one. The queue is an ideal data structure because of its FIO(First In, First Out) property.
6. Traffic Management
Circular queues are used to manage the traffic lights in a traffic management system for switching the traffic lights one by one, in order.
Application of Queue in Operating Systems
Application of queues in operating systems are:
-
It helps in First Come, First Serve to schedule.
-
It also makes CPU scheduling easier.
-
It is used in memory management.
-
It is used in semaphores.
- It is also used in spooling printers.
Applications of Queue in Networks
Applications of Queue in Networks are:
-
Queues are used in routers and switches.
-
It is used in packet switching.
-
It also helps in network monitoring.
-
Queues are used to manage network traffic.
- Network servers use queues for job scheduling.
Some Other Useful Applications of Queue
-
Whatsapp uses a queue to queue up the messages in the WhatsApp server if the recipient’s internet connection is turned off.
-
It is used in music applications to queue up a new song in a playlist.
-
It is used in traffic management to manage traffic lights.
-
Queues are used to handle the hardware or real-time system interrupts.
-
It is used to manage shared resources.
-
It helps in asynchronous data transfer between systems.
-
The queue also helps in using shared resources like CPU scheduling.
- Queue enables handling interruptions in Operating System.
Issues in Applications of Queue
-
The increasing number of elements leads to performance and scalability issues.
-
Queue faces overflow and underflow problems.
-
Queues sometimes fail in proper management of queue size and capacity.
-
There are performance trade-offs between various queue implementations.
-
There are memory management concerns, such as memory leaks and premature allocation.
-
Priority and ordering requirements beyond the standard FIFO order.
- Queues face synchronization and concurrency challenges on concurrent systems.
Implementation of Queue using Arrays
C++ Code
C++
#include <bits/stdc++.h>
using namespace std;
class Queue {
public:
int* array;
int front, rear, size;
int maxSize;
};
Queue* create_queue(int maxSize)
{
Queue* queue = new Queue();
queue->maxSize = maxSize;
queue->front = queue->size = 0;
queue->rear = maxSize - 1;
queue->array = new int[queue->maxSize];
return queue;
}
int isFull(Queue* queue)
{
return (queue->size == queue->maxSize);
}
int isEmpty(Queue* queue)
{
return (queue->size == 0);
}
void enqueue(Queue* queue, int item)
{
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)
% queue->maxSize;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
cout << item << " is enqueued to queue.\n";
}
void dequeue(Queue* queue)
{
if (isEmpty(queue))
{
cout<<"Queue is empty.\n";
return;
}
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % queue->maxSize;
queue->size = queue->size - 1;
cout << item << " is dequeued from the queue.\n";
}
int front(Queue* queue)
{
if (isEmpty(queue))
{
cout<<"Queue is empty\n";
return INT_MIN;
}
return queue->array[queue->front];
}
int rear(Queue* queue)
{
if (isEmpty(queue))
{
cout<<"Queue is empty\n";
return INT_MIN;
}
return queue->array[queue->rear];
}
int main()
{
Queue* queue = create_queue(10);
enqueue(queue, 10);
enqueue(queue, 30);
enqueue(queue, 51);
cout << "Front element of the queue is " << front(queue) << endl;
cout << "Rear element of the queue is " << rear(queue) << endl;
dequeue(queue);
dequeue(queue);
dequeue(queue);
dequeue(queue);
return 0;
}
You can also try this code with Online C++ Compiler
Output
10 is enqueued to queue.
30 is enqueued to queue.
51 is enqueued to queue.
Front element of the queue is 10
Rear element of the queue is 51
10 is dequeued from the queue.
30 is dequeued from the queue.
51 is dequeued from the queue.
Queue is empty.
Also read - Data Structure MCQ
Frequently Asked Questions
What are the applications of queues?
Job scheduling, Operating systems, message queues, task processing, buffering, BFS, etc, are some of the applications of queues.
What are the applications of queue and stack?
Expression evaluation, function call stack, undo-redo operations, backtracking, browser history, printer and spooling, web servers, etc, are some applications of queues and stacks.
What are some real-life examples of queue?
Supermarket checkout, ticket counters, customer service lines, ATM machines, Airports and security checkouts, public transport, etc, are some real-life examples of queues.
What is the technical application of queue in data structure?
Event-driven programming, task or process management, implementing caches, message passing and inter-process communication, etc are some technical applications in the queue data structure.
Conclusion
Queues are data structures that resemble real-life queues and support entry from one end and exit from another end. There are several real-life application of queue which involve the implementation of a stack using two queues, CPU task scheduling, graph traversals etc.
Data structures gave a way for solving real-life issues and queues are responsible for solving problems that involve the addition of data first followed by later processing of data. One should understand queues before moving on to more complex data structures such as graphs and trees as there are cases when queues are needed for their implementation.
Recommended Reading -
You can also consider our Online Coding Courses such as the DSA in Python, C++ DSA Course, DSA in Java Course to give your career an edge over others.
Happy Learning!
46+ registered 