ZOFTINO.COM android and web dev tutorials

Java Collections Queue Tutorial

Queue is a collection which holds elements prior to processing. It provides operations to add, remove and examine elements. These operations operate on head and tails elements or position. Which element becomes head and tail depends on the order queue maintains. Depending on the implementation, order of the elements can be FIFO or LIFO manner or elements are ordered in natural order or based on the given comparator.

Some of the implementations of Queue are ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue and SynchronousQueue.

All the operations such as removeAll(), iterator(), spliterator(), toArray(), etc., defined in the collection interface can be used with the queue, see set examples and list examples.

Table of Contents

Queue Hierarchy

java queue hierarchy

ArrayBlockingQueue

ArrayBlockingQueue orders elements in first in first out (FIFO) manner. The element which exists in the queue for longest time becomes the head of the queue. New elements are added at the tail of the queue and retrieval operations return element at the head of the queue.

ArrayBlockingQueue maintains a fixed length of array to hold elements. Capacity is specified when it is created.

ArrayBlockingQueue can be instantiated by passing to its constructor the capacity (int value) or capacity and fairness policy (for ordering waiting producer and consumer threads, boolean value) as arguments, see following section for more details on fairness policy. It can also be instantiated by passing a collection to its constructor.

	ArrayBlockingQueue<Integer> abQueue = new ArrayBlockingQueue<Integer>(4);
	
	ArrayBlockingQueue<Integer> abQueueOne = new ArrayBlockingQueue<Integer>(10, true);
	
	
	ArrayList<Integer> list = new ArrayList<>();		
	list.add(40);
	list.add(45);
	list.add(62);
	ArrayBlockingQueue<Integer> abQueueTwo = new ArrayBlockingQueue<Integer>(4, false, list);

ArrayBlockingQueue maintains FIFO order.

	ArrayBlockingQueue<Integer> abQueue = new ArrayBlockingQueue<Integer>(4);
	abQueue.add(2);
	abQueue.add(10);
	abQueue.add(8);
	abQueue.add(1);
	
	System.out.println(abQueue);

Output

[2, 10, 8, 1]

Adding Elements to Queue

You can add elements using add(), offer() and put() methods which add elements at the tail of the queue. The difference between these methods is that if queue is full, add() method throws IllegalStateException exception, offer method returns false without adding the element and put methods blocks the thread until space in the queue becomes available for the new element and adds it. There is one more variant of offer() method which makes the thread wait for the specified amount of time and quit if it still can’t add element to the queue due to full capacity.

In the following examples, ArrayBlockingQueue is instantiated with a capacity of two and elements are added using add method. Trying to add an element after queue is full will throw "java.lang.IllegalStateException: Queue full" exception.

	ArrayBlockingQueue<String> categories = new ArrayBlockingQueue<String>(2);
	
	categories.add("fashion");
	categories.add("appliance");
	
	categories.add("electronics");

Output

Exception in thread "main" java.lang.IllegalStateException: Queue full

You can check the remaining capacity of the queue using remainingCapacity() method and add elements based on the capacity of the queue.

	ArrayBlockingQueue<String> categories = new ArrayBlockingQueue<String>(2);
	
	categories.add("fashion");
	categories.add("appliance");
	
	if(categories.remainingCapacity() > 0) {
		categories.add("electronics");
	}else {
		System.out.println("queue is full");
	}

Output

queue is full

You can use offer method to add elements. Offer method doesn’t throw exception if the queue is full. It returns false if it can’t add an element.

	ArrayBlockingQueue<String> categories = new ArrayBlockingQueue<String>(2);
	
	categories.offer("fashion");
	
	String cat = "mobiles";
	if(!categories.offer(cat)) {
		System.out.println(cat+" could not be added to queue");
	}		
	
	cat = "electronics";
	if(!categories.offer(cat)) {
		System.out.println(cat+" could not be added to queue");
	}		
	
	System.out.println(categories);

Output

electronics could not be added to queue
[fashion, mobiles]

