5. Major Queue’s Implementations
- Part II: Understanding Queue API Structure1. Understanding Queue interface’s API Structure
2. Understanding Deque interface’s API Structure
3. Understanding BlockingQueue interface’s API Structure
4. Understanding BlockingDeque interface’s API Structure
- Part III: Performing Operations on Queue Collections1. Creating a New Queue Instance
2. Adding New Elements to the Queue
3. Removing the Head of the Queue
4. Examining the Head of the Queue
5. Iterating over Elements in the Queue
Part I: Understanding Queue Concepts+ LinkedList: this class implements both List and Deque interface, thus having hybrid characteristics and behaviors of list and queue. Consider using a LinkedList when you want fast adding and fast removing elements at both ends, plus accessing elements by index.
+ PriorityQueue: this queue orders elements according to their natural ordering, or by a Comparator provided at construction time. Consider using a PriorityQueue when you want to take advantages of natural ordering and fast adding elements to the tail and fast removing elements at the head of the queue.
+ ArrayDeque: a simple implementation of the Deque interface. Consider using an ArrayDeque when you want to utilize features of a double ended queue without list-based ones (simpler than a LinkedList).
+ ArrayBlockingQueue: this is a blocking queue backed by an array. Consider using an ArrayBlockingQueue when you want to use a simple blocking queue that has limited capacity (bounded).
+ PriorityBlockingQueue: Use this class when you want to take advantages of both PriorityQueue and BlockingQueue.
+ DelayQueue: a time-based scheduling blocking queue. Elements added to this queue must implement the Delayed interface. That means an element can only be taken from the head of the queue when its delay has expired.
Because the Queue interface extends the Collection interface, all Queue implementations have basic operations of a collection:Type of operation | Throws exception | Returns special value |
Insert | add(e) | offer(e) |
Remove | remove() | poll() |
Examine | element() | peek() |
Type of operation | First element | Last element |
Insert | addFirst(e) offerFirst(e) | addLast(e) offerLast(e) |
Remove | removeFirst() pollFirst() | removeLast() pollLast() |
Examine | getFirst() peekFirst() | getLast() peekLast() |
Type of operation | Throws exception | special value | blocks | times out |
Insert | add(e) | offer(e) | put(e) | offer(e, time, unit) |
Remove | remove() | poll() | take() | poll(time, unit) |
Examine | element() | peek() | N/A | N/A |
First Element (head) | ||||
| Throws exception | special value | blocks | times out |
Insert | addFirst(e) | offerFirst(e) | putFirst(e) | offerFirst(e, time, unit) |
Remove | removeFirst() | pollFirst() | takeFirst() | pollFirst(time, unit) |
Examine | getFirst() | peekFirst() | N/A | N/A |
Last Element (tail) | ||||
| Throws exception | special value | blocks | times out |
Insert | addLast(e) | offerLast(e) | putLast(e) | offerLast(e, time, unit) |
Remove | removeLast() | pollLast() | takeLast() | pollLast(time, unit) |
Examine | getLast() | peekLast() | N/A | N/A |
Queue<String> namesQueue = new LinkedList<>(); Deque<Integer> numbersDeque = new ArrayDeque<>(); BlockingQueue<String> waitingCustomers = new ArrayBlockingQueue<>(100);Most Queue implementations do not have restriction on capacity (unbounded queues), except the ArrayBlockingQueue, LinkedBlockingQueue and LinkedBlockingDeque classes. The following statement creates an ArrayBlockingQueue with fixed capacity of 200 elements:
BlockingQueue<String> waitingCustomers = new ArrayBlockingQueue<>(200);Also remember that we can use the copy constructor to create a new Queue instance from another collection. For example:
List<String> listNames = Arrays.asList("Alice", "Bob", "Cole", "Dale", "Eric", "Frank"); Queue<String> queueNames = new LinkedList<>(listNames); System.out.println(queueNames);Output:
[Alice, Bob, Cole, Dale, Eric, Frank]
Queue<String> queueNames = new LinkedList<>(); queueNames.add("Mary"); queueNames.add("John");When using an unbounded queue (no capacity restriction), the add() and offer() methods do not show the difference. However, when using a bounded queue, the add() method will throw an exception if the queue is full, while the offer() method returns false. The following example illustrates this difference:
Queue<Integer> queueNumbers = new ArrayBlockingQueue<>(3); queueNumbers.add(1); queueNumbers.add(2); queueNumbers.add(3); queueNumbers.add(4); // this line throws exceptionThe last line throws java.lang.IllegalStateException: Queue full because we declare the queue with capacity of 3 elements. Hence adding the 4th element results in an exception.However, we are safe when using the offer() method, as shown in the following code snippet:
Queue<Integer> queueNumbers = new ArrayBlockingQueue<>(3); System.out.println(queueNumbers.offer(1)); System.out.println(queueNumbers.offer(2)); System.out.println(queueNumbers.offer(3)); System.out.println(queueNumbers.offer(4));Output:
true true true falseThe following code snippet adds an element to the head and an element to the tail of a double ended queue (notice the type of the interface is used):
Deque<String> queueNames = new ArrayDeque<>(); queueNames.offer("Katherine"); queueNames.offer("Bob"); queueNames.addFirst("Jim"); queueNames.addLast("Tom"); System.out.println(queueNames);Output:
[Jim, Katherine, Bob, Tom]For blocking queue, use the put(e)or offer(e, time, unit) in case you want the current thread to wait until space becomes available in the queue. For example:
BlockingQueue<Integer> queueNumbers = new ArrayBlockingQueue<>(100); try { queueNumbers.put(2000); } catch (InterruptedException ie) { ie.printStackTrace(); }
Queue<String> queueCustomers = new LinkedList<>(); queueCustomers.offer("Jack"); String next = queueCustomers.remove(); System.out.println("Next customer is: "+ next); next = queueCustomers.remove(); // throws exceptionHere, the queue has only one element, so the first call to remove() working fine. However the subsequent invocation results in java.util.NoSuchElementException because the queue becomes empty.In contrast, the poll() method returns null if the queue is empty, as shown in the following example:
Queue<String> queueCustomers = new LinkedList<>(); queueCustomers.offer("Jack"); System.out.println("next: " + queueCustomers.poll()); System.out.println("next: " + queueCustomers.poll()); // returns nullOutput:
next: Jack next: nullThe following example removes the head element and tail element from a deque:
Deque<String> queueCustomers = new ArrayDeque<>(); queueCustomers.offer("Bill"); queueCustomers.offer("Kim"); queueCustomers.offer("Lee"); queueCustomers.offer("Peter"); queueCustomers.offer("Sam"); System.out.println("Queue before: " + queueCustomers); System.out.println("First comes: " + queueCustomers.pollFirst()); System.out.println("Last comes: " + queueCustomers.pollLast()); System.out.println("Queue after: " + queueCustomers);Output:
Queue before: [Bill, Kim, Lee, Peter, Sam] First comes: Bill Last comes: Sam Queue after: [Kim, Lee, Peter]For a blocking queue, use the take()or poll(time, unit)methods in case you want the current thread to wait until an element becomes available. For example:
BlockingQueue<String> queueCustomers = new ArrayBlockingQueue<>(100); queueCustomers.offer("Kathe"); try { String nextCustomer = queueCustomers.take(); } catch (InterruptedException ie) { ie.printStackTrace(); }
Queue<String> queueCustomers = new PriorityQueue<>(); queueCustomers.offer("Jack"); System.out.println("who's next: " + queueCustomers.poll()); // this returns null in case the queue is empty System.out.println("who's next: " + queueCustomers.peek()); // this throws exception in case the queue is empty System.out.println("who's next: " + queueCustomers.element());For a deque, use the getFirst() or peekFirst() methods to examine the first element, and getLast() or peekLast() to examine the last element. Here’s an example:
Deque<Integer> queueNumbers = new ArrayDeque<>(); queueNumbers.add(10); queueNumbers.add(20); queueNumbers.add(30); queueNumbers.add(40); System.out.println("first: " + queueNumbers.getFirst()); System.out.println("last: " + queueNumbers.peekLast());There’s no method for examining a blocking queue.
Queue<String> queueNames = new LinkedList<>(); queueNames.add("Dale"); queueNames.add("Bob"); queueNames.add("Frank"); queueNames.add("Alice"); queueNames.add("Eric"); queueNames.add("Cole"); queueNames.add("John"); for (String name : queueNames) { System.out.println(name); }Output:
Dale Bob Frank Alice Eric Cole JohnMore simply, using Lambda expression with forEach() method in Java 8:
queueNames.forEach(name -> System.out.println(name));The following example iterates over elements of a PriorityQueue which sorts elements by natural ordering:
Queue<String> queueNames = new PriorityQueue<>(); queueNames.add("Dale"); queueNames.add("Bob"); queueNames.add("Frank"); queueNames.add("Alice"); queueNames.add("Eric"); queueNames.add("Cole"); queueNames.add("John"); queueNames.forEach(name -> System.out.println(name));Output:
Alice Bob Cole Dale Eric Frank JohnAs you can see in the output, the elements are sorted in the alphabetic order (natural ordering of Strings).NOTE: Pay attention when using an iterator of a PriorityQueue, because it is not guaranteed to traverse the elements of the priority queue in any particular order.
- LinkedList
- ArrayDeque
- PriorityQueue
When you want to use a synchronized linked list, use the following code:List list = Collections.synchronizedList(new LinkedList<>());And consider using the PriorityBlockingQueue instead of the PriorityQueue when you want to use a synchronized priority queue.So far you have learned almost everything you need to know about Queue in Java. I hope you benefit from this tutorial. If you want to go further in Java programming, consider to learn this Java Masterclass course.