Queue

Some Queue based concepts and logic are discussed below

Queue :

1. A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT.

2. Queue is referred to be as First In First Out list.

Applications of Queue

There are various applications of queues discussed as below.

  1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
  2. Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets.
  3. Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.
  4. Queue are used to maintain the play list in media players, in operating systems for handling interrupts.

Array Representation of QUEUE

There are two variables i.e. front and rear, that are implemented in the case of every queue. Front and rear variables point to the position from where insertions and deletions are performed in a queue. Initially, the value of front and queue is -1 which represents an empty queue.

After inserting an element at the rear end


The value of front remains -1 . However, the value of rear increases by one every time an insertion is performed in the queue.


After deleting an element from the front end


The value of front will increase from -1 to 0.

Algorith for Inserting an element:

  • Step 1: IF REAR = MAX - 1

Write OVERFLOW

Go to step

[END OF IF]

  • Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0

ELSE

SET REAR = REAR + 1

[END OF IF]

  • Step 3: Set QUEUE[REAR] = NUM
  • Step 4: EXIT

Algorithm for deleting an element:

  • Step 1: IF FRONT = -1 or FRONT > REAR

Write UNDERFLOW

ELSE

SET VAL = QUEUE[FRONT]

SET FRONT = FRONT + 1

[END OF IF]

  • Step 2: EXIT
Array Implementation of Queue:
import java.util.*;
class Queue
{ 
    static int front, rear, capacity; 
    static int queue[]; 
  
    Queue(int c) 
    { 
        front = rear = 0; 
        capacity = c; 
        queue = new int[capacity]; 
    } 
    static void queueEnqueue(int data) 
    { 
        if (capacity == rear)
        { 
            System.out.printf("\nQueue is full\n"); 
            return; 
        } 
        else
        { 
            queue[rear] = data; 
            rear++; 
        } 
        return; 
    } 
    static void queueDequeue() 
    { 
        if (front == rear) 
        { 
            System.out.printf("\nQueue is empty\n"); 
            return; 
        } 
        else 
        { 
            for (int i = 0; i < rear - 1; i++)
            { 
                queue[i] = queue[i + 1]; 
            } 
            if (rear < capacity) 
                queue[rear] = 0; 
            rear--; 
        } 
        return; 
    } 
    static void queueDisplay() 
    { 
        int i; 
        if (front == rear) 
        { 
            System.out.printf("\nQueue is Empty\n"); 
            return; 
        } 
        for (i = front; i < rear; i++) 
        { 
            System.out.printf(" %d <-- ", queue[i]); 
        } 
        return; 
    } 
    static void queueFront() 
    { 
        if (front == rear) { 
            System.out.printf("\nQueue is Empty\n"); 
            return; 
        } 
        System.out.printf("\nFront Element is: %d", queue[front]); 
        return; 
    } 
} 
public class Main
{ 
    public static void main(String[] args) 
    { 
        Queue q = new Queue(4); 
        q.queueDisplay(); 
        q.queueEnqueue(20); 
        q.queueEnqueue(30); 
        q.queueEnqueue(40); 
        q.queueEnqueue(50); 
        q.queueDisplay(); 
        q.queueEnqueue(60); 
        q.queueDisplay(); 
        q.queueDequeue(); 
        q.queueDequeue(); 
        System.out.printf("\n\nafter two node deletion\n\n"); 
        q.queueDisplay(); 
        q.queueFront(); 
    } 
}

output:
Queue is Empty
 20 <--  30 <--  40 <--  50 <-- 
Queue is full
 20 <--  30 <--  40 <--  50 <-- 

after two node deletion

 40 <--  50 <-- 
Front Element is: 40

Linked List Implementation of QUEUE

  1. The array implementation can not be used for the large scale applications where the queues are implemented. One of the alternative of array implementation is linked list implementation of queue.
  2. The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).
  3. In a linked queue, each node of the queue consists of two parts i.e. data part and the link part.

Operations in queue:

Insert operation:

The insert operation append the queue by adding an element to the end of the queue. The new element will be the last element of the queue.

Algorithm:

  • Step 1: Allocate the space for the new node PTR
  • Step 2: SET PTR -> DATA = VAL
  • Step 3: IF FRONT = NULL

SET FRONT = REAR = PTR

SET FRONT -> NEXT = REAR -> NEXT = NULL

ELSE

