Java Program to Implement Doubly Ended Queue

This is a Java Program to implement a Double Ended Queue. Queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. This makes queue a First-In-First-Out (FIFO) data structure. However in a double ended queue addition and removal of entities can be performed at both ends. A double-ended queue (dequeue) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).

Here is the source code of the Java program to implement a Double Ended Queue. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  * Java Program to Implement Double Ended Queue
  3.  */
  4.  
  5. import java.util.*;
  6.  
  7. /*  Class Node  */
  8. class Node
  9. {
  10.     protected int data;
  11.     protected Node link;
  12.  
  13.     /*  Constructor  */
  14.     public Node()
  15.     {
  16.         link = null;
  17.         data = 0;
  18.     }    
  19.     /*  Constructor  */
  20.     public Node(int d,Node n)
  21.     {
  22.         data = d;
  23.         link = n;
  24.     }    
  25.     /*  Function to set link to next Node  */
  26.     public void setLink(Node n)
  27.     {
  28.         link = n;
  29.     }    
  30.     /*  Function to set data to current Node  */
  31.     public void setData(int d)
  32.     {
  33.         data = d;
  34.     }    
  35.     /*  Function to get link to next node  */
  36.     public Node getLink()
  37.     {
  38.         return link;
  39.     }    
  40.     /*  Function to get data from current Node  */
  41.     public int getData()
  42.     {
  43.         return data;
  44.     }
  45. }    
  46.  
  47. /*  Class Dequeue  */
  48. class Dequeue
  49. {
  50.     private Node front, rear;
  51.     private int size;
  52.  
  53.     /* Constructor */
  54.     public Dequeue()
  55.     {
  56.         front = null;
  57.         rear = null;
  58.         size = 0;
  59.     }    
  60.     /*  Function to check if queue is empty */
  61.     public boolean isEmpty()
  62.     {
  63.         return front == null;
  64.     }    
  65.     /*  Function to get the size of the queue */
  66.     public int getSize()
  67.     {
  68.         return size;
  69.     }
  70.     /* Clear dequeue */
  71.     public void clear()
  72.     {
  73.         front = null;
  74.         rear = null;
  75.         size = 0;
  76.     }
  77.     /*  Function to insert an element at begining  */
  78.     public void insertAtFront(int val)
  79.     {
  80.         Node nptr = new Node(val, null);    
  81.         size++ ;    
  82.         if (front == null) 
  83.         {
  84.             front = nptr;
  85.             rear = front;
  86.         }
  87.         else 
  88.         {
  89.             nptr.setLink(front);
  90.             front = nptr;
  91.         }
  92.     }
  93.     /*  Function to insert an element at end  */
  94.     public void insertAtRear(int val)
  95.     {
  96.         Node nptr = new Node(val,null);    
  97.         size++ ;    
  98.         if (rear == null) 
  99.         {
  100.             rear = nptr;
  101.             front = rear;
  102.         }
  103.         else 
  104.         {
  105.             rear.setLink(nptr);
  106.             rear = nptr;
  107.         }
  108.     }    
  109.     /*  Function to remove front element from the queue */
  110.     public int removeAtFront()
  111.     {
  112.         if (isEmpty() )
  113.             throw new NoSuchElementException("Underflow Exception");
  114.         Node ptr = front;
  115.         front = ptr.getLink();
  116.  
  117.         if (front == null)
  118.             rear = null;
  119.         size-- ;
  120.  
  121.         return ptr.getData();
  122.     }
  123.     /*  Function to remove rear element from the queue */
  124.     public int removeAtRear()
  125.     {
  126.         if (isEmpty() )
  127.             throw new NoSuchElementException("Underflow Exception");
  128.         int ele = rear.getData();
  129.         Node s = front;
  130.         Node t = front;
  131.         while (s != rear)
  132.         {
  133.             t = s;
  134.             s = s.getLink();
  135.         }
  136.         rear = t;
  137.         rear.setLink(null);
  138.         size --;
  139.  
  140.         return ele;
  141.     }        
  142.     /*  Function to check the front element of the queue */
  143.     public int peekAtFront()
  144.     {
  145.         if (isEmpty() )
  146.             throw new NoSuchElementException("Underflow Exception");
  147.         return front.getData();
  148.     }
  149.     /*  Function to check the front element of the queue */
  150.     public int peekAtRear()
  151.     {
  152.         if (isEmpty() )
  153.             throw new NoSuchElementException("Underflow Exception");
  154.         return rear.getData();
  155.     }    
  156.     /*  Function to display the status of the queue */
  157.     public void display()
  158.     {
  159.         System.out.print("\nDequeue = ");
  160.         if (size == 0)
  161.         {
  162.             System.out.print("Empty\n");
  163.             return ;
  164.         }
  165.         Node ptr = front;
  166.         while (ptr != rear.getLink() )
  167.         {
  168.             System.out.print(ptr.getData()+" ");
  169.             ptr = ptr.getLink();
  170.         }
  171.         System.out.println();        
  172.     }
  173. }
  174.  
  175. /*  Class DoubleEndedQueueTest  */
  176. public class DoubleEndedQueueTest
  177. {    
  178.     public static void main(String[] args)
  179.     {
  180.         Scanner scan = new Scanner(System.in); 
  181.         /* Creating object of class Dequeue */   
  182.         Dequeue dq = new Dequeue();            
  183.         /* Perform Dequeue Operations */    
  184.         System.out.println("Dequeue Test\n"); 
  185.         char ch;        
  186.         do
  187.         {
  188.             System.out.println("\nDequeue Operations");
  189.             System.out.println("1. insert at front");
  190.             System.out.println("2. insert at rear");
  191.             System.out.println("3. delete at front");
  192.             System.out.println("4. delete at rear");
  193.             System.out.println("5. peek at front");
  194.             System.out.println("6. peek at rear");
  195.             System.out.println("7. size");
  196.             System.out.println("8. check empty");
  197.             System.out.println("9. clear");
  198.             int choice = scan.nextInt();
  199.             switch (choice)
  200.             {
  201.             case 1 : 
  202.                 System.out.println("Enter integer element to insert");
  203.                 dq.insertAtFront( scan.nextInt() );
  204.                 break;  
  205.             case 2 : 
  206.                 System.out.println("Enter integer element to insert");
  207.                 dq.insertAtRear( scan.nextInt() );
  208.                 break;                         
  209.             case 3 : 
  210.                 try 
  211.                 {
  212.                     System.out.println("Removed Element = "+ dq.removeAtFront());
  213.                 }
  214.                 catch (Exception e)
  215.                 {
  216.                     System.out.println("Error : " + e.getMessage());
  217.                 }    
  218.                 break;
  219.             case 4 : 
  220.                 try 
  221.                 {
  222.                     System.out.println("Removed Element = "+ dq.removeAtRear());
  223.                 }
  224.                 catch (Exception e)
  225.                 {
  226.                     System.out.println("Error : " + e.getMessage());
  227.                 }    
  228.                 break;                         
  229.             case 5 : 
  230.                 try
  231.                 {
  232.                     System.out.println("Peek Element = "+ dq.peekAtFront());
  233.                 }
  234.                 catch (Exception e)
  235.                 {
  236.                     System.out.println("Error : " + e.getMessage());
  237.                 }
  238.                 break;
  239.             case 6 : 
  240.                 try
  241.                 {
  242.                     System.out.println("Peek Element = "+ dq.peekAtRear());
  243.                 }
  244.                 catch (Exception e)
  245.                 {
  246.                     System.out.println("Error : " + e.getMessage());
  247.                 }
  248.                 break;                         
  249.             case 7 : 
  250.                 System.out.println("Size = "+ dq.getSize());
  251.                 break; 
  252.             case 8 : 
  253.                 System.out.println("Empty status = "+ dq.isEmpty());
  254.                 break; 
  255.             case 9 : 
  256.                 System.out.println("\nDequeue Cleared\n");
  257.                 dq.clear();
  258.                 break;                         
  259.             default : 
  260.                 System.out.println("Wrong Entry \n ");
  261.                 break;
  262.             }                
  263.             /* display dequeue */        
  264.             dq.display();
  265.  
  266.             System.out.println("\nDo you want to continue (Type y or n) \n");
  267.             ch = scan.next().charAt(0);            
  268.         } while (ch == 'Y'|| ch == 'y');                                                            
  269.     } 
  270. }

