Write a Java program to implement a queue data structure using a singly linked l
ID: 3600746 • Letter: W
Question
Write a Java program to implement a queue data structure using a singly linked list. You can assume the items to be stored in the queue are distinct positive integers. You do not need to incorporate any ordering of the items. However, the queue must implement a front and a rear. The insert operation will use rear and the delete operation will use front. Restrictions: You are not allowed to use any Java API that supports queue interface or list class, rather you are required to build your own singly linked list by defining a node class and implementing a singly linked list class, followed by using that class to implement the queue. If you wish you may use the singly linked list code provided earlier. Programming: Your driver program must have a main() method that is interactive (menu driven) and should give the following options to a user: i) Insert an item into the queue ii) Delete from the queue iii) Display the item at front iv) Display the item at rear v) Display total number of items currently present in the queue vi) Print the items currently present in the queue, from front to rear vii) Quit Program run: The program should start with the menu and the user should be able to choose any option from the menu. The menu should keep coming back, after producing appropriate output for each user choice, until the user selects ‘Quit’ option. Also, include proper error checking (for example, when someone tries to delete item from an empty queue, or tries to display items of an empty queue) with appropriate message(s).
Explanation / Answer
import java.util.*;
/* Class Node */
class Node
{
protected int data;
protected Node link;
/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
/* Class linkedQueue */
class linkedQueue
{
protected Node front, rear;
public int size;
/* Constructor */
public linkedQueue()
{
front = null;
rear = null;
size = 0;
}
/* Function to check if queue is empty */
public boolean isEmpty()
{
return front == null;
}
/* Function to get the size of the queue */
public int getSize()
{
return size;
}
/* Function to insert an element to the queue */
public void insert(int data)
{
Node nptr = new Node(data, null);
if (rear == null)
{
front = nptr;
rear = nptr;
}
else
{
rear.setLink(nptr);
rear = rear.getLink();
}
size++ ;
}
/* Function to remove front element from the queue */
public int remove()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
Node ptr = front;
front = ptr.getLink();
if (front == null)
rear = null;
size-- ;
return ptr.getData();
}
/* Function to check the front element of the queue */
public int frontElement()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return front.getData();
}
public int rearElement()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
return rear.getData();
}
/* Function to display the status of the queue */
public void display()
{
System.out.print(" Queue = ");
if (size == 0)
{
System.out.print("Empty ");
return ;
}
Node ptr = front;
while (ptr != rear.getLink() )
{
System.out.print(ptr.getData()+" ");
ptr = ptr.getLink();
}
System.out.println();
}
}
/* Class LinkedQueueImplement */
public class LinkedQueueImplement
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class linkedQueue */
linkedQueue lq = new linkedQueue();
/* Perform Queue Operations */
char ch;
while(true)
{
System.out.println("1. insert");
System.out.println("2. remove");
System.out.println("3. Display at front");
System.out.println("4. Display at rear");
System.out.println("5. Display total No.of Items");
System.out.println("6. Display Queue");
System.out.println("7. Quit");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
lq.insert( scan.nextInt() );
break;
case 2 :
try
{
System.out.println("Removed Element = "+ lq.remove());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 3 :
try
{
System.out.println("Front Element = "+ lq.frontElement());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 4 :
try
{
System.out.println("Rear Element = "+ lq.rearElement());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 5 :
System.out.println("Size = "+ lq.getSize());
break;
case 6 :
lq.display();
break;
case 7 :
System.exit(0);
default :
System.out.println("Wrong Entry ");
break;
}
}
}
}
Output:
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
1
Enter integer element to insert
1
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
1
Enter integer element to insert
2
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
1
Enter integer element to insert
3
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
3
Front Element = 1
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
4
Rear Element = 3
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
5
Size = 3
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
6
Queue = 1 2 3
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
2
Removed Element = 1
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
5
Size = 2
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
6
Queue = 2 3
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
2
Removed Element = 2
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
2
Removed Element = 3
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
6
Queue = Empty
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
5
Size = 0
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
2
Error : Underflow Exception
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
3
Error : Underflow Exception
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
4
Error : Underflow Exception
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
6
Queue = Empty
1. insert
2. remove
3. Display at front
4. Display at rear
5. Display total No.of Items
6. Display Queue
7. Quit
7
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.