SET REAR -> NEXT = PTR

SET REAR = PTR

SET REAR -> NEXT = NULL

[END OF IF]

  • Step 4: END

Deletion :

Deletion operation removes the element that is first inserted among all the queue elements. The condition front == NULL becomes true if the list is empty.

Algorithm:

  • Step 1: IF FRONT = NULL

Write " Underflow "

Go to Step 5

[END OF IF]

  • Step 2: SET PTR = FRONT
  • Step 3: SET FRONT = FRONT -> NEXT
  • Step 4: FREE PTR
  • Step 5: END
Linked-List Implementation of queue:
import java.util.*;
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; 
    } 
    void enqueue(int key) 
    { 
        QNode temp = new QNode(key); 
        if (this.rear == null) 
        { 
            this.front = this.rear = temp; 
            return; 
        } 
        this.rear.next = temp; 
        this.rear = temp; 
    } 
    void dequeue() 
    { 
        if (this.front == null) 
            return; 
        QNode temp = this.front; 
        this.front = this.front.next; 
        if (this.front == null) 
            this.rear = null; 
    } 
} 
public class Main
{ 
    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); 
    } 
} 
output:
Queue Front : 40
Queue Rear : 50

Circular QUEUE


  1. if we delete 2 elements at the front end of the queue, we still can not insert any element since the condition rear = max -1 still holds.
  2. Circular queue will be full when front = -1 and rear = max-1. Implementation of circular queue is similar to that of a linear queue.

Insertion in Circular queue

  1. If (rear + 1)%maxsize = front, the queue is full.
  2. If rear != max - 1, then rear will be incremented to the mod(maxsize) and the new value will be inserted at the rear end of the queue.
  3. If front != 0 and rear = max - 1, then it means that queue is not full

Algorithm:

  • Step 1: IF (REAR+1)%MAX = FRONT

Write " OVERFLOW "

Goto step 4

[End OF IF]

  • Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0

ELSE IF REAR = MAX - 1 and FRONT ! = 0

SET REAR = 0

ELSE

SET REAR = (REAR + 1) % MAX

[END OF IF]

  • Step 3: SET QUEUE[REAR] = VAL
  • Step 4: EXIT

deletion from a circular queue:

  1. If front = -1, then there are no elements in the queue
  2. If there is only one element in the queue, the condition rear = front holds and therefore, both are set to -1 and the queue is deleted completely.
  3. If front = max -1 then, the value is deleted from the front end the value of front is set to 0.

Algorithm

  • Step 1: IF FRONT = -1

Write " UNDERFLOW "

Goto Step 4

[END of IF]

  • Step 2: SET VAL = QUEUE[FRONT]
  • Step 3: IF FRONT = REAR

SET FRONT = REAR = -1

ELSE

IF FRONT = MAX -1

SET FRONT = 0

ELSE

SET FRONT = FRONT + 1

[END of IF]

[END OF IF]

  • Step 4: EXIT
Implementation of Circular Queue:

import java.util.*;
public class Main
{
   static int Queue[] = new int[50];
      static int n, front, rear;
 public static void CircularQueue(int size)
 {
    n=size;
      front = 0;
         rear=0;
  }
  public static void enqueue(int item)
  {
      if((rear+1) % n != front)
     {
        rear = (rear+1)%n;
           Queue[rear] = item;
     }
      else
    {
        System.out.println("Queue is full !");
    }
  }
   public static int dequeue()
  {
     int item=0;
      if(front!=rear)
    {
      front = (front+1)%n;
       item = Queue[front];
    }
      else
    {
         System.out.println("Can't remove element from queue");
    }
    return item;
  }
   public static void display()
  {
      int i;
       if(front != rear)
    {
        for(i=(front+1)%n ; i<rear ; i=(i+1)%n)
      {
          System.out.println(Queue[i]);
      }
    }
       else
         System.out.println("Queue is empty !");
  }
    public static void main(String args[]) 
  {
     System.out.print("Enter the size of the queue : ");
       Scanner scan = new Scanner (System.in);
         int size = scan.nextInt();
         CircularQueue(size);
         int x;
       boolean flag=true;
       while(flag)
    {
       System.out.print("\n 1 : Add\n 2 : Delete\n 3 : Display\n 4 : Exit\n\n\n\n Enter Choice : ");
         x = scan.nextInt();
          switch(x)
       {
           case 1 :
                     System.out.print("\n Enter element u want to add in queue: ");
                     int num = scan.nextInt();
                     enqueue(num);
                       break;
           case 2 :
                     int data = dequeue();
                     System.out.println("\n Item deleted from queue is :" + data);
                       break;
          case 3 :
                     display();
                      break;
         case 4 :
                    flag=false;
                      break;
        default :
                   System.out.println("\n Wrong Choice !");
                      break;
      }
    }
  }
}

