Java Collections Framework Part 6 - Queues

This is the sixth part of the tutorial, and this link goes to the previous post java collections framework part 5

Queues

A queue is a collection that implements the interface java.util.Queue , usually a queue is an ordered collection that follows the FIFO (First-In, First-Out) rule, but the queue implementations allow other ways to order the collection as well, such as LIFO or based on priority and so on.

The Queue interface defines the following methods:

boolean add(E e): Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

E element(): Retrieves, but does not remove, the head of this queue.

Boolean offer(E e): Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.

E peek(): Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

E poll(): Retrieves and removes the head of this queue, or returns null if this queue is empty.

E remove(): Retrieves and removes the head of this queue.

Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties.

PriorityQueue

The class java.util.PriotiyQueue is an implementation of the Queue interface, it is an ordered collection and allows duplicates, it works as a “Priority-In, Priority-Out” collection, its elements are ordered by priority and its default priority is given by its natural order, it can be defined another priority order with an instance of a Comparator.

Example

The previous example should print the elements in the collection according to its priority, in this case it should print 1 2 3 4 5 6 7 8 9, this means they priority is the natural order.

To specify a different priority an instance of a Comparator should be used:

Example

The previous example should print its elements according to the new priority specified at the time the collection was created, this new priority is the inverse of the natural order and the example should print 9 8 7 6 5 4 3 2 1

Deque

The java.util.Deque interface extends the Queue interface, the deque name means “double-ended queue”. In a double-ended queue elements can be inserted and removed at both ends of the queue, unlike queue that elements only can be inserted at the tail and removed at the head.

With this a deque can also act as a LIFO collection or Stack.

The Deque interface defines new methods besides the ones defined in the Queue interface:

void addFirst(E e) : Inserts e at the head if there is enough space

void addLast(E e): Inserts e at the tail if there is enough space

void push(E e): Inserts e at the head if there is enough space

boolean removeFirstOccurrence(Object o): Removes the first occurrence of o

boolean removeLastOccurrence(Object o): Removes the last occurrence of o

Iterator<E> descendingIterator(): Gets an iterator that returns the elements in reverse order

boolean offerFirst(E e): Inserts e at the head if the deque has space

boolean offerLast(E e): Inserts e at the tail if the deque has space

E peekFirst(): Gets but do not removes the first element

E peekLast(): Gets but do not removes the last element

E pollFirst(): Gets and removes the first element

E pollLast(): Gets and removes the last element

E getFirst(): Gets but do not removes the first element

E getLast(): Gets but do not removes the last element

E removeFirst(): Gets and removes the first element

E removeLast(): Gets and removes the last element

E pop(): Gets and removes the first element

Example

In the previous example a deque collection was created and elements were added in different ways, first the elements were added at the head so the collection final order was:

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

The the elements were added to the tail the collection final order was:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

And this is also the default behavior for adding elements, in the example were used methods for querying the head and the tail of the collection. The example should print:

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

0

9

0

LinkedList

The class java.util.LinkedList besides being a List also implements the Deque interface, this class is very popular because with one class many different behaviors can be implemented.

Go to part 7