Queue Using Linked List

Image by Richard Mcall from Pixabay

AIM

To Implement a Q using LinkedList.

You need to implement enqueue and dequeue function.

When getHeadOfLinkedList is called, return the head of the linked list.

When enqueue is called, insert the items in list at the head.

When the Q is empty and dequeue is called return 0.

When the Q is empty, GetMax and GetMin should return 0.

GetMin should return the MIN element in the Q and it should NOT remove the element out.

I have published an ebook. A compilation of 100 Java(Interview)Programming problems which have been solved . I have given clear explanation and the code in the book. Believe me when I say, this will kick start you to achieve the job at your dream company.

Click on this link to get you to the landing page. It is completely free when you use kindle amazon. Take a look at it.

INPUT AND OUTPUT:

ENQUEUE 4

ENQUEUE 6

ENQUEUE 8

DEQUEUE

Output:

GETMAX should return: 6

Code

public class LLStack implements LLStackQInterface{

SintNode head = null,tail=null;

@Override

public void enQueue(int num) {

SintNode n=new SintNode(num);

if(head==null)

{

head=n;

tail=n;

}

else

{

tail.nextNode=n;

tail=n;

}

}

@Override

public int deQueue() {

int a=0;

if(head!=null)

{

a=head.num;

head=head.nextNode;

}

return a;

}

@Override

public SintNode getHeadOfLinkedList() {

return head;

}

@Override

public int getMin(){

if(head==null)

{

return 0;

}

int min=99999;

SintNode curr=head;

while(curr!=null)

{

if(curr.num<min)

{

min=curr.num;

}

curr=curr.nextNode;

}

return min;

}

}

}

Explanation

This is a basic linked list concept that is used to create a queue data structure.

Queue by default works based on the first come first serve strategy(FIFO).

When a data element is inserted a node is created and it is inserted to the tail of the existing list if there is a list already.

If there is no existing list the node is created and made as the head of the list.

Enqueue function adds a node to the list and dequeue function removes the top element from the lists.

If there are no elements in the list then the dequeue function returns 0 as the result.

Algorithm

Algorithm for en queue:

• a new node is created using SintNode n=new SintNode(num) with the num initialized in the node.

• If the head of the list is null then the node is made the head and tail of the list.

• If there is a existing list the new node is added as the next node to the tail and the inserted node is made as the tail node of the list.

Algorithm for dequeue:

• If the list is empty then the dequeue function returns zero as the result.

• Else the node element stored in the head is returned and the next node is made as the head of the list.

Algorithm for getMin():

• A variable min is initialized with 0 as the value.

• The loop continues until the list is not null.

• If the curr.num value is less than the min value then min is assigned with the curr.num value.

  • The min variable value is returned as the output.

Conclusion

Well if you have reached this far. I am confident in one of two things. Either you would have understood the problem. Or you are just scrolling just to see where I have completed my rambling of code.

Well if you are the first Please follow House of Codes. It will be useful for many coding Interviews.

And if you are the latter. Please click on the follow button. Because between you and me I am just looking for followers :).

Author: Architha Harinath
Editor : Akshay Ravindran

Code -> Understand-> Repeat is my motto. I am a Data Engineer who writes about everything related to Data Science and Interview Preparation for SDE.

Love podcasts or audiobooks? Learn on the go with our new app.