Problems based on Queue

Find the shortest distance (Minimum number of steps taken by a knight) to reach from source to destination:

Knight movement is given below

input 1:

8

0 7

7 0

output 1:

Minimum number of steps required is 6

import java.util.*;
class Node
{
  int x, y, dist;
 public Node(int x, int y) 
 {
  this.x = x;
  this.y = y;
 }
 public Node(int x, int y, int dist) 
 {
  this.x = x;
  this.y = y;
  this.dist = dist;
 }
 @Override
 public boolean equals(Object o) 
 {
  if (this == o) return true;
  if (o == null || getClass() != o.getClass()) return false;

  Node node = (Node) o;

  if (x != node.x) return false;
  if (y != node.y) return false;
  return dist == node.dist;
 }

 @Override
 public int hashCode()
 {
  int result = x;
  result = 31 * result + y;
  result = 31 * result + dist;
  return result;
 }
};
public class Main
{
 // Below arrays details all 8 possible movements for a knight
 private static int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
 private static int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
 private static boolean valid(int x, int y, int N)
 {
  if (x < 0 || y < 0 || x >= N || y >= N)
   return false;

  return true;
 }
 public static int BFS(Node src, Node dest, int N)
 {
  Set<Node> visited = new HashSet<>();
  Queue<Node> q = new ArrayDeque<>();
  q.add(src);
  while (!q.isEmpty())
  {
   Node node = q.poll();
   int x = node.x;
   int y = node.y;
   int dist = node.dist;
   if (x == dest.x && y == dest.y)
    return dist;
   if (!visited.contains(node))
   {
    visited.add(node);
    for (int i = 0; i < 8; ++i)
    {
     int x1 = x + row[i];
     int y1 = y + col[i];

     if (valid(x1, y1, N))
      q.add(new Node(x1, y1, dist + 1));
    }
   }
  }
  return Integer.MAX_VALUE;
 }
 public static void main(String[] args)
 {
     Scanner sc=new Scanner(System.in);
  int N = sc.nextInt();
  int srcR=sc.nextInt();
  int srcC=sc.nextInt();
  int destR=sc.nextInt();
  int destC=sc.nextInt();
  Node src = new Node(srcR,srcC);
  Node dest = new Node(destR,destC);
  System.out.println("Minimum number of steps required is " + BFS(src, dest, N));
 }
}
Array Implementation of queue:

import java.util.*;
public class Main
{
    static int n=0;
    static class Queue
    {
        int front=-1,rear=-1;
        List<Integer> al=new ArrayList<>();
        boolean isEmpty()
        {
            if(front==-1&&rear==-1)
            return true;
            else
            return false;
        }
        boolean isFull()
        {
            if(front==n&&rear==n)
            return true;
            else
            return false;
        }
        void Enqueue(int n)
        {
            if(!isFull())
            {
                if(isEmpty())
                front=rear=0;
                else
                rear=rear+1;
            }
            al.add(n);
        }
        int Dequeue()
        {
            int num=0;
            if(!isEmpty())
            {
                if(front==rear)
                {
                    num=al.get(front);
                    front=rear=-1;
                }
                else 
                {
                    num=al.get(front);
                    front=front+1;
                }
            }
            return num;
        }
    }
    public static void main(String args[]) 
    {
         Scanner sc=new Scanner(System.in);
         Queue queue=new Queue();
         n=sc.nextInt();
         for(int index=1;index<=n;index++)
         {
             queue.Enqueue(sc.nextInt());
         }
         for(int index=1;index<=n;index++)
         {
             System.out.print(queue.Dequeue()+" ");
         }
    }
}

input 1:
5 
1 2 3 4 5

output 1:
1 2 3 4 5

input 2:
14
16 28 10 36 190 35 18 39 16 278 18 37 17 89

output 2:
16 28 10 36 190 35 18 39 16 278 18 37 17 89