In this post, we dig in the Queue interface and then into PriorityQueue implementation of the Queue interface with examples. Here we'll see the basic concept of priority queue and its methods in detail.
Queue
In general, a queue is a line of people or things waiting to be handled, usually in sequential order starting at the beginning or top of the line or sequence.
In computer technology, a queue is a sequence of work objects that are waiting to be processed.
Queue Interface
A Queue is designed to hold a list of "to-dos," or things to be processed in some way. Although other orders are possible, queues are typically thought of as FIFO (first-in,first-out).
Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value either null or false, depending on the operation.
The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues\
The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.
The element() and peek() methods return, but do not remove, the head of the queue.
Queue implementations generally do not allow insertion of null elements, although some implementations, such as LinkedList, do not prohibit insertion of null
PriorityQueue
An unbounded priority queue based on a priority heap. The purpose of a PriorityQueue is to create a "priority-in, priority out" queue as opposed to a typical FIFO queue.
A PriorityQueue's elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator. In either case, the elements' ordering represents their relative priority.
Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies
Let's see an example of Priority Queue
Let's see an another example of priority queue with Comparator with out own ordering instead of natural ordering
This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Let see this with the help of another example
Sample Output
Natural order
2
3
5
6
8
9
64
Iterator:
2
3
6
8
5
9
64
Example of priority Queue sorting by String Length
Sample Output
olx
java
Myntra
flipkart
We'll see an example of how PriorityQueue use in real world example. The order of patients to be treated by a doctor can be determined by checking if it's a emergency case or not.
Queue
In general, a queue is a line of people or things waiting to be handled, usually in sequential order starting at the beginning or top of the line or sequence.
In computer technology, a queue is a sequence of work objects that are waiting to be processed.
Queue Interface
A Queue is designed to hold a list of "to-dos," or things to be processed in some way. Although other orders are possible, queues are typically thought of as FIFO (first-in,first-out).
Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value either null or false, depending on the operation.
Operation | Throws exception | Return special value |
Insert | add( e ) | offer ( e ) |
Remove | remove (e ) | poll ( e ) |
Examine | element (e ) | peek ( e ) |
The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues\
The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.
The element() and peek() methods return, but do not remove, the head of the queue.
Queue implementations generally do not allow insertion of null elements, although some implementations, such as LinkedList, do not prohibit insertion of null
PriorityQueue
An unbounded priority queue based on a priority heap. The purpose of a PriorityQueue is to create a "priority-in, priority out" queue as opposed to a typical FIFO queue.
A PriorityQueue's elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator. In either case, the elements' ordering represents their relative priority.
- A priority queue does not permit null elements.
- A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
- A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically.
Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies
Let's see an example of Priority Queue
Sample Output
I hope, now it clear how to use priority queue and it's methods.head of queue: 2 2 3 5 6 8 9 64 poll : null peek : null 2 3 5 6 8 9 64 Exception in thread "main" java.util.NoSuchElementException at java.util.AbstractQueue.remove(Unknown Source) at PriorityQueueDemo.main(PriorityQueueDemo.java:22)
Let's see an another example of priority queue with Comparator with out own ordering instead of natural ordering
Sample Output
head of queue: 64
64
9
8
6
5
3
2
Exception in thread "main" java.lang.NullPointerException
at java.util.PriorityQueue.offer(Unknown Source)
at PriorityQueueComparatorDemo.main(PriorityQueueComparatorDemo.java:17)
This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Let see this with the help of another example
Sample Output
Natural order
2
3
5
6
8
9
64
Iterator:
2
3
6
8
5
9
64
Sample Output
olx
java
Myntra
flipkart
If you know anyone who has started learning Java, why not help them out! Just share this post with them. Thanks for studying today!...
Thanks for sharing this article. This article is really very helpful.
ReplyDeleteJava training