If the queue if full, you can make the offer() method to wait for certain amount of time and try to add the element after that by passing duration as argument to it. This version of offer() method throws InterruptedException since the thread waits and can be interrupted.

The following example shows that while offer() method waits in a separate thread and an element is removed from the queue on different thread paving the way for the offer method to add the element.

	ArrayBlockingQueue<String> categories = new ArrayBlockingQueue<String>(2);
	categories.offer("home");
	categories.offer("laptops");
	
	new Thread(new Runnable() {
		@Override
		public void run() {
			try {
				categories.offer("tablets", 400, TimeUnit.MILLISECONDS);
			} catch (InterruptedException e1) {
				e1.printStackTrace();
			}
		}			
	}).start();		
	categories.remove();
	
	try {
		Thread.sleep(500);
	} catch (InterruptedException e1) {
		e1.printStackTrace();
	}
	
	System.out.println(categories);

Output

[laptops, tablets]

Similarly put method can be used to add an element which blocks the thread if queue is full. Following example shows that while put method waits for the space in the queue to be available, another thread removes an element causing put() method to exit by adding the element to the queue.

	ArrayBlockingQueue<Integer> abQueue = new ArrayBlockingQueue<Integer>(4);
	try {
		abQueue.put(23);
		abQueue.put(40);
		abQueue.put(18);
		abQueue.put(12);
		
		System.out.println(abQueue);		

		new Thread(new Runnable() {
			@Override
			public void run() {
				try {
					Thread.sleep(500);
				} catch (InterruptedException e) {}
				System.out.println("removing an element from queue");
				abQueue.remove();
			}			
		}).start();
		
		System.out.println("try to put 5th element..");
		abQueue.put(55);
		System.out.println("5th element has been added to queue");
		
		
	} catch (InterruptedException e1) {	}
	
	System.out.println(abQueue);

Output

[23, 40, 18, 12]
try to put 5th element..
removing an element from queue
5th element has been added to queue
[40, 18, 12, 55]

A collection of elements can be added to the queue using addAll() method passing the collection to it.

Removing Elements from Queue

An element at head of the queue can be removed by calling remove method.

	ArrayBlockingQueue<String> stores = new ArrayBlockingQueue<String>(4);
	stores.add("amazon");
	stores.add("walmart");
	stores.add("ebay");
	stores.add("sears");
	
	System.out.println("Elements in the queue: "+stores);
	
	stores.remove();
	
	System.out.println("after remove: "+stores);

Output

Elements in the queue: [amazon, walmart, ebay, sears]
after remove: [walmart, ebay, sears]

Specific element can be removed from the queue by passing the element to remove method.

	System.out.println("Elements in the queue: "+stores);	
	stores.remove("ebay");	
	System.out.println("after remove: "+stores);

Output

Elements in the queue: [amazon, walmart, ebay, sears]
after remove: [amazon, walmart, sears]

To retrieve and remove the head element from the queue, you can use poll method. The difference between remove and poll method is that while poll method returns null, remove method throws NoSuchElementException exception if the queue is empty.

	ArrayBlockingQueue<Integer> price = new ArrayBlockingQueue<Integer>(3);
	price.add(298);
	price.add(398);
	price.add(498);
	
	System.out.println("elements in the queue: "+price);
	System.out.println("element removed: "+price.poll());
	System.out.println("elements in the queue: "+price);

Output

elements in the queue: [298, 398, 498]
element removed: 298
elements in the queue: [398, 498]

Poll method returns null if the queue is empty. If the queue is empty, you can make the thread to wait for some time for elements to be available in the queue using poll() method . Following example calls poll() method with a wait time of 600 milliseconds while another thread adds an element to the queue causing the waiting poll method to remove and return the added element.

	ArrayBlockingQueue<Integer> price = new ArrayBlockingQueue<Integer>(3);
	
	new Thread(new Runnable() {
		@Override
		public void run() {
			try {
				Thread.sleep(400);
			} catch (InterruptedException e) {}
			
			System.out.println("adding an element to queue");
			price.add(129);
		}			
	}).start();
	
	System.out.println("no elements in the queue "+price);
	System.out.println("poll method waiting for element");
	try {
		System.out.println("removed element: "+
				price.poll(600, TimeUnit.MILLISECONDS));
	} catch (InterruptedException e2) {	}

