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.

Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
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.
Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.
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

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.
The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).
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

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.
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

If (rear + 1)%maxsize = front, the queue is full.
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.
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:

If front = -1, then there are no elements in the queue
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.
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:

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:

1 2 3 4 5

output 1:

1 2 3 4 5

input 2:

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

Page updated

Google Sites

Report abuse