Queue basic operation

1. Creating a New Queue Instance

As a best practice, it’s recommended to use generic type and interface as reference type when creating a new collection. For queues, depending on the need of a particular type (queue, deque and blocking queue), use the corresponding interface as the reference type.For example, the following statements create 3 different types of queues:

1
2
3
Queue<String> namesQueue = new LinkedList<>();
Deque<Integer> numbersDeque = new ArrayDeque<>();
BlockingQueue<String> waitingCustomers = new ArrayBlockingQueue<>(100);

Most Queue implementations do not have restriction on capacity (unbounded queues), except the ArrayBlockingQueue, LinkedBlockingQueue and LinkedBlockingDeque classes. The following statement creates an ArrayBlockingQueuewith fixed capacity of 200 elements:

1
BlockingQueue<String> waitingCustomers = new ArrayBlockingQueue<>(200);

Also remember that we can use the copy constructor to create a new Queue instance from another collection. For example:

1
2
3
List<String> listNames = Arrays.asList("Alice", "Bob", "Cole", "Dale", "Eric", "Frank");
Queue<String> queueNames = new LinkedList<>(listNames);
System.out.println(queueNames);

Output:

1
[Alice, Bob, Cole, Dale, Eric, Frank]

 

2. Adding New Elements to the Queue

To insert an element to the tail of the queue, we can use either the add() or offer() method. The following code adds two elements to a linked list:

1
2
3
Queue<String> queueNames = new LinkedList<>();
queueNames.add("Mary");
queueNames.add("John");

When using an unbounded queue (no capacity restriction), the add() and offer() methods do not show the difference. However, when using a bounded queue, the add() method will throw an exception if the queue is full, while the offer()method returns false. The following example illustrates this difference:

1
2
3
4
5
Queue<Integer> queueNumbers = new ArrayBlockingQueue<>(3);
queueNumbers.add(1);
queueNumbers.add(2);
queueNumbers.add(3);
queueNumbers.add(4);    // this line throws exception

The last line throws java.lang.IllegalStateException: Queue full because we declare the queue with capacity of 3 elements. Hence adding the 4th element results in an exception.However, we are safe when using the offer() method, as shown in the following code snippet:

1
2
3
4
5
6
Queue<Integer> queueNumbers = new ArrayBlockingQueue<>(3);
System.out.println(queueNumbers.offer(1));
System.out.println(queueNumbers.offer(2));
System.out.println(queueNumbers.offer(3));
System.out.println(queueNumbers.offer(4));

Output:

1
2
3
4
true
true
true
false

The following code snippet adds an element to the head and an element to the tail of a double ended queue (notice the type of the interface is used):

1
2
3
4
5
6
7
8
9
Deque<String> queueNames = new ArrayDeque<>();
queueNames.offer("Katherine");
queueNames.offer("Bob");
queueNames.addFirst("Jim");
queueNames.addLast("Tom");
System.out.println(queueNames);

Output:

1
[Jim, Katherine, Bob, Tom]

For blocking queue, use the put(e) or offer(e, time, unit) in case you want the current thread to wait until space becomes available in the queue. For example:

1
2
3
4
5
6
7
BlockingQueue<Integer> queueNumbers = new ArrayBlockingQueue<>(100);
try {
    queueNumbers.put(2000);
} catch (InterruptedException ie) {
    ie.printStackTrace();
}

3. Removing the Head of the Queue

A Queue provides the remove() and poll() methods that allow us to pick the element at the head and remove it from the queue. And you should understand the difference between these two methods.The remove() method returns the head element or throws an exception if the queue is empty. For example:

1
2
3
4
5
6
7
Queue<String> queueCustomers = new LinkedList<>();
queueCustomers.offer("Jack");
String next = queueCustomers.remove();
System.out.println("Next customer is: "+ next);
next = queueCustomers.remove(); // throws exception

Here, the queue has only one element, so the first call to remove() working fine. However the subsequent invocation results in java.util.NoSuchElementException because the queue becomes empty.In contrast, the poll() method returns null if the queue is empty, as shown in the following example:

1
2
3
4
5
Queue<String> queueCustomers = new LinkedList<>();
queueCustomers.offer("Jack");
System.out.println("next: " + queueCustomers.poll());
System.out.println("next: " + queueCustomers.poll());   // returns null

Output:

1
2
next: Jack
next: null

