Various Operation on Queue using Linked List in Java

We keep track of front and rear pointers in a queue data structure. The head of the line points to the first item, and the back to the last.

Rear is moved to the next node by the operation enQueue(), which also adds a new node after it.

deQueue() This operation advances the front node to the subsequent node after removing the front node.

Approach:

To implement the queue using a linked list, follow these steps:

• Next, make a Struct QNode with the data elements QNode* and integer data.
• A parameterized constructer that sets the data to equal the integer value x and then next as NULL.
• A struct Queue with the data elements QNode front and rear should be created.
• The front and rear are set to NULL by default constructor Queue().
• Operation to enqueue with parameter x:
• Set front and rear to temp and return after initialising QNode* temp with data = x if rear is set to NULL.
• If not, place the rear's next to the temp before moving the rear to the temp variable.
• If not, place the rear's next to the temp before moving the rear to the temp variable. Dequeue Operation:
• If front is set to NULL, return from the dequeue operation.
• Set front to its next while initialising QNode* temp with front.
• Set rear to NULL if front is equal to NULL.
• Delete the temp variable

Insertion

If the queue is empty, the insert operation appends it by adding an element to the end of it. In order to make the new element the last one in the queue, we place it into an empty queue. The statement front = NULL is true in this instance. The front and rear pointers' next pointers will now both point to NULL, making the new element the only element in the queue. The condition is no longer true if front = NULL. It is necessary to update the end pointer rear so that the next pointer of rear now points to the new node next pointer.

Deletion

The element that was first inserted out of all the queue elements is removed during deletion operations. We must find whether the queue is empty or not. The condition for this is (front == NULL) if it becomes true then queue is empty, then we just print underflow on the console. If not, we shall remove the object that the pointer front is pointing at. Copy the node pointed by the front pointer into the pointer next for this purpose. After that, move the front pointer, point to the node after it, and release the node that the node next pointed at.

Queue implementation using Linked List

// Node creation to store new values using class QNode1
class QNode1 {
int k1 ;
QNode1 next ;


public QNode1 ( int k1 )
{
this . k1 = k1 ;
this . next = null ;
}
}
class QueueImplementation {
QNode1 f, r ;
public QueueImplementation ( ) { this.f = this.r = null; }
void enqueue ( int k1 )
{
QNode1 temp = new QNode1 ( k1 ) ;
if (this . r == null ) {
this . f = this . r = temp ;
return ;
}
this . r . next = temp ;
this . r = temp ;
}
void dequeue()
{ if ( this . f == null)
return ;
QNode1 temp = this.f;
this.f = this.f.next;
if ( this . f == null )
this . r = null ;
}
}


// Main section of the program from where execution begins
public class Main {
public static void main ( String [ ] args )
{
QueueImplementation q1 = new QueueImplementation ( ) ;
q1 .enqueue ( 30 ) ;
q1 .enqueue ( 40 ) ;
q1 .dequeue () ;
q1 .enqueue ( 70 ) ;
q1 .dequeue () ;
q1 .enqueue ( 10 ) ;
q1 .enqueue ( 80 ) ;
q1 .dequeue ( ) ;
System . out . println(" Front  of the queue : " + q1 . f . k1 ) ;
System . out . println ( " Rear of the queue : " + q1 . r . k1 ) ;
}
}

Output