Queue in Java

Queues are an essential data structure in computer science and programming. They are commonly used to store and manage data in a first-in, first-out (FIFO) manner. In Java, the Queue interface is implemented by several classes, including LinkedList, PriorityQueue, and ArrayDeque.

Queue Interface

The Queue interface is a subinterface of the Collection interface, which is the root interface for all collection classes in Java. The Queue interface extends the Collection interface and adds methods specific to queues. The methods include:

1. add(E e): Adds the specified element to the end of the queue.
2. offer(E e): Adds the specified element to the end of the queue.
3. remove(): Removes and returns the element at the head of the queue.
4. poll(): Removes and returns the element at the head of the queue, or returns null if the queue is empty.
5. element(): Returns the element at the head of the queue without removing it.
6. peek(): Returns the element at the head of the queue without removing it, or returns null if the queue is empty.

LinkedList Class

LinkedList is a class in Java that implements the Queue interface. It is a doubly linked list, meaning that each node in the list contains a reference to both the previous and next nodes. LinkedList allows for fast insertion and deletion of elements at the beginning and end of the list. To create a LinkedList that implements the Queue interface, use the following code:

Queue queue = new LinkedList<>();

PriorityQueue Class

PriorityQueue is another class in Java that implements the Queue interface. It is an unbounded priority queue, meaning that it can grow dynamically as elements are added. The elements are ordered according to their natural ordering, or by a Comparator that is provided at the time of construction. To create a PriorityQueue that implements the Queue interface, use the following code:

Queue queue = new PriorityQueue<>();

ArrayDeque Class

ArrayDeque is a class in Java that implements the Deque interface, which is a subinterface of the Queue interface. It is a resizable array, meaning that it can grow dynamically as elements are added. ArrayDeque allows for fast insertion and deletion of elements at both the beginning and end of the deque. To create an ArrayDeque that implements the Queue interface, use the following code:

Queue queue = new ArrayDeque<>();

Using Queues in Java

Queues can be used in a variety of scenarios in Java programming. They are commonly used for implementing algorithms that require a FIFO data structure, such as breadth-first search (BFS) and depth-first search (DFS) in graph theory. Queues can also be used for implementing message queues in distributed systems, where multiple processes or threads need to communicate with each other by sending messages.

Here’s an example of using a Queue to implement BFS:

void bfs(Node start) {
Queue queue = new LinkedList<>();
Set visited = new HashSet<>();
queue.offer(start);
visited.add(start);

while (!queue.isEmpty()) {
    Node node = queue.poll();
    // process node
    for (Node neighbor : node.neighbors()) {
        if (!visited.contains(neighbor)) {
            queue.offer(neighbor);
            visited.add(neighbor);
        }
    }
}
}

In this example, the bfs() method implements BFS on a graph starting from a given start node. It uses a LinkedList to implement the Queue interface, and a HashSet to keep track of visited nodes. The bfs() method starts by adding the start node to the queue and marking it as visited. It then enters a loop that processes each node in the queue. For each node, it checks its neighbors and adds them to the queue if they haven’t been visited yet.