Java Program to Implement Queue using Linked List

«
»
This is a Java Program to implement a queue using linked list. 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. A linked list is an ordered set of data elements, each containing a link to its successor. Here we need to apply the application of linked list to perform basic operations of a queue.

Here is the source code of the Java program to implement a queue using linked list. 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 Queue using Linked List
  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 linkedQueue  */
  48. class linkedQueue
  49. {
  50.     protected Node front, rear;
  51.     public int size;
  52.  
  53.     /* Constructor */
  54.     public linkedQueue()
  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.     /*  Function to insert an element to the queue */
  71.     public void insert(int data)
  72.     {
  73.         Node nptr = new Node(data, null);
  74.         if (rear == null)
  75.         {
  76.             front = nptr;
  77.             rear = nptr;
  78.         }
  79.         else
  80.         {
  81.             rear.setLink(nptr);
  82.             rear = rear.getLink();
  83.         }
  84.         size++ ;
  85.     }    
  86.     /*  Function to remove front element from the queue */
  87.     public int remove()
  88.     {
  89.         if (isEmpty() )
  90.             throw new NoSuchElementException("Underflow Exception");
  91.         Node ptr = front;
  92.         front = ptr.getLink();        
  93.         if (front == null)
  94.             rear = null;
  95.         size-- ;        
  96.         return ptr.getData();
  97.     }    
  98.     /*  Function to check the front element of the queue */
  99.     public int peek()
  100.     {
  101.         if (isEmpty() )
  102.             throw new NoSuchElementException("Underflow Exception");
  103.         return front.getData();
  104.     }    
  105.     /*  Function to display the status of the queue */
  106.     public void display()
  107.     {
  108.         System.out.print("\nQueue = ");
  109.         if (size == 0)
  110.         {
  111.             System.out.print("Empty\n");
  112.             return ;
  113.         }
  114.         Node ptr = front;
  115.         while (ptr != rear.getLink() )
  116.         {
  117.             System.out.print(ptr.getData()+" ");
  118.             ptr = ptr.getLink();
  119.         }
  120.         System.out.println();        
  121.     }
  122. }
  123.  
  124. /*  Class LinkedQueueImplement  */
  125. public class LinkedQueueImplement
  126. {    
  127.     public static void main(String[] args)
  128.     {
  129.         Scanner scan = new Scanner(System.in); 
  130.         /* Creating object of class linkedQueue */   
  131.         linkedQueue lq = new linkedQueue();            
  132.         /* Perform Queue Operations */    
  133.         System.out.println("Linked Queue Test\n"); 
  134.         char ch;        
  135.         do
  136.         {
  137.             System.out.println("\nQueue Operations");
  138.             System.out.println("1. insert");
  139.             System.out.println("2. remove");
  140.             System.out.println("3. peek");
  141.             System.out.println("4. check empty");
  142.             System.out.println("5. size");
  143.             int choice = scan.nextInt();
  144.             switch (choice)
  145.             {
  146.             case 1 : 
  147.                 System.out.println("Enter integer element to insert");
  148.                 lq.insert( scan.nextInt() );
  149.                 break;                         
  150.             case 2 : 
  151.                 try 
  152.                 {
  153.                     System.out.println("Removed Element = "+ lq.remove());
  154.                 }
  155.                 catch (Exception e)
  156.                 {
  157.                     System.out.println("Error : " + e.getMessage());
  158.                 }    
  159.                 break;                         
  160.             case 3 : 
  161.                 try
  162.                 {
  163.                     System.out.println("Peek Element = "+ lq.peek());
  164.                 }
  165.                 catch (Exception e)
  166.                 {
  167.                     System.out.println("Error : " + e.getMessage());
  168.                 }
  169.                 break;                         
  170.             case 4 : 
  171.                 System.out.println("Empty status = "+ lq.isEmpty());
  172.                 break;
  173.  
  174.             case 5 : 
  175.                 System.out.println("Size = "+ lq.getSize());
  176.                 break;  
  177.  
  178.             default : 
  179.                 System.out.println("Wrong Entry \n ");
  180.                 break;
  181.             }                
  182.             /* display queue */        
  183.             lq.display();
  184.  
  185.             System.out.println("\nDo you want to continue (Type y or n) \n");
  186.             ch = scan.next().charAt(0);            
  187.         } while (ch == 'Y'|| ch == 'y');                                                            
  188.     } 
  189. }

advertisement
Linked Queue Test
 
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
4
Empty status = true
 
Queue = Empty
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
24
 
Queue = 24
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
5
 
Queue = 24 5
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
9
 
Queue = 24 5 9
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
72
 
Queue = 24 5 9 72
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
14
 
Queue = 24 5 9 72 14
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
1
Enter integer element to insert
1
 
Queue = 24 5 9 72 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
5
Size = 6
 
Queue = 24 5 9 72 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
3
Peek Element = 24
 
Queue = 24 5 9 72 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 24
 
Queue = 5 9 72 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 5
 
Queue = 9 72 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 9
 
Queue = 72 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
5
Size = 3
 
Queue = 72 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
3
Peek Element = 72
 
Queue = 72 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 72
 
Queue = 14 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 14
 
Queue = 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
3
Peek Element = 1
 
Queue = 1
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Removed Element = 1
 
Queue = Empty
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
2
Error : Underflow Exception
 
Queue = Empty
 
Do you want to continue (Type y or n)
 
y
 
Queue Operations
1. insert
2. remove
3. peek
4. check empty
5. size
4
Empty status = true
 
Queue = 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.

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 & technical discussions at Telegram SanfoundryClasses.