- unlike a normal list, it is not random access: that is, you can't get or set the element at an arbitrary position in the list;
- get and set operations always take place at the ends of the queue (generally, one "takes from the head" and "puts on the tail").
Why use a queue?
So you may well be thinking: why use a queue if it has these restrictions? Can't you just use a boring old ArrayList or LinkedList1? It turns out there are at least three main reasons:- in some cases, a queue is "conceptually what we want";
- eliminating random access allows optimisations for concurrency;
- Java's efficient BlockingQueue implementations can take some of the work out of the most typical use of queues.
Queues with thread pools
One place, then, in which queues are useful is for the work queue of a thread pool. Java provides the ThreadPoolExecutor class; when constructing this class, you can pass in the queue that you want the thread pool to use. Or, you can construct your thread pool with one of the utility methods in the Executors class, in which case a default BlockingQueue will be used.Queue implementations firstly share a new Queue interface, which has several methods for accessing the head and tail of the queue. Recall that items are always placed on the end or "tail" of the list, and always read from the beginning or "head" of the list.
Operation | Throws exception if not possible | Returns value if not possible |
---|---|---|
Add item to tail | add() | offer() |
Remove item from head | remove() | poll() |
"Peek" item at head | element() | peek() |
Types of Queues
Java provides Queue implementations depending on a few key criteria:- thread-safety: if you don't require the queue to be accessed concurrently from multiple threads, then a plain LinkedList can be used as a Queue; the advantage of the other implementations is that they offer efficient thread-safety;
- blocking or non-blocking: various blocking implementations add extra methods to put and remove items from the queue, blocking until the operation is possible, with an optional time limit;
- bound or non-bound: sometimes it is useful to put an upper limit on the number of items that can fit in the queue, e.g. to prevent a thread pool from queueing up too many jobs when the machine is busy;
- other special operations: Java provides an implementation that orders by priority, and another that applies a delay to queued items.
Blocking? | Other criteria | Bound | Non-bound |
---|---|---|---|
Blocking | None | ArrayBlockingQueue | LinkedBlockingQueue |
Priority-based | PriorityBlockingQueue | ||
Delayed | DelayQueue | ||
Non-blocking | Thread-safe | ConcurrentLinkedQueue | |
Non thread-safe | LinkedList | ||
Non thread-safe, priority-based | PriorityQueue |
No comments:
Post a Comment