Output

no elements in the queue []
poll method waiting for element
adding an element to queue
removed element: 129

You can remove an element from the queue using take method, if queue is empty, take() method blocks until an element is available to be removed.

	ArrayBlockingQueue<Integer> price = new ArrayBlockingQueue<Integer>(3);
	
	new Thread(new Runnable() {
		@Override
		public void run() {
			try {
				Thread.sleep(2000);
			} catch (InterruptedException e) {}
			
			System.out.println("adding an element to queue");
			price.add(200);
		}			
	}).start();
	
	System.out.println("no elements in the queue "+price);
	System.out.println("take method waiting for an element");
	try {
		System.out.println("removed element: "+
				price.take());
	} catch (InterruptedException e2) {	}

Output

no elements in the queue []
take method waiting for an element
adding an element to queue
removed element: 200

Examine Elements from Queue

Methods peek() or element() returns the head element of the queue without removing it. The difference between peek() and element() is that while peek() returns null, element() throws NoSuchElementException exception if the queue is empty. Following example examines the head element and removes it if it fulfills a condition.

	ArrayBlockingQueue<Integer> discount = new ArrayBlockingQueue<Integer>(3);
	
	discount.add(20);
	discount.add(70);
	discount.add(60);
	
	if(discount.peek() < 50) {
		discount.remove();
	}
	
	System.out.println(discount);

Output

[70, 60]

Draining Queue

All the elements of the queue can be removed and added into a collection using drainTo() method.

	ArrayBlockingQueue<Integer> marks = new ArrayBlockingQueue<Integer>(3);
	marks.add(66);
	marks.add(55);
	marks.add(49);
	System.out.println("queue before drain: "+marks);
	
	List<Integer> lst = new ArrayList<>();
	marks.drainTo(lst);
	
	System.out.println("queue after drain: "+marks);
	System.out.println("queue elements in list : "+lst);

Output

queue before drain: [66, 55, 49]
queue after drain: []
queue elements in list : [66, 55, 49]

Blocking Queue Fairness Policy

When the blocking operations such as put, take, poll, offer are performed on the blocking queues, the thread performing the operation waits if queue is full for put and offer operations or if queue is empty for poll and take operations. In this scenario, multiple producer threads which are waiting to perform blocking add operations or consumer threads which are waiting to perform blocking remove operations are given priority using fairness policy.

If fairness policy set to true, which can be done by passing the boolean value of true to constructor when the queue is created, the consumer thread or producer thread which is waiting for long time gets priority, meaning priority of performing operations on the queue is given to the waiting threads in FIFO manner. If fairness policy is set to false, order is not defined.

