Here we are going to discuss the Java Queue interface. You’ll find out what Queue data structure is, how it is represented in Java, what methods are the most important for all queues. Also, what implementations of Queue are in Java language. After that, we take a closer look at the most important implementations and learn them with examples.
What does it mean? First of all, Java Queue is a part of the Collection Framework and implements Collection interface. So it supports all methods of Collection interface such as insertion, deletion and so on.
Queue implements Iterable interface, that allows an object to be the target of the "for-each loop" statement.
Queue data structure
A Queue is a linear abstract data structure with the particular order of performing operations — First In First Out (FIFO). That means you can add an element (or enqueue, put in the queue) only at the end of the structure, and take an element (dequeue or remove from the queue) only from its beginning. You may imagine Queue data structure very easily. It seems like a queue or a line of customers in real life. The customer that came first, is going to be served first as well. If you have four people in line in McDonalds or elsewhere, the first to line up will be the first to get the store. If the new customer comes, he/she will be the 5th in line to get hamburgers. So, while working with a queue, new elements are added to the end, and if you want to get an element, it will be taken from the beginning. This is the main principle of classical queue data structure work.Queue in Java
Queue in Java is an interface. According to Oracle documentation, Queue interface has 2 superinterfaces, 4 different interfaces that inherit from the queue, and an extremely impressive list of classes.Superinterfaces: Collection<E>, Iterable<E> All Known Subinterfaces: BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> All Known Implementing Classes: AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue |
Queue Methods Java
The Queue declares a number of methods. As interface’s methods they should be represented in all classes that implement Queue. The most important Queue Methods, Java:- Boolean offer() – inserts a new element into the queue if it is possible
- Boolean add(E e) – inserts a new element into the queue if it is possible. Returns true in case of success and throws an IllegalStateException if there is no space.
- Object poll() – retrieves and removes an element from the head of the. Returns null if the queue is empty.
- Object remove() – retrieves and removes an element from the head of the queue.
- Object peek() – retrieves, but doesn’t remove an element from the head of the queue. Returns null if the queue is empty.
- Object element() – retrieves, but doesn’t remove an element from the head of the queue.
Subinterfaces of Java Queue
Queue interface is inherited by 4 subinterfaces – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>. You may divide them into 3 groups: Deques, Blocking Queues and Transfer Queues with BlockingDeque belonging to the two first. Let's take a glimpse at these groups.Deques
Deque means Double-Ended Queue and supports addition or removal from either tail of the data as a queue (first-in-first-out/FIFO) or from the head as another popular data structure called stack (last-in-first-out/LIFO). Classes that implement Deque Interface: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.Blocking Queues
A blocking queue is a queue that blocks a thread in two cases:- thread is trying to get elements from an empty queue
- thread is trying to put elements in the full queue
Transfer Queues
TransferQueue interface extends BlockingQueue interface. However unlike the implementation of BlockingQueue interface queues, where threads can be blocked if the queue is empty (reading), or if the queue is full (writing), TransferQueue interface queues block the write stream until another stream retrieves the element. Use a transfer method for this. In other words, the implementation of BlockingQueue guarantees that the element created by the Producer must be in the queue, while the implementation of TransferQueue guarantees that the Producer element is "received" by the Consumer. There is only one official Java implementation of TransferQueue interface — LinkedTransferQueue.Java Queue Implementations
There are many classes that implement Queue interface:- AbstractQueue according to Queue Java 8 docs, this abstract class provides basic implementations of some Queue operations. It doesn’t allow null elements. There are 3 more methods add, remove, and element based on Queue classical offer, poll, and peek, respectively. However they throw exceptions instead of indicating failure via false or null returns.
- ArrayBlockingQueue — a fixed size FIFO blocking queue backed by an array
- ArrayDeque — resizable array implementation of the Deque interface
- ConcurrentLinkedDeque — an unbounded concurrent deque based on linked nodes.
- ConcurrentLinkedQueue — an unbounded thread-safe queue based on linked nodes.
- DelayQueue — a time-based scheduling queue backed by a heap
- LinkedBlockingDeque — the concurrent implementation of the Deque interface.
- LinkedBlockingQueue — an optionally bounded FIFO blocking queue backed by linked nodes
- LinkedList — doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null)
- LinkedTransferQueue — an unbounded TransferQueue based on linked nodes
- PriorityBlockingQueue — an unbounded blocking priority queue backed by a heap
- PriorityQueue — a priority queue based on the heap data structure
- SynchronousQueue — a blocking queue where each insert operation must wait for a corresponding remove operation by another thread, and vice versa.
LinkedList
Class LinkedList in Java implements List and Deque interfaces. So, it is a combination of List and Deque, a two-way queue, that supports adding and removing elements from both sides. In Java LinkedList is doubly-linked List: every element of List calls Node and contains an object and references to two neighboring objects — the previous and the next. You may say that LinkedList isn’t very effective in terms of using memory. That’s true, but this data structure can be useful in case of the insert and delete operations performance. However it happens only if you use iterators for them (in this case it occurs in constant time). Access operations by index are performed by searching from the beginning of the end (whichever is closer) to the desired element. However, don’t forget about additional costs for storing references between elements. So, LinkedList is the most popular queue implementation in Java. It is an implementation of List and Deque as well and it allows us to create a bidirectional queue consisting of any objects including null. LinkedList is a collection of elements.More about LinkedList: LinkedList Java Data Structure |
LinkedList Constructors
LinkedList() without parameters is used to construct an empty list. LinkedList(Collection<? extends E> c) is for creating a list containing the elements of the specified collection, in order, they are returned by the collection's iterator.Main LinkedList Methods:
- add(E element) Appends the specified element to the end of this list;
- add(int index, E element) Inserts the element at the specified position index;
- get(int index) Returns the element at the specified position in this list;
- remove(int index) Removes the element that is at position index;
- remove(Object o) Removes the first occurrence of ?o element from this list if it is there.
- remove() Retrieves and removes the first element of the list.
- addFirst(), addLast() add an element to the beginning/end of a list
- clear() removes all elements from the list
- contains(Object o) returns true if the list contains the o element.
- indexOf(Object o) returns the index of the first occurrence of the o element, or -1 if it isn’t in the list.
- set(int index, E element) replaces the element at index position with the element
- size()Returns the quantity of elements in the list.
- toArray() returns an array containing all list’s elements from first to the last element.
- pop() that pops an element from the stack (represented by the list)
- push(E e) that pushes an element onto the stack (represented by this list)
import java.util.*;
public class LinkedListTest {
public static void main(String args[]){
LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
myLinkedList.add(1);
myLinkedList.add(2);
myLinkedList.add(4);
System.out.println("three added elements: " + myLinkedList);
//put one element into the head, not to the tail:
myLinkedList.push(5);
System.out.println("The new element last in will be the first: " + myLinkedList);
//add new element at the specified position:
myLinkedList.add(4,3);
//put one element into the head, not to the tail (same as push):
myLinkedList.addFirst(6);
System.out.println(myLinkedList);
//now remove element no 2 (it is 1):
myLinkedList.remove(2);
System.out.println(myLinkedList);
//now remove the head of the list
myLinkedList.pop();
System.out.println(myLinkedList);
//remove with the other method
myLinkedList.remove();
System.out.println(myLinkedList);
//and with one more
myLinkedList.poll();
System.out.println(myLinkedList);
}
}
PriorityQueue
PriorityQueue is not exactly the queue in FIFO general meaning. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. However it is not an order like it could be in linear structure such as list (from the biggest to the smallest or vice versa). A priority queue based on a priority min heap. Heap is a data structure based on binary tree. The priority of each parent is greater than the priorities of its children. A tree is called complete binary if each parent has no more than two children, and the filling of the levels goes from top to bottom (from the same level — from left to right). Binary heap reorganises itself every time a new element is added or removed from it. In case of min-heap, the smallest element goes to the root regardless of the order of its insertion. Priority queue based on this min-heap, so if we have a PriorityQueue of integers, its first element will be the smallest of these numbers. If you delete the root, the next smallest becomes a root.Main PriorityQueue Methods:
- boolean add(object) inserts the specified element into the priority queue. Returns true in case of success. If the queue is full, the method throws an exception.
- boolean offer(object) inserts the specified element into this priority queue. If the queue is full, the method returns false.
- boolean remove(object) removes a single instance of the specified element from this queue, if it is present.
- Object poll() retrieves and removes the head of this queue. Returns null if the queue is empty.
- void clear() removes all elements from the priority queue.
- Object element() retrieves the head of this queue without removing it. Throws NoSuchElementException if the queue is empty.
- Object peek() retrieves the head of the queue without removing it. Returns null if the queue is empty.
- boolean contains(Object o) returns true if the queue contains the o element.
- int size() returns the number of elements in this queue.
Example of PriorityQueue
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
Queue<Integer> queueL = new LinkedList<>();
for (int i = 5; i > 0; i--) {
queueL.add(i);
}
System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
System.out.println("Print PriorityQueue using poll() (by retrieval): " );
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our PriorityQueue using poll() (by retrieval):
1
2
3
4
5
It is important to understand that priority queues are based on binary heaps, so they do not keep elements in linear sorted order. Every way from the root to the leaf is ordered, but different ways from the root are not. That means you can get the minimal element of the queue very quickly. If you delete the head every time, you’ll print a sorted structure.
ArrayBlockingQueue
Internal data structure of ArrayBlockingQueue is based on a circular array to store elements. It is a typical queue (FIFO) in case new elements are inserted at the tail of the queue, and extraction operations return an element from the head of the queue.Once created queue capacity cannot be changed. Attempts to insert (put) an element into a full queue lead to blocking the flow; trying to take an element from an empty queue also blocks the thread. As we said before, this array is circular. That means that the first and the last elements of the array are treated logically adjacent. The queue advances the indices of the head and tail elements every time you put the elemento into the queue or remove it from the queue. If some index advances the last element of the array, it restarts from 0. Hence, the queue doesn’t have to shift all the elements in case of the head removing (as in usual array). However, in case of removing an element from the middle (using Iterator.remove), the elements are shifted. ArrayBlockingQueue supports an additional fairness policy with fair parameter in the constructor to order the work of waiting flows of producers (inserting elements) and consumers (extracting elements). By default, the order is not guaranteed. However if the queue is created with "fair == true", the implementation of the ArrayBlockingQueue class provides thread access in FIFO order. Equity typically reduces bandwidth, but also reduces volatility and prevents running out of resources.ArrayBlockingQueue Class сonstructors
- ArrayBlockingQueue (int capacity) creates a queue of fixed capacity and with a default access policy.
- ArrayBlockingQueue (int capacity, boolean fair) creates a queue with a fixed capacity and a specified access policy.
- ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) creates a queue with a fixed capacity specified by the access policy and includes elements in the queue.
import java.util.concurrent.*;
public class ArrayBlockingQueueExample {
private BlockingQueue<Integer> blockingQueue;
private final Integer[] myArray = {1,2,3,4,5};
public ArrayBlockingQueueExample ()
{ blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
(new Thread(new Producer())).start();
(new Thread(new Consumer())).start();
}
class Producer implements Runnable
{
public void run() {
try {
int counter = 0;
for (int i=0; i < myArray.length; i++) {
blockingQueue.put(myArray[i]);
if (counter++ < 2)
Thread.sleep(3000);
} blockingQueue.put(-1);
}
catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
class Consumer implements Runnable
{
public void run() {
try {
Integer message = 0;
while (!((message = blockingQueue.take()).equals(-1)))
System.out.println(message);
} catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
public static void main(String[] args) {
new ArrayBlockingQueueExample();
}
}
The output is the queue in natural order; the first two elements appear with a delay.
To reinforce what you learned, we suggest you watch a video lesson from our Java CourseConclusions
- The Queue is used to insert elements at the end of the queue and removes from the beginning of the queue. It follows the FIFO concept.
- Java Queue is a part of the Collection Framework and implements Collection interface. So it supports all methods of Collection interface such as insertion, deletion and so on.
- The most frequently used implementations of Queue are LinkedList, ArrayBlockingQueue and PriorityQueue.
- The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
- If any null operation is performed on BlockingQueues, NullPointerException is thrown.
GO TO FULL VERSION