The following example removes the head element and tail element from a deque:

1
2
3
4
5
6
7
8
9
10
11
12
Deque<String> queueCustomers = new ArrayDeque<>();
queueCustomers.offer("Bill");
queueCustomers.offer("Kim");
queueCustomers.offer("Lee");
queueCustomers.offer("Peter");
queueCustomers.offer("Sam");
System.out.println("Queue before: " + queueCustomers);
System.out.println("First comes: " + queueCustomers.pollFirst());
System.out.println("Last comes: " + queueCustomers.pollLast());
System.out.println("Queue after: " + queueCustomers);

Output:

1
2
3
4
Queue before: [Bill, Kim, Lee, Peter, Sam]
First comes: Bill
Last comes: Sam
Queue after: [Kim, Lee, Peter]

For a blocking queue, use the take()or poll(time, unit) methods in case you want the current thread to wait until an element becomes available. For example:

1
2
3
4
5
6
7
8
9
BlockingQueue<String> queueCustomers = new ArrayBlockingQueue<>(100);
queueCustomers.offer("Kathe");
try {
    String nextCustomer = queueCustomers.take();
} catch (InterruptedException ie) {
    ie.printStackTrace();
}

 

4. Examining the Head of the Queue

In contrast to the remove() method, the examine methods element() and peek() return (but do not remove) the head of the queue. So consider using these methods in case you just want to check what is currently in the head element without modifying the queue.Also, you need to know the difference between the element() and peek() methods:The element() method throws an exception in case the queue is empty, whereas the peek() method returns null. For example:

1
2
3
4
5
6
7
8
9
10
11
Queue<String> queueCustomers = new PriorityQueue<>();
queueCustomers.offer("Jack");
System.out.println("who's next: " + queueCustomers.poll());
// this returns null in case the queue is empty
System.out.println("who's next: " + queueCustomers.peek());
// this throws exception in case the queue is empty
System.out.println("who's next: " + queueCustomers.element());

For a deque, use the getFirst() or peekFirst() methods to examine the first element, and getLast() or peekLast()to examine the last element. Here’s an example:

1
2
3
4
5
6
7
8
9
Deque<Integer> queueNumbers = new ArrayDeque<>();
queueNumbers.add(10);
queueNumbers.add(20);
queueNumbers.add(30);
queueNumbers.add(40);
System.out.println("first: " + queueNumbers.getFirst());
System.out.println("last: " + queueNumbers.peekLast());

There’s no method for examining a blocking queue.

5. Iterating over Elements in the Queue

We can use the enhanced for loop, iterator and forEach() method to iterate over elements in the queue. The following code snippet illustrates how to iterate a linked list using the enhanced for loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Queue<String> queueNames = new LinkedList<>();
queueNames.add("Dale");
queueNames.add("Bob");
queueNames.add("Frank");
queueNames.add("Alice");
queueNames.add("Eric");
queueNames.add("Cole");
queueNames.add("John");
for (String name : queueNames) {
    System.out.println(name);
}

Output:

1
2
3
4
5
6
7
Dale
Bob
Frank
Alice
Eric
Cole
John

More simply, using Lambda expression with forEach() method in Java 8:

1
queueNames.forEach(name -> System.out.println(name));

The following example iterates over elements of a PriorityQueue which sorts elements by natural ordering:

1
2
3
4
5
6
7
8
9
10
11
Queue<String> queueNames = new PriorityQueue<>();
queueNames.add("Dale");
queueNames.add("Bob");
queueNames.add("Frank");
queueNames.add("Alice");
queueNames.add("Eric");
queueNames.add("Cole");
queueNames.add("John");
queueNames.forEach(name -> System.out.println(name));

Output:

1
2
3
4
5
6
7
Alice
Bob
Cole
Dale
Eric
Frank
John

As you can see in the output, the elements are sorted in the alphabetic order (natural ordering of Strings).NOTE: Pay attention when using an iterator of a PriorityQueue, because it is not guaranteed to traverse the elements of the priority queue in any particular order.

6. Concurrent Queues

All implementations of BlockingQueue are thread-safe. The following implementations are not:

– LinkedList

– ArrayDeque

– PriorityQueue

When you want to use a synchronized linked list, use the following code:

1
List list = Collections.synchronizedList(new LinkedList<>());
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

Up ↑

%d bloggers like this: