Deque Implementation : Double Ended Queue Java Program Source Code

Deque , is a short abbreviation of Double Ended QUEue . Java provides Deque class , which is found in java.util package . Here we try to apply the functionality of deque in the console based java programming . Deque is an abstract data type which is a generalize form of queue .
In deque the elements can be added or removed only from two ends i.e beginning and tail end .
A-Steal job scheduling algorithm is an example of deque implementation.

Here in this below example , you can select the add ,remove , display or exit functionality by choosing the number in front of the options .
If you selected the add or remove functionality then there will be two more actions you can perform, you can either add or remove them from end or at beginning . For front end insertion/deletion press a or rear end insertion /deletion press b .

Here in deque there are two pointers associated with each link .

---> ---> ---> -->
5 2 4 34 27
<--- <--- <--- <--

Actually in java there are built in methods to perform the task which are done by deque .

Deque can perform the following functions : JAVA built in methods

* Insertion at the front offerFirst
* Insertion at the back offerLast
* Remove element from the front pollFirst
* Remove element from the back pollLast

These methods are found in the java.util.ArrayDequeue class in java . If you see the oracle docs then you will find two more methods in the class addFirst() and addLast() , then one obvious question arises what is the difference between offerFirst and addFirst methods .
The difference is in the return type of the two methods , addFirst() methods return type is void while the return type of the offerFirst() method is boolean . So we can use offerFirst() method in the condition of the loops as well . Similar difference also exist between the addLast() and offerLast() method of the arraydeque class .

There is also removeFirst() and removeLast() methods in the arraydeque class , then the question arises why we choose pollFirst() instead of removeFirst() .
The only difference between the pollFirst and removeFirst methods is that the pollFirst() method has extra feature , that is , if the deque is empty then the pollFirst() method will return null .
Similar is the reason of difference between pollLast() and removeLast() methods .

Pseudo code :

1. Choose add,remove,display or exit from the menu
2. If add
2.1 choose rear or front
inserted
3. If remove
3.1 choose front end or rear end
deleted
4. If display
show all elements in the deque to the console
5. If choose exit
then program shuts down

Here we intentionally use the skip method to read the characters from the console . The functionality of the skip method is to skip the specified number of inputs from the input stream .
Suppose n is 2
so skip(5 * n) ,
that is skip(10) , so it will skip the 10 characters in the input stream or in other words start reading the input stream from the 11 th character .

One example of deque implementation is the A-Steal job scheduling algorithm . This algorithm implements task scheduling for various processors .

Demo :

Deque insertion and deletion front and rear end

Please find the Code below :

import java.io.*;
import java.util.*;
public class Dequeue
{
    static char s,s1=' ';
    static int n=0;
    public static void first(LinkedList l)
    {
        System.out.println("1. add");
        System.out.println("2. remove");
        System.out.println("3. display");
        System.out.println("4. exit");
        //   System.out.println(l);
        try
        {
            System.in.skip(5*n);
            char s=(char)System.in.read();
            //      System.out.println(s);
            choose(l,s);
        }
        catch(Exception e){}
    }
    
    public static void main(String as[])
    {
        LinkedList l1=new LinkedList();
        first(l1);
    }
    
    public static void choose( LinkedList l,char s) throws Exception
    {
        n++;
        if((s=='1')||(s=='2'))
        {
            System.out.println(" a) Front end");
            System.out.println(" b) Rear end");
            System.out.println(" c) back");
            work(l,s);
        }
        else if(s=='3')
        {
            System.out.println(l);
            rest(l);
        }
        else if(s=='4')
        {
            System.exit(0);
        }
        
        else
        {
            System.out.println(">>>>>>  BAWARI PUCCHH SAHI DAL <<<<<<<<");
            rest(l);
        }
    }
    
    public static  void work(LinkedList l,char s) throws Exception
    {
        System.out.println("Enter the choice ");
        System.in.skip((5*n)+2);
        char s1=(char)System.in.read();
        //    System.out.println(s1);
        if(s1=='c')
        {
            first(l);
        }
        else if(s=='1')
        frontEnd(s1,l);
        else if(s=='2')
        backEnd(s1,l);
    }
    
    public static void rest(LinkedList l)
    {
        try
        {
            Thread.sleep(2000);
            first(l);
        }
        catch(Exception e){};
    }
    
    public static void frontEnd(char s1,LinkedList l) throws Exception
    {
        if(s1=='a')
        {
            System.out.println("Enter the String");
            System.in.skip((5*n)+4);
            char s2=(char)System.in.read();
            l.offerFirst(s2);
            //     System.out.println(l);
            rest(l);
        }
        else if(s1=='b')
        {
            System.out.println("Enter the character");
            System.in.skip((5*n)+4);
            char s2=(char)System.in.read();
            l.offerLast(s2);
            //     System.out.println(l);
            rest(l);
        }
        else
        {
            System.out.println(">>>>>>  BAWARI PUCCHH SAHI DAL <<<<<<<<");
            rest(l);
        }
    }
    
    public static void backEnd(char s1,LinkedList l)
    {
        if(s1=='a')
        {
            if(l.size()!=0)
            l.removeFirst();
            else
            System.out.println("please insert elements first(:(: BAWARI  PUCCCHHH :):)");
            //     System.out.println(l);
            rest(l);
        }
        else if(s1=='b')
        {
            if(l.size()!=0)
            l.removeLast();
            else
            System.out.println("please insert elements first (:(: BAWARI  PUCCCHHH :):)");
            //      System.out.println(l);
            rest(l);
        }
        else
        {
            System.out.println(">>>>>>  BAWARI PUCCHH SAHI DAL <<<<<<<<");
            rest(l);
        }
    }
    
}

Author : Anonymous J

Share this

Deque Implementation : Double Ended Queue Java Program Source Code

Author : Anonymous J

Share this

Related Posts