HelloKoding

Practical coding guides

Queue in Java

The implementations of queue data structures in Java are grouped into general purpose (implementations of of the Queue interface), and concurrent (implementations of the BlockingQueue interface)

Map implementations in Java Collections Framework

The Queue interface

  • Designed for holding elements prior to processing in a single-threaded environment. All operations are not thread-safe
  • Generally do not allow insertion of null elements
  • Supported since Java 1.5

Queue operations

java.util.Queue methods come in 2 forms

  • Throw an exception if the operation fails

    • add(e), equivalent to enqueue, return true upon success and throwing IllegalStateException if no space is currently available
    • remove, equivalent to dequeue, throwing NoSuchElementException if the queue is empty
    • element, equivalent to front, throwing NoSuchElementException if the queue is empty
  • Returns the special value (either null or false) depending on the operation, preferred for capacity restricted queue

    • offer(e), equivalent to enqueue, return true upon success and false if no space is currently available
    • poll, equivalent to dequeue, return null if the queue is empty
    • peek, equivalent to front, return null if the queue is empty

Queue implementations

  • LinkedList, an optionally bounded FIFO queue backed by linked nodes
  • PriorityQueue, an unbounded priority queue backed by a heap

Queue usage example

Queue<Integer> queue = new LinkedList<>();

// Group of operations returning special value (either `null` or `false`)
// if the operation fails
queue.offer(1);
queue.peek();
queue.poll();

// Group of operations throwing an exception
// if the operation fails
queue.add(2);
queue.element();
queue.remove();

The BlockingQueue interface

  • Designed to be used primarily for producer-consumer queues in a multi-threaded environment. All public operations are thread-safe
  • Does not accept null elements, throw NullPointerException on attempts to add, put or offer a null.
  • Supported since Java 1.5

BlockingQueue operations

java.util.concurrent.BlockingQueue methods come in 4 forms

  • Throw an exception if the operation fails, extended from java.util.Queue (add(e), remove and element)
  • Returns special value (either null or false) depending on the operation, extended from java.util.Queue (offer(e), poll and peek)
  • Blocks the current thread indefinitely until the operation can succeed
  • put(e), equivalent to enqueue, waiting if necessary for space to become available
  • take(), equivalent to dequeue, waiting if necessary until an element becomes available
  • Blocks for only a given maximum time limit before giving up
  • offer(e, time, unit), equivalent to enqueue, waiting up to the specified wait time if necessary for space to become available.
  • poll(time, unit), equivalent to dequeue, waiting up to the specified wait time if necessary for an element to become available.

BlockingQueue implementations

  • ArrayBlockingQueue, a bounded FIFO blocking queue backed by an array
  • LinkedBlockingQueue, an optionally bounded FIFO blocking queue backed by linked nodes
  • PriorityBlockingQueue, an unbounded blocking priority queue backed by a heap

BlockingQueue usage example

BlockingQueueExample.java

package com.hellokoding.java.collections;

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.atomic.AtomicInteger;

public class BlockingQueueExample {
    private static AtomicInteger seq = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {
        BlockingQueue q = new ArrayBlockingQueue(10);

        Thread t1 = new Thread(new Producer(q));
        Thread t2 = new Thread(new Consumer(q));
        Thread t3 = new Thread(new Consumer(q));
        t1.start();
        t2.start();
        t3.start();

        t1.join();
        t2.join();
        t3.join();
    }

    static class Producer implements Runnable {
        private final BlockingQueue queue;
        Producer(BlockingQueue q) { queue = q; }
        public void run() {
            try {
                for (int i = 0; i < 10; i++) {
                    queue.put(produce());
                    Thread.sleep(10);
                }
            } catch (InterruptedException ex) {System.out.println(ex);}
        }
        Book produce() {
            Book book = new Book();
            System.out.printf("Put %s %s", book, System.lineSeparator());

            return book;
        }
    }

    static class Consumer implements Runnable {
        private final BlockingQueue queue;
        Consumer(BlockingQueue q) { queue = q; }
        public void run() {
            try {
                while (true) {
                    consume(queue.take());
                    Thread.sleep(10);
                }
            } catch (InterruptedException ex) {
                System.out.println(ex);
            }
        }
        void consume(Object x) {
            System.out.printf("Take %s %s", x, System.lineSeparator());
        }
    }

    static class Book {
        Integer id ;

        Book() {
            this.id = seq.incrementAndGet();
        }

        @Override
        public String toString() {
            return this.id.toString();
        }
    }
}


Follow HelloKoding