Question
Implement the queue using a linked list. Use the followingclass definition for the queue and use the given main method totest your implementation.
public class Queue
{
private class node
{
int data;
node next;
}
private node myFront;//pointer to the frontof the queue
private node myBack; //pointer to theback of the queue
public Queue()
{//Create an empty queue}
public boolean empty()
{// return true if queue is empty,otherwise return false}
public void addQ(int value)
{//add to the back of the queue}
public void display()
{//display data stored in queue fromfront to back}
public int front()
{//return the front value of thequeue}
public void removeQ()
{//remove the value at the front of thequeue}
}
public static void main(String[] args)
{
Queue Q = new Queue();
// insert each value 1 through 5 onto thequeue
for(int x = 1; x<=5; x++)
Q.addQ(x);
//Display the content of the queue to thescreen
Q.display();
//Remove and display each value on thequeue
while (!S.empty())
{ int x;
x =Q.front();
System.out.println();
System.out.println(“removing … “ + x);
Q.removeQ();
Q.display();
}
if (Q.empty())
System.out.println(“Queue is empty.”);
}
Explanation / Answer
public class Queue { private class Node { intdata; Nodenext; } private Node myFront;//pointer to the front ofthe queue private Node myBack; //pointer to the backof the queue public Queue() {//Create an empty queue myFront=null; myBack= null; } public boolean empty() {// return true if queue is empty, otherwisereturn false if(myFront ==null) returntrue; else returnfalse; } public void addQ(int value) {//add to the back of the queue Node temp= newNode(); temp.data = value; temp.next=null; if(myBack ==null) { myBack=temp; myFront= myBack; } else { temp.next=myBack; myBack=temp; } } public void display() {//display data stored in queue from frontto back String s=""; Node temp= myBack; while(temp!=null) { s = (temp.data) + " " +s; temp= temp.next; } System.out.println("Displaying QUEUE: " + s); } public int front() {//return the front value of the queue return myFront.data; } public void removeQ() {//remove the value at the front of thequeue Node temp1 =myBack; boolean check =false; while( ! check) { //Node temp2 =temp1; if(temp1 == null) { System.out.println("QUEUE is empty"); check = true; } else if( temp1==myFront) { check =true; temp1=null; myFront=null; } else if( temp1.next ==myFront) { check =true; temp1.next=null; myFront=temp1; } else { temp1=temp1.next; } } } public static void main(String[] args) { Queue Q = new Queue(); // insert each value 1 through 5 onto thequeue for(int x = 1; x