Queue in Java | Priority Queue Java | Java Queue FIFO – Part 2

Queue in Java chapter is an immediate successor of Java Collections Framework that we had seen earlier. Make sure you have completely understood List before proceeding to learn about Java Queue FIFO.

As per the hierarchy that we have seen for JCF, queue interface stands as our next topic.

Queue in Java

Generally speaking, what do you really mean by queue? A line, right? You would know, now wouldn’t you? How many times in your life have you been forced to stand in a barely moving queue. So what was it like? Not the experience. I know it must have sucked. I mean the behaviour of the queue?

If you might remember the first person to enter the queue is the first to get out too once his/her job is done. Such a kind of setup of “first in first out” is also popularly abbreviated as FIFO. So with that, we have established that a queue follows a FIFO.

A Queue in Java is no different. It follows FIFO meaning it orders elements on the basis of first in first out. So the first element is removed first and the last element gets removed last.

Queue Interface

As you might have already guessed Queue in Java is an Interface that extends Collection Interface. There are only six methods in here and they are:

1. add(Object e)
2. offer(Object e)
3. element()
4. peek()
5. poll()
6. remove()

The last four methods namely, element(), peek(), poll() and remove() more or less do the same thing – retrieves the head of the queue. Out of these four, the last two namely: poll() and remove() also remove the head from the queue.

NOTE: A queue doesn’t allow the insertion of null elements. Duplicates are allowed in queue.

Since we cannot instantiate an interface, we will use one of its inheriting classes to see all the aforementioned methods in an example. There are two classes that implement Queue interface and they are:

• LinkedList
• PriorityQueue

So writing:

Queue q = new LinkedList();

or

Queue q = new PriorityQueue();

would be both correct.

One of the crucial classes that inherit Queue Interface’s methods is PriorityQueue which is our next topic.

Priority Queue Java Class

Priority Queue Java or PriorityQueue Class is one of those classes that implement Queue interface. It extends AbstractQueue class which in turn implements Queue to rake in its benefits.

Here’s a hierarchical diagram explaining things in a much better way:

PriorityQueue Class has the facility to use Queue in Java. However, surprisingly it does not order around elements in FIFO manner. It orders elements based on element’s natural ordering or based on the supplied comparator.

PriorityQueue Constructors and Methods

Here are the constructors of PriorityQueue that you could use:

1. PriorityQueue()
2. PriorityQueue(Collection c)
3. PriorityQueue(int capacity)
4. PriorityQueue(int capacity, Comparator comparator)
5. PriorityQueue(PriorityQueue p)
6. PriorityQueue(SortedSet s)

The methods of PriorityQueue class you can use are:

1. add(Object e)
2. clear()
3. comparator()
4. contains(Object o)
5. iterator()
6. offer(Object e)
7. peek()
8. poll()
9. remove(Object o)
10. size()
11. toArray()
12. toArray(T[] a)

Priority Queue Java Example

Here an example would be helpful:

PriorityQueue<Integer>q = new PriorityQueue<Integer>(5); 
q.add(23); 
q.add(1); 
q.add(3); 
q.add(7);
q.offer(6);         // does the same thing as add
System.out.println(q);

Notice here offer() method of Queue Interface does the same thing as add(). If you run the program above, you will get:

[1, 6, 3, 23, 7]

As you can see the elements are ordered as per their natural ordering. It doesn’t follow any FIFO here.

Let’s see what other methods we can put up in there to see what they do. Append the following code to the above code:

System.out.println("Head of the queue: " + q.poll());
System.out.println(q); 
q.clear(); 
System.out.println(q);

Poll as we had learned earlier helps in extracting the head of the queue by removing it. The method clear() will simply remove everything from the list. Here’s the result you will get now:

[1, 6, 3, 23, 7]
Head of the queue: 1
[3, 6, 7, 23]
[]

As you have noticed already that the ordering is kind of naturally done for you. It might be cumbersome for you. You could choose to use a method called comparator() to provide your own ordering. If there’s no comparator provided and the ordering is innate, it will give you a result as null. Like if you augment the following in the above code:

Comparator c = q.comparator(); 
System.out.println(c);

If you run it now you will get:

