Implement a Queue Data Structure in Java using LinkedList

The Queue is an interface in Java which extends Collection interface. In this tutorial, we will learn how to use Queue to implement a Queue data structure in Java. Queue is a FIFO or First in first out data structure. That means it will always insert an element to the end of the list and remove an element from the beginning of the list.

Since it is only an interface, we need one class to create one Queue object. To implement this, we can use either one LinkedList or one Priority Queue or one PriorityBlockingQueue. LinkedList and Priority Queue for Queue implementation are not thread safe. But PriorityBlockingQueue is thread safe. In this example, we will learn Queue implementation by using LinkedList.

One more thing we need to note that all Queue implementation are not FIFO or First in First Out. For example, Prioriry Blocking Queue order elements according to a comparator or by using natural ordering.

We will check the following methods of Queue in this example :

1. element() : Retrieves but doesn’t remove the head of the queue. If the queue is empty it throws NoSuchElementException.
2. peek() : Retrieves but doesn’t remove the head of the queue. If the queue is empty it returns null.
3. remove() : Retrieves and removes the head of the queue. If the queue is empty it throws NoSuchElementException.
4. poll() : Retrieves and removes the head of the queue. If the queue is empty it returns null.
5. add(E e) : It inserts an element to the given queue. On success, it returns true. If no space available, it throws an IllegalStateException.
6. size() : Get the size of the Queue.

Let’s take a look into the program :

Java program to implement Queue using LinkedList :

 import java.util.*;

public class Main {

    //1
    private static void printCurrentQueue(Queue queue) {
        System.out.println("Current Queue : " + queue);
    }

    //2
    private static void printNewLine() {
        System.out.println();
    }

    public static void main(String[] args) {
        //3
        Queue sampleQueue = new LinkedList<>();

        //4
        sampleQueue.add("sun");
        sampleQueue.add("mon");
        sampleQueue.add("tue");
        sampleQueue.add("wed");
        sampleQueue.add("thu");
        sampleQueue.add("fri");
        sampleQueue.add("sat");
        
        //5
        printCurrentQueue(sampleQueue);
        printNewLine();

        //6
        String element = sampleQueue.element();
        System.out.println("First Element : " + element);
        printCurrentQueue(sampleQueue);
        printNewLine();

        //7
        String peekElement = sampleQueue.peek();
        System.out.println("Peek element : " + peekElement);
        printCurrentQueue(sampleQueue);
        printNewLine();

        //8
        String removedElement = sampleQueue.remove();
        System.out.println("Removed element : " + removedElement);
        printCurrentQueue(sampleQueue);
        printNewLine();

        //9
        String pollElement = sampleQueue.poll();
        System.out.println("Poll element : " + pollElement);
        printCurrentQueue(sampleQueue);
        printNewLine();

        //10
        sampleQueue.add("Days");
        System.out.println("After adding a new element :");
        printCurrentQueue(sampleQueue);
        printNewLine();

        //11
        System.out.println("Final count of the queue : " + sampleQueue.size());

    }

}

Output :

Current Queue : [sun, mon, tue, wed, thu, fri, sat]

First Element : sun
Current Queue : [sun, mon, tue, wed, thu, fri, sat]

Peek element : sun
Current Queue : [sun, mon, tue, wed, thu, fri, sat]

Removed element : sun
Current Queue : [mon, tue, wed, thu, fri, sat]

Poll element : mon
Current Queue : [tue, wed, thu, fri, sat]

After adding a new element :
Current Queue : [tue, wed, thu, fri, sat, Days]

Final count of the queue : 6

Explanation :

The commented numbers in the above program denotes the step number below :

1. printCurrentQueue(Queue queue) is an utility function. We will pass one Queue with string elements to this function and it will print out that queue.
2. printNewLine() is also an utility function. It will print one blank line.
3. Create one Queue that can hold string and the type of the Queue is LinkedList.
4. Add elements to the queue. We are adding all days of the week to the queue.
5. Print the queue with a blank line.
6. Use the element() method to get the first element and then print out the queue. It will not remove the element.
7. Use the peek() method to get the first element. It will also not remove the first element.
8. Use the remove() method to get the first element and it will remove the first element. Print out the queue.
9. Use the poll() method to get the first element and it will remove the first element. Print out the queue.
10. Add one element using add(E e) method and print out the queue. It will add one element to the last position.
11. Use the size() method to print out the size of the queue.

Leave a Reply