Following example shows applying blocking queue fairness policy for two producers.

		ArrayBlockingQueue<Integer> marks = new ArrayBlockingQueue<Integer>(3, true);
		marks.add(66);
		marks.add(55);
		marks.add(49);
		
		if(marks.remainingCapacity() < 1) {
			System.out.println("queue is full: "+marks);
		}
		
		
		new Thread(new Runnable() {
			@Override
			public void run() {				
				System.out.println("adding an element to queue on thread : "
				+Thread.currentThread().getId());
				try {
					marks.put(79);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				System.out.println("added element to queue on thread : "
				+Thread.currentThread().getId());
			}			
		}).start();
		
		try {
			Thread.sleep(200);
		} catch (InterruptedException e) {}
		
		System.out.println("after 200 milli seconds");
		
		new Thread(new Runnable() {
			@Override
			public void run() {				
				System.out.println("adding an element to queue on thread : "
				+Thread.currentThread().getId());
				try {
					marks.put(58);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				System.out.println("added element to queue on thread : "
				+Thread.currentThread().getId());
			}			
		}).start();
		
		try {
			Thread.sleep(200);
		} catch (InterruptedException e) {}
		
		System.out.println("after 200 milli seconds");
		
		System.out.println("element removed: "+marks.remove());
		
		try {
			Thread.sleep(200);
		} catch (InterruptedException e) {}
		
		System.out.println("after 200 milli seconds, queue: "+marks);
		
		System.out.println("element removed: "+marks.remove());
		
		System.out.println("queue: "+marks);

Output

queue is full: [66, 55, 49]
adding an element to queue on thread : 10
after 200 milli seconds
adding an element to queue on thread : 11
after 200 milli seconds
element removed: 66
added element to queue on thread : 10
after 200 milli seconds, queue: [55, 49, 79]
element removed: 55
added element to queue on thread : 11
queue: [49, 79, 58]

Similarly, if fairness policy is set to true, consumer threads are given priority in FIFO manner.

	ArrayBlockingQueue<Integer> marks = new ArrayBlockingQueue<Integer>(3, true);
	
	if(marks.isEmpty()) {
		System.out.println("queue is empty: "+marks);
	}
	
	
	new Thread(new Runnable() {
		@Override
		public void run() {				
			System.out.println("removing an element from queue on thread : "
			+Thread.currentThread().getId());
			try {
				System.out.println(marks.take()+" removed from queue on thread : "
						+Thread.currentThread().getId());
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			
		}			
	}).start();
	
	new Thread(new Runnable() {
		@Override
		public void run() {				
			System.out.println("removing an element from queue on thread : "
			+Thread.currentThread().getId());
			try {
				System.out.println(marks.take()+" removed from queue on thread : "
						+Thread.currentThread().getId());
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			
		}			
	}).start();
	
	try {
		Thread.sleep(200);
	} catch (InterruptedException e) {}
	
	System.out.println("after 200 milli seconds added element");
	marks.add(46);
	
	try {
		Thread.sleep(200);
	} catch (InterruptedException e) {}
	
	System.out.println("after 200 milli seconds added an element");
	marks.add(69);

Output

queue is empty: []
removing an element from queue on thread : 10
removing an element from queue on thread : 11
after 200 milli seconds added element
46 removed from queue on thread : 10
after 200 milli seconds added an element
69 removed from queue on thread : 11

LinkedBlockingQueue

LinkedBlockingQueue is similar to ArrayBlockingQueue. It works in FIFO (first in first out) manner, remove operation returns element at the head of the queue and element is added at the tail of the queue. LinkedBlockingQueue.

ArrayBlockingQueue uses fixed length array to hold queue elements. LinkedBlockingQueue is based on linked nodes and can grow as you add elements. LinkedBlockingQueue can be instantiated with a capacity of integer-maximum value using default constructor or you can specify capacity by passing the value to constructor.

In single threaded applications, LinkedBlockingQueue perform better than ArrayBlockingQueue. But the performance is not predictable in concurrent applications.

PriorityQueue

PriorityQueue is an unbounded queue, capacity grows as elements are added to it.

It orders elements according to natural order or based on the comparator provided to its constructor. Following example shows instantiating PriorityQueue with default constructor and elements are ordered according to their natural order.

	PriorityQueue<Integer> nums = new PriorityQueue<>();
	nums.add(23);
	nums.add(45);
	nums.add(9);
	nums.add(78);
	nums.add(37);
	
	while(!nums.isEmpty()) {
	   System.out.println(nums.remove());
	}

Output

9
23
37
45
78

Following example shows using PriorityQueue with comparator to order elements in custom order.

	PriorityQueue<Integer> nums = new PriorityQueue<>((i, ii) -> {
		if(i < ii) {
			return 1;
		}
		return -1;
	});
	nums.add(23);
	nums.add(45);
	nums.add(9);
	nums.add(78);
	nums.add(37);
	
	while(!nums.isEmpty()) {
	   System.out.println(nums.remove());
	}

Output

78
45
37
23
9

Priority queue doesn’t allow null values. If you run the following code which tries to add null value to priority queue, you will get null pointer exception.

	PriorityQueue<String> brands = new PriorityQueue<>();
	brands.add("samsung");
	brands.add("apple");
	brands.add(null);

Elements are added at the tail of the queue and remove and examine operations return element which is at the head of the queue. The top element (or least element in natural order) after ordering the elements becomes the head of the queue and highest element becomes the tail of the queue.

Retrieval operations, discussed in the previous sections, such as poll(), peek(), element() and remove() return element at the head.

	PriorityQueue<String> brands = new PriorityQueue<>();
	brands.add("samsung");
	brands.add("apple");
	brands.add("lg");
	
	
	System.out.println(brands.peek());
	System.out.println(brands.poll());

Output

apple
apple
[lg, samsung]

Traversal using Iterator object returned by iterator() operation on the PriorityQueue object doesn’t return elements in a particular order. That is because PriorityQueue doesn’t order all its elements, it only makes sure that element at the head of the queue is the one which is either least or highest element depending on the order.

	PriorityQueue<Integer> tax = new PriorityQueue<>();
	tax.add(22);
	tax.add(32);
	tax.add(11);
	tax.add(28);		
	
	System.out.println("traversal of priority queue: ");
	Iterator<Integer> taxIterator = tax.iterator();
	while(taxIterator.hasNext()) {
		System.out.println(taxIterator.next());
	}
	
	System.out.println("elements in priority queue: ");
	System.out.println(tax);

Output

traversal of priority queue: 
11
28
22
32
elements in the priority queue: 
[11, 28, 22, 32]

You need to perform external sorting if you need ordered elements of the priority queue, like done in the following example.

	Object taxes[] = tax.toArray();		
	Arrays.sort(taxes);
	for(Object taxNum : taxes) {
		System.out.println(""+taxNum);
	}

Output

11
22
28
32

PriorityBlockingQueue

Properties of PriorityBlockingQueue is same as the properties of PriorityQueue. The difference between PriorityBlockingQueue and PriorityQueue is that as name suggests PriorityBlockingQueue provides blocking operations such as put, take, poll and offer.

SynchronousQueue

SynchronousQueue allows an object in one thread to pass data, event or task to an object running on another thread. SynchronousQueue is a blocking queue without any capacity. Insert operation waits for remove operations and remove operation waits for insert operation.

Following example shows how to use SynchronousQueue.

	SynchronousQueue<String> latestCoupon = new SynchronousQueue<String>();
	
	new Thread(new Runnable() {
		@Override
		public void run() {				
			System.out.println("waiting for element on thread : "
			+Thread.currentThread().getId());
			try {
				System.out.println(latestCoupon.take()+
						"\n got element from the queue on thread : "
						+Thread.currentThread().getId());
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			
		}			
	}).start();
	
	new Thread(new Runnable() {
		@Override
		public void run() {				
			System.out.println("adding an element to queue on thread : "
			+Thread.currentThread().getId());
			try {
				latestCoupon.put("flat 40% off on fashion");
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			
		}			
	}).start();

Output

waiting for element on thread : 10
adding an element to queue on thread : 11
flat 40% off on fashion
 got element from the queue on thread : 10

DelayQueue

DelayQueue is an unbounded blocking queue meaning size of it can grow as you add elements to it and it supports blocking operations which are applicable when queue is full or empty. DelayQueue can contain objects which implement Delayed interface. If the delay time returned by getDelay() method of objects expires then only the elements of the DelayQueue will be available for removal. For details and examples see DelayQueue examples.

TransferQueue

TransferQueue can be used as synchronous queue and normal blocking queue, meaning in addition to normal add and remove operations, it provides operations for producer to add an element to the queue and wait for the consumer to receive it.

LinkedTransferQueue

LinkedTransferQueue is based on linked nodes. It can be used as transfer queue and linked blocking queue. For details and examples, please see LinkedTransferQueue examples.

Deque

For details and examples, please see Deque tutorial.