Learn Queue and it’s types using Java
There are types of queues and we are going to see, only types in it! Rest you are going to do!
Types of Queue :
→Simple Queue
A simple queue is the most basic queue. In this queue, the enqueue operation takes place at the rear, while the dequeue operation takes place at the front.
Now what is Enqueue and Dequeue?
Enqueue is adding item and dequeue is removing an item
Now let us compare stack and queue
→ Stack follows LIFO principle →Queue follows FIFO
→only elements can be added at top →Elements can be added at start
→Pop can be only done at top →Pop can be done at end
Ok now i guess you can understand what is queue.
→Circular Queue :
what is circular linked list?
Single linked list that contains last node’s next as head
Now what could be Circular queue?
In this queue, the last node points to the first node and creates a circular connection. Thus, it allows us to insert an item at the first node of the queue when the last node is full and the first node is free.
→Priority Queue :
In this queue, the enqueue operation takes place at the rear in the order of arrival of the items, while the dequeue operation takes place at the front based on the priority of the items.
That is to say that an item with a high priority will be dequeued before an item with a low priority.
In the case, when two or more items have the same priority, then they’ll be dequeued in the order of their arrival. Hence, it may or may not strictly follow the FIFO rule
→Double-Ended Queue
In this queue, the enqueue and dequeue operations take place at both front and rear. That means, we can insert an item at both the ends and can remove an item from both the ends.
Hence it’s an exception to Queue’s traditional FIFO method.
Simple Queue using Array :
Operations to keep in mind
→Enqueue
→Dequeue
→Peek
→isempty
→isfull
Initializing template →
public class Main
{
public static int front, rear, capacity;
public static int queue[];
Queue(int n){
front = rear = 0;
capacity = n;
queue = new int[capacity];
}
public static void main(String[] args) {
Queue q = new Queue(100);
}
}
We initialize front and read along with capacity of queue
Construct constructor
why? To declare values of variables
In main function create object and pass capacity of queue
ENQUEUE →
Algorithm :
Initialize function called whatever and get int data as parameter
If capacity is equal to real print This is to check if queue is full
Else declare queue of rear as data and add 1 to read
Example add 11,12,13,14,15,16 //rear = 6
DEQUEUE →
Algorithm :
If front is equal to rear then print queue is empty and end if
Else loop till rear-1 and make queue of i as queue of i+1 //this is to shift all elements by 1 to right
end loop and if rear is less than capacity then make queue of rear as zero end if
Example : 12,13,14,15,16,16 //rear = 6
decrement rear by 1
Example : 12,13,14,15,16 // rear = 5
end else
Display :
It’s very simple just loop rear of i till read and print queue of i;
Simple queue using Linked list
Enqueue →
Elements are added at end, so use insert at end
Dequeue →
Pop at end, so
Node dummy = head;
while(dummy.next!=null)
dummy = dummy.next;
end while
dummy.next = null;
Display →
Simple traversal of linked list
Wanna know how to Using standard rear and front in linked list?
class QNode {
int key;
QNode next;
public QNode(int key)
{
this.key = key;
this.next = null;
}
}
class Queue {
QNode front, rear;
public Queue()
{
this.front = this.rear = null;
}
public class Test {
public static void main(String[] args)
{
Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.dequeue();
q.dequeue();
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.dequeue();
System.out.println(“Queue Front : “ + q.front.key);
System.out.println(“Queue Rear : “ + q.rear.key);
}
}
Enqueue →
If rear is null, then declare both front to dummy node
Else rear of next as dummy node end else and rear as dummy //what this does?
//confusing?
Dequeue →
if front equal to null then print empty
else dummy = front // dummy is gonna have front (optional)
front = front.next //this points to next node after last node ie indirectly mentioning front = null
if front is null then change rear to null
code:
public class Main {
public static class Node {
public int data;
public Node next;
}
public static Node rear = null;
public static Node front = null;
public static void enqueue(int data) {
Node temp = new Node();
temp.data = data;
temp.next = null;
if(rear == null){
front = temp;
}
else{
rear.next = temp;
}
rear = temp;
}
public static void print() {
System.out.println(front.data);
}
public static void printall() {
Node dummy = front;
while (dummy != rear) {
System.out.println(dummy.data);
dummy = dummy.next;
}
System.out.println(dummy.data);
}
public static void main(String[] args) {
enqueue(5);
enqueue(8);
enqueue(6);
enqueue(7);
print();
printall();
}
}
— — — — — — — — — — — — — — — — — — — — — — —
I had made a blog for other types of queue, if you are interested to learn other types, please proceed to given link