null

Other methods are pretty much the same that we had seen in ArrayList and LinkedList earlier. So I am not going to describe them all over again. Of course, you can always go back to see what does what.

Deque Interface

Moving on to the main course now. It is the Deque (pronounce it as Deck because that’s how the cool kids do) interface. It is a double ended queue. That’s what it stands for too. What is a double ended queue, you ask?

Well it is a queue that allows us to push elements from both ends. That didn’t sound right.

I mean take a look at this diagram and see for yourself:

Here you can enter an element from front or from the rear end. Also, you can order something to be removed from either the front side or the rear.

So deque interface is basically a linear collection that allows element insertion and removal from both its ends. It is different from queue in java in that respect.

When we will see the example things would be much clearer.

Methods of Deque

Deque methods can be classified under three different categories.

1. Insert                –     addFirst(), offerFirst(), addLast(), offerLast()
2. Remove           –     removeFirst(), pollFirst(), removeLast(), pollLast()
3. Retrieve           –     getFirst(), peekFirst(), getLast(), peekLast()

So to list all of its methods down here:

1. add(Object e)
2. addFirst()
3. offerFirst()
4. addLast()
5. offerLast()
6. removeFirst()
7. pollFirst()
8. removeLast()
9. pollLast()
10. getFirst()
11. peekFirst()
12. getLast()
13. peekLast()
14. contains(Object o)
15. descendingIterator()
16. element()
17. iterator()
18. offer(Object e)
19. peek()
20. poll()
21. pop()
22. push(Object e)
23. remove()
24. remove(Object o)
25. removeFirstOccurrence(Object o)
26. removeLastOccurrence(Object o)
27. size()

Since we cannot instantiate an interface we must use some concrete classes to do that for us. The following two classes come in handy:

• LinkedList
• ArrayDeque

So choosing to use either:

Deque d = new LinkedList();

or

Deque d = new ArrayDeque();

would be both fine.

LinkedList is something we have already seen. We will focus on the second kind.

ArrayDeque in Java

ArrayDeque is a class that implements Deque. It gives you the ability to incorporate resizable-arrays. It extends AbstractCollection class.

Here’s its hierarchical diagram to make you understand where it stands in Java Collections Framework.

You can add and remove elements from both sides since it implements deque. It doesn’t allow null elements as was the case with List. Duplicates are fine. It is also not thread safe.

ArrayDeque is faster than LinkedList and has no capacity restrictions.

Constructors and Methods of ArrayDeque

Let’s take a look at its constructors:

1. ArrayDeque()
2. ArrayDeque(Collection c)
3. ArrayDeque(int numElements)

Here are the methods that it uses:

1. add(Object e)
2. addFirst()
3. addLast()
4. clear()
5. clone()
6. contains(Object o)
7. descendingIterator()
8. element()
9. getFirst()
10. getLast()
11. isEmpty()
12. iterator()
13. offer(Object e)
14. offerFirst()
15. offerLast()
16. peek()
17. peekFirst()
18. peekLast()
19. poll()
20. pollFirst()
21. pollLast()
22. pop()
23. push(Object e)
24. remove()
25. remove(Object o)
26. removeFirst()
27. removeFirstOccurrence(Object o)
28. removeLast()
29. removeLastOccurrence(Object o)
30. size()
31. toArray()
32. toArray(T[] a)

An example here would be awesome now:

ArrayDeque<Integer>d = new ArrayDeque<Integer>(); 
d.add(23); 
d.add(1); 
d.addFirst(3); 
d.add(7); 
d.addLast(3); 
System.out.println(d); 
System.out.println("Head of the queue: " + d.poll()); 
System.out.println(d);
System.out.println(d.peekFirst()); 
System.out.println(d.getLast());

Print the above and you will get:

[3, 23, 1, 7, 3]
Head of the queue: 3
[23, 1, 7, 3]
23
3

I think all the other methods we have seen one way or the other. Rest are pretty simple to understand. Experiment away soldier!

We are yet to find out about Set, that’s one of the most crucial sections of JCF. Yes there’s going to be a Part 3 for this punishing section and it is going to be all about Set.

You can’t rush into things, can you?

Farewell peeps.