Java Queue Interface

The Java Queue interface is part of the Java Collections Framework and represents a data structure that allows elements to be inserted at the rear end and removed from the front end. The Queue interface extends the Collection interface and adds methods for enqueueing, dequeuing, and accessing the element at the front of the queue.

Here are some of the methods provided by the Queue interface:

add(E e): Adds the specified element to the rear of the queue.
offer(E e): Adds the specified element to the rear of the queue, returning true if successful, or false if the queue is full.
remove(): Removes and returns the element at the front of the queue, throwing an exception if the queue is empty.
poll(): Removes and returns the element at the front of the queue, or returns null if the queue is empty.
element(): Returns the element at the front of the queue without removing it, throwing an exception if the queue is empty.
peek(): Returns the element at the front of the queue without removing it, or returns null if the queue is empty.

Java provides several classes that implement the Queue interface, including LinkedList and ArrayDeque. Developers can use these implementations to create queues of different types based on their requirements.

Queue Interface Declaration:

Here is the declaration of the Queue interface in Java:

public interface Queue<E> extends Collection<E> {
    // Inserts the specified element into this queue if it is possible to do so
    // immediately without violating capacity restrictions.
    boolean add(E e);

    // Inserts the specified element into this queue if it is possible to do so
    // immediately without violating capacity restrictions.
    boolean offer(E e);

    // Retrieves and removes the head of this queue.
    E remove();

    // Retrieves and removes the head of this queue, or returns null if this queue
    // is empty.
    E poll();

    // Retrieves, but does not remove, the head of this queue.
    E element();

    // Retrieves, but does not remove, the head of this queue, or returns null if
    // this queue is empty.
    E peek();
}

As mentioned earlier, the Queue interface extends the Collection interface, which means that all the methods of the Collection interface are also available in the Queue interface. The type parameter E represents the type of elements that the queue can hold.

Methods of Java Queue Interface:

Here are the methods provided by the Java Queue interface:

add(E e): Inserts the specified element e into the queue if it is possible to do so immediately without violating capacity restrictions. This method throws an IllegalStateException if the queue is full.
offer(E e): Inserts the specified element e into the queue if it is possible to do so immediately without violating capacity restrictions. This method returns true if the element was added successfully, or false if the queue is full.
remove(): Retrieves and removes the element at the front of the queue. This method throws a NoSuchElementException if the queue is empty.
poll(): Retrieves and removes the element at the front of the queue, or returns null if the queue is empty.
element(): Retrieves, but does not remove, the element at the front of the queue. This method throws a NoSuchElementException if the queue is empty.
peek(): Retrieves, but does not remove, the element at the front of the queue, or returns null if the queue is empty.

Note that all of these methods are optional operations. Some implementations of the Queue interface may not support all of these methods, and may throw an UnsupportedOperationException if an unsupported operation is attempted.

Features of a Queue:

A queue is a data structure that follows the First-In-First-Out (FIFO) principle, meaning that the first element that is added to the queue is the first one to be removed. Here are some of the key features of a queue:

Enqueue: A queue allows for elements to be added at the rear end of the queue. This operation is also known as “enqueue”.
Dequeue: A queue allows for elements to be removed from the front end of the queue. This operation is also known as “dequeue”.
Peek: A queue allows for the front element to be examined without removing it from the queue. This operation is also known as “peek”.
Size: A queue keeps track of the number of elements it contains.
Capacity: A queue may have a fixed capacity, meaning that it can only hold a certain number of elements at a time. When the queue is full, attempting to enqueue an element may cause an error.
Blocking: Some implementations of a queue may be blocking, meaning that attempting to dequeue an element from an empty queue will cause the thread to block until an element becomes available.
Priority: Some implementations of a queue may be priority-based, meaning that elements are dequeued in order of priority rather than in the order they were added.

Queues are useful in many applications, such as process scheduling, event-driven programming, and message passing. They are often implemented using arrays or linked lists, and there are many variations of queues that have different features and characteristics.

PriorityQueue Class:

The PriorityQueue class in Java is an implementation of the Queue interface that provides priority-based ordering for elements. The elements in a PriorityQueue are ordered according to their natural ordering (as defined by the Comparable interface) or by a custom Comparator that is provided at the time of creation.

The PriorityQueue class is defined in the java.util package and extends the AbstractQueue class. Here is the declaration of the PriorityQueue class:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable {
    // Constructors
    public PriorityQueue();
    public PriorityQueue(int initialCapacity);
    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator);
    public PriorityQueue(Collection<? extends E> c);

    // Queue methods
    public boolean add(E e);
    public boolean offer(E e);
    public E remove();
    public E poll();
    public E element();
    public E peek();

    // Other methods
    public int size();
    public void clear();
    public boolean contains(Object o);
    public boolean remove(Object o);
    public Object[] toArray();
    public <T> T[] toArray(T[] a);
}

The PriorityQueue class provides several constructors that allow for the creation of a priority queue with different initial capacities and custom comparators. The PriorityQueue class also provides methods for adding, removing, and examining elements in the queue, as well as methods for determining the size of the queue, clearing the queue, and converting the queue to an array.

When elements are added to a PriorityQueue, they are automatically ordered according to their natural ordering or the ordering specified by the custom Comparator. When elements are removed from the queue, they are removed in order of priority, with the highest priority elements being removed first. The PriorityQueue class is often used in applications where elements need to be processed in order of priority, such as task scheduling or event processing.

PriorityQueue Class Declaration:

Here is the declaration of the PriorityQueue class in Java:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable {
    // Constructors
    public PriorityQueue();
    public PriorityQueue(int initialCapacity);
    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator);
    public PriorityQueue(Collection<? extends E> c);

    // Queue methods
    public boolean add(E e);
    public boolean offer(E e);
    public E remove();
    public E poll();
    public E element();
    public E peek();

    // Other methods
    public int size();
    public void clear();
    public boolean contains(Object o);
    public boolean remove(Object o);
    public Object[] toArray();
    public <T> T[] toArray(T[] a);
}

The PriorityQueue class is a generic class, and the type parameter E represents the type of elements that the queue will hold. The class extends the AbstractQueue class and implements the Queue interface.

The PriorityQueue class provides several constructors:

PriorityQueue(): Creates a new empty priority queue with the default initial capacity of 11.
PriorityQueue(int initialCapacity): Creates a new empty priority queue with the specified initial capacity.
PriorityQueue(int initialCapacity, Comparator<? super E> comparator): Creates a new empty priority queue with the specified initial capacity and comparator.
PriorityQueue(Collection<? extends E> c): Creates a new priority queue that contains all the elements in the specified collection.

The PriorityQueue class also provides methods for adding, removing, and examining elements in the queue:

add(E e): Inserts the specified element into the queue. This method throws an IllegalStateException if the element cannot be added to the queue.
offer(E e): Inserts the specified element into the queue. This method returns true if the element was added successfully, or false if the queue is full.
remove(): Retrieves and removes the head of the queue. This method throws a NoSuchElementException if the queue is empty.
poll(): Retrieves and removes the head of the queue, or returns null if the queue is empty.
element(): Retrieves, but does not remove, the head of the queue. This method throws a NoSuchElementException if the queue is empty.
peek(): Retrieves, but does not remove, the head of the queue, or returns null if the queue is empty.

In addition, the PriorityQueue class provides several other methods, such as size(), clear(), contains(), remove(), and toArray(), which allow for the manipulation and examination of the elements in the queue.

Java PriorityQueue Example:

Here’s an example that demonstrates the use of PriorityQueue in Java:

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Create a new priority queue with initial capacity of 5
        PriorityQueue<Integer> pq = new PriorityQueue<>(5);

        // Add elements to the queue
        pq.offer(4);
        pq.offer(1);
        pq.offer(3);
        pq.offer(2);
        pq.offer(5);

        // Print the contents of the queue
        System.out.println("Contents of the queue: " + pq);

        // Retrieve and remove the head of the queue
        int head = pq.poll();
        System.out.println("Head of the queue: " + head);

        // Print the contents of the queue again
        System.out.println("Contents of the queue: " + pq);

        // Retrieve, but do not remove, the head of the queue
        int peek = pq.peek();
        System.out.println("Peek of the queue: " + peek);

        // Print the contents of the queue again
        System.out.println("Contents of the queue: " + pq);
    }
}

In this example, we first create a new PriorityQueue with an initial capacity of 5. We then add 5 elements to the queue using the offer() method. The println() method is used to print the contents of the queue before and after we remove the head of the queue using the poll() method. We also retrieve the head of the queue without removing it using the peek() method.

When we run this program, the following output is produced:

Contents of the queue: [1, 2, 3, 4, 5]
Head of the queue: 1
Contents of the queue: [2, 4, 3, 5]
Peek of the queue: 2
Contents of the queue: [2, 4, 3, 5]

As we can see from the output, the elements in the queue are automatically ordered in ascending order (according to their natural ordering), and the poll() method removes the head of the queue (which is the smallest element). The peek() method retrieves the head of the queue without removing it, and the contents of the queue are updated accordingly.

Java PriorityQueue Example: Book

Here’s an example that demonstrates the use of PriorityQueue in Java to sort a collection of books based on their title:

import java.util.PriorityQueue;

public class Book implements Comparable<Book> {
    private String title;
    private String author;

    public Book(String title, String author) {
        this.title = title;
        this.author = author;
    }

    public String getTitle() {
        return title;
    }

    public String getAuthor() {
        return author;
    }

    @Override
    public int compareTo(Book other) {
        return this.title.compareTo(other.title);
    }

    @Override
    public String toString() {
        return title + " by " + author;
    }

    public static void main(String[] args) {
        // Create a new priority queue of books
        PriorityQueue<Book> books = new PriorityQueue<>();

        // Add books to the queue
        books.offer(new Book("The Great Gatsby", "F. Scott Fitzgerald"));
        books.offer(new Book("To Kill a Mockingbird", "Harper Lee"));
        books.offer(new Book("1984", "George Orwell"));
        books.offer(new Book("The Catcher in the Rye", "J.D. Salinger"));
        books.offer(new Book("Pride and Prejudice", "Jane Austen"));

        // Print the sorted books
        while (!books.isEmpty()) {
            System.out.println(books.poll());
        }
    }
}

In this example, we define a Book class that implements the Comparable interface, allowing us to sort a collection of books based on their title. We then create a new PriorityQueue of books and add several books to the queue using the offer() method.

The compareTo() method compares two books based on their titles using the compareTo() method of the String class. The toString() method is overridden to return a string representation of a book.

Finally, we print the sorted books by retrieving and removing each book from the queue using the poll() method until the queue is empty.

When we run this program, the books are printed in alphabetical order based on their titles:

1984 by George Orwell
Pride and Prejudice by Jane Austen
The Catcher in the Rye by J.D. Salinger
The Great Gatsby by F. Scott Fitzgerald
To Kill a Mockingbird by Harper Lee