Queue in Data Structure:
What is Queue?
In computer science, Queue is Fundamental (Basic) data Structures. Queue is a type of linear data structure that represents the collection of elements in which addition of new elements happens at one end (at the rare end) and the removal of the elements is happens at the other end (from the front end). It follows First in First out (FIFO), means the who first come will served first.
Implementation of Queue:
There are several data structures that can be used to implement a Queue. The choice of data structure depends on the specific requirements of your program or application. Here are two main data structures that can be used to implement a queue:
- Array: Arrays can be used to implement a queue by allocating the fixed-size array to store queue elements.
- Linked-List: A Linked List can be used to implement a queue by creating a new node for each element of the queue and linking them together. For linked list queue implementation we can use both Singly Linked List or doubly Linked List.
Implementation with Linked List:
Here for now we will use Singly Linked List to implement a simplest Queue. Insertion in Queue is called enqueue and deletion from queue is called dequeue.
Code is given below:
//Public class Queue:
public class Queue {
// Private inner Node class:
private class Node{
// Data members of Node class:
String data;
Node next;
// Constructor for node class:
Node(String d){
data = d;
next = null;
}
}
//Data members of queue class:
private Node front, rare;
private int size;
//Constructor of Queue class
public Queue(){
front = rare = null;
size = 0;
}
// Method for adding element at rare:
public void enqueue(String name){
Node nn = new Node(name);
if(isEmpty()){
front = rare = nn;
}
else{
rare.next = nn;
rare = nn;
}
size ++;
}
// Method for deleting element from the front
public String dequeue(){
String name;
if(isEmpty()){
return null;
}
else{
name = front.data;
front = front.next;
}
return name;
}
// Method for printing tue whole Queue:
public void printQueue(){
Node temp = front;
while(temp != null){
System.out.print(temp.data + " ");
temp = temp.next;}
}
// Method for checking if the queue is empty:
public boolean isEmpty(){
boolean status = true;
if(front != null){
status = false;
}
return status;
}
// Main Function:
public static void main(String[] args) {
//Ctrating an object of Queue
Queue myQueue = new Queue();
//Adding Elements in Queue:
myQueue.enqueue("Justin");
myQueue.enqueue("Clara");
myQueue.enqueue("Peter");
myQueue.enqueue("Marina");
myQueue.enqueue("Wyn");
//Deleting first two elements:
myQueue.dequeue();
myQueue.dequeue();
//Printing created Queue:
myQueue.printQueue();
}
}
Variants of Queue:
The followings are different types of Queues in data Structures each of them has its own applications:Circular Queue:
In a standard queue, new elements are added at the rear and removed from the front. In
a circular queue, the queue is treated as a circular buffer, so when the rear pointer reaches the end of the
buffer, it wraps around to the beginning. This allows for efficient use of memory and the ability to keep
track of the front and rear pointers without the need to resize the array. Circular queues are commonly
used in embedded systems where memory is limited.
Double-ended Queue (Deque):
A deque is a queue-like data structure that allows
for insertion and deletion at both the front and the rear. This allows for greater flexibility in managing the
data structure, as elements can be added or removed from either end of the queue. Deques can be
implemented using arrays or linked lists and are used in a wide range of applications such as simulation,
networking, and operating systems.
Priority Queue:
A priority queue is a special type of queue data structure where each element has a
priority associated with it, and the element with the highest priority is always at the front of the queue.
Elements are added to the queue based on their priority, and when an element is removed, the next
highest-priority element takes its place. Priority queues are commonly used in operating systems, network
routing, and simulations where tasks need to be executed in a particular order.
Concurrent Queue:
A concurrent queue is a thread-safe variant of the queue data structure, designed for
use in multi-threaded environments. In a multi-threaded environment, a standard queue can lead to race
conditions and data inconsistencies. A concurrent queue provides synchronized access to the queue,
ensuring that only one thread can access the queue at a time. Concurrent queues are commonly used in
concurrent programming languages such as Java and C#.
Blocking Queue:
A blocking queue is a queue data structure that blocks or waits when trying to dequeue an element from an empty queue or enqueue an element to a full queue. This provides a way for threads to synchronize their access to the queue, ensuring that the queue is always in a consistent state. Blocking queues are commonly used in concurrent programming, where threads are needed to communicate and coordinate their activities.
De-prioritized Queue:
A de-prioritized queue is a variant of the priority queue data structure where
elements can be removed from the middle of the queue, based on a specified priority. This allows for
greater flexibility in managing the priority of elements in the queue and enables the removal of lowerpriority elements without affecting the order of the higher-priority elements. De-prioritized queues are
commonly used in simulations, where tasks need to be executed in a particular order, but some tasks can
be de-prioritized if necessary.
Applications of Variants of Queue:
Priority Queue:
A priority queue is used when there is a need to process items based on their priority. It
is used in many real-world scenarios such as scheduling processes in an operating system, routing packets
in a computer network, and managing events in simulations or games.
Deque:
A deque is a double-ended queue that allows insertion and deletion of elements from both ends.
It is useful in applications that require fast insertion and deletion of elements from both ends, such as
implementing a sliding window in a streaming algorithm and maintaining the history of recently visited
pages in a web browser.
Circular Queue:
A circular queue is a data structure in which the last element is connected to the first
element forming a circular chain. It is useful in situations where there is a fixed amount of space available
for storing elements, such as storing logs in a logging system and implementing a buffer in a
communication system.
De-prioritized Queue:
A de-prioritized queue is like a priority queue, but it allows the priority of an item
to be decreased after it has been added to the queue. It is useful in scenarios where priorities can change
dynamically, such as handling incoming requests to a server where older requests may be de-prioritized
to ensure newer requests are handled in a timely manner.
Concurrent Queue:
A concurrent queue is a thread-safe version of the queue data structure that allows
multiple threads to access the queue at the same time. It is useful in concurrent programming scenarios
where multiple threads may need to access the queue simultaneously, such as in a producer-consumer
problem, where multiple producers add items to a queue, and multiple consumers remove items from
the queue.
0 Comments