Dequeue Test
 
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
1
Enter integer element to insert
5
 
Dequeue = 5
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
1
Enter integer element to insert
8
 
Dequeue = 8 5
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
2
Enter integer element to insert
3
 
Dequeue = 8 5 3
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
2
Enter integer element to insert
45
 
Dequeue = 8 5 3 45
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
1
Enter integer element to insert
28
 
Dequeue = 28 8 5 3 45
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
5
Peek Element = 28
 
Dequeue = 28 8 5 3 45
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
6
Peek Element = 45
 
Dequeue = 28 8 5 3 45
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
7
Size = 5
 
Dequeue = 28 8 5 3 45
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
3
Removed Element = 28
 
Dequeue = 8 5 3 45
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
4
Removed Element = 45
 
Dequeue = 8 5 3
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
3
Removed Element = 8
 
Dequeue = 5 3
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
7
Size = 2
 
Dequeue = 5 3
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
9
 
Dequeue Cleared
 
 
Dequeue = Empty
 
Do you want to continue (Type y or n)
 
y
 
Dequeue Operations
1. insert at front
2. insert at rear
3. delete at front
4. delete at rear
5. peek at front
6. peek at rear
7. size
8. check empty
9. clear
8
Empty status = true
 
Dequeue = Empty
 
Do you want to continue (Type y or n)
 
n

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.