Beginning Algorithms (2006)

Chapter 3

public void clear() { _headAndTail.setPrevious(_headAndTail); _headAndTail.setNext(_headAndTail); _size = 0;

}

How It Works

Not surprisingly, the size() and isEmpty() methods are carbon copies of their array list counterparts.

The last method, clear(), is almost, but not quite, as simple as the array list implementation. In order to maintain the correct behavior while using the sentinel, you need to set its next and previous values to point to itself. This ensures that when you insert the first element into the list, its next and previous values will point to the sentinel, and, most important, the sentinel’s next and previous values will point to the new element.

Summar y

This chapter demonstrated that lists can be used as a replacement for the use of arrays in most realworld applications.

You learned that lists preserve insertion order and that they have no inherent concept of uniqueness.

You’ve also covered quite a lot of code in order to examine two of the most common list implementations and their relative performance characteristics. Both array lists and linked lists have similar search and iteration times. However, by their very nature, array lists have much better index-based access compared to linked lists. On the other hand, linked lists don’t have the overhead of copying and resizing that array lists do, so they have generally better insertion and deletion times, especially at the ends.

Although lists as described here are useful in many situations, there are times when slightly different behavior is needed. The next two chapters discuss some variations on lists, known as queues and stacks, that help solve some very specific computing problems.

Exercises

1.Write a constructor for ArrayList that accepts a standard Java array to initially populate List.

2.Write an equals() method that will work for any List implementation.

3.Write a toString() method that will work for any List implementation that prints the contents as a single line with values surrounded by square brackets and separated by commas. For example, “[A, B, C]” or “[]” for an empty List.

4.Create an Iterator that will work for any List implementation. What are the performance implications?

5.Update LinkedList to traverse backward if, when inserting and deleting, the desired index is more than halfway along the list.

6.Rewrite indexOf() so that it will work for any list.

7.Create a List implementation that is always empty and throws

UnsupportedOperationException if an attempt is made to modify it.

74

4

Queues

Queues are an essential part of algorithms that manage the allocation and scheduling of work, events, or messages to be processed. They are often used as a way of enabling different processes — either on the same or different machines — to communicate with one another.

In this chapter, you will learn the following:

How queues differ from lists

Characteristics and implementation of a first-in-first-out (FIFO) queue

How to create a thread-safe queue

How to create a bounded queue — one with a maximum size limit

How to combine all of these queue types to build a multi-threaded simulation of a call center to see just how queues can be put to use

Understanding Queues

Customers line up in a bank waiting to be served by a teller and in supermarkets waiting to check out. No doubt you’ve been stuck waiting in a line to speak to a customer service representative at a call center. In computing terms, however, a queue is a list of data items stored in such a way that they can be retrieved in a definable order. The main distinguishing feature between a queue and a list is that whereas all items in a list are accessible — by their position within the list — the only item you can ever retrieve from a queue is the one at the head. Which item is at the head depends on the specific queue implementation.

More often than not, the order of retrieval is indeed the same as the order of insertion (also known as first-in-first-out, or FIFO), but there are other possibilities as well. Some of the more common examples include a last-in-first-out queue (see Chapter 5) and a priority queue (see Chapter 8), whereby retrieval is based on the relative priority of each item. You can even create a random queue that effectively “shuffles” the contents.

Chapter 4

In this book, whenever we use the term “queue,” we are not necessarily referring to a FIFO queue.

Queues are often described in terms of producers and consumers. A producer is anything that stores data in a queue, while a consumer is anything that retrieves data from a queue. Figure 4-1 shows the interactions between producers, consumers, and queues.

Producer	Consumer
	Queue
Producer	Consumer

Producer	Consumer
Figure 4-1: How producers and consumers interact with a queue.

Queues can be ether bounded or unbounded. Bounded queues have limits placed on the number of items that can be held at any one time. These are especially useful when the amount of available memory is constrained — for example, in a device such as a router or even an in-memory message queue. Unbounded queues, conversely, are free to grow in size as the limits of the hardware allow.

Queue Operations

This chapter describes several different queues used throughout the course of this book, all with slightly different retrieval order. Irrespective of their behavior, the various queues all share a common interface. Table 4-1 lists each of the queue operations along with a brief description.

Table 4-1: Queue Operations

Operation Description

enqueue	Stores a value in the queue. The size of the queue will increase by one.
dequeue	Retrieves the value at the head of the queue. The size of the queue will decrease
	by one. Throws EmptyQueueException if there are no more items in the queue.
clear	Deletes all elements from the queue. The size of the queue will be reset to zero (0).
Size	Obtains the number of elements in the queue.
isEmpty	Determines whether the queue is empty (size() == 0) or not.

76

Queues

As you can see, the queue interface is much simpler than that of the list: enqueue() is responsible for storing values, dequeue() for retrieving them. The remaining methods have the same behavior as those with the same names defined for lists. Notice also that there is no means for accessing all of the data items in a queue at once using an iterator (see Chapter 2), further reinforcing the idea that the only thing you can do is obtain the item at the head.

The Queue Interface

Any operations you have defined can be translated directly into a Java interface so that you can easily create pluggable implementations:

package com.wrox.algorithms.queues;

public interface Queue {

public void enqueue(Object value);

public Object dequeue() throws EmptyQueueException; public void clear();

public int size(); public boolean isEmpty();

}

Each operation has been translated directly into a method on the interface. The only other thing you need to define is the EmptyQueueException thrown by dequeue():

package com.wrox.algorithms.queues;

public class EmptyQueueException extends RuntimeException {

}

We have chosen to make EmptyQueueException a runtime extension. This means you will not be forced to wrap try-catch blocks around calls to dequeue(). The primary reason for this is that we consider retrieval attempts from an empty queue to be a programming error; you can always call isEmpty() to check before calling dequeue().

A First-In-First-Out Queue

This section describes the implementation of a first-in-first-out (FIFO) queue. You’ll first learn about the characteristics of a FIFO queue. After that, you’ll develop some tests and finally implement a very straightforward unbounded FIFO queue based on lists.

The name says it all really: The first value to go in is always the first value to come out. Calling dequeue() on a FIFO queue always returns the element that has been in the queue the longest.

If you were to call enqueue() with the values Cat, Dog, Apple, and Banana, for example, calling dequeue() would return them in the following order: Cat, Dog, Apple, Banana.

Although there are many ways to implement a FIFO queue (and other types of queues, for that matter), one of the simplest solutions, and the one presented here, is to use a list as the underlying storage mechanism. In many ways, this is a very natural fit: A queue can be thought of as a simplified list that includes some constraints on adding and removing items.

77

Chapter 4

When you enqueue a value, it is added to the end of the list, as shown in Figure 4-2.

0	1	2	3
Cat	Dog	Apple

Banana

Figure 4-2: Calling enqueue() adds to the end of the list.

Conversely, when you dequeue a value, it is removed from the beginning of the list, as shown in Figure 4-3.

0	1	2	3
	Dog	Apple	Banana

Cat

Figure 4-3: Calling dequeue() removes from the start of the list.

Of course, you could just as easily have chosen to add to the start and remove from the end. Either way will work, but in this instance we have chosen to add to the end and remove from the start because this seems to better fit our mental model of a queue.

Having discussed the design, it’s time to write some code. As usual, you’ll write some tests first and then the actual queue implementation.

Try It Out

Testing the FIFO Queue

Although you’re only going to examine one way to implement a FIFO queue, there are many others, so in keeping with our approach so far in this book, you’ll develop a suite of tests that any FIFO queue should pass. These tests will be defined in an abstract class with some hooks, to enable you to extend them in order to test specific implementations later:

package com.wrox.algorithms.queues;

import junit.framework.TestCase;

public abstract class AbstractFifoQueueTestCase extends TestCase { private static final String VALUE_A = “A”;

private static final String VALUE_B = “B”; private static final String VALUE_C = “C”;

private Queue _queue;

protected void setUp() throws Exception {

78

Queues

super.setUp();

_queue = createFifoQueue();

}

protected abstract Queue createFifoQueue();

...

}

The first test is really a bit of bounds checking. You want to make sure that an empty list returns a size of zero, that isEmpty() returns true, and that attempting to dequeue something results in an

EmptyQueueException:

public void testAccessAnEmptyQueue() { assertEquals(0, _queue.size()); assertTrue(_queue.isEmpty());

try { _queue.dequeue(); fail();

}catch (EmptyQueueException e) {

//expected

}

}

The next test is a little longer but still pretty straightforward. It checks to make sure that you can successfully enqueue and dequeue values:

public void testEnqueueDequeue() { _queue.enqueue(VALUE_B); _queue.enqueue(VALUE_A); _queue.enqueue(VALUE_C);

assertEquals(3, _queue.size()); assertFalse(_queue.isEmpty());

assertSame(VALUE_B, _queue.dequeue()); assertEquals(2, _queue.size()); assertFalse(_queue.isEmpty());

assertSame(VALUE_A, _queue.dequeue()); assertEquals(1, _queue.size()); assertFalse(_queue.isEmpty());

assertSame(VALUE_C, _queue.dequeue()); assertEquals(0, _queue.size()); assertTrue(_queue.isEmpty());

try { _queue.dequeue(); fail();

} catch (EmptyQueueException e) {

79

Chapter 4

// expected

}

}

There is also one final test to ensure that when you call clear(), the queue is emptied as expected:

public void testClear() { _queue.enqueue(VALUE_A); _queue.enqueue(VALUE_B); _queue.enqueue(VALUE_C);

assertFalse(_queue.isEmpty());

_queue.clear();

assertEquals(0, _queue.size()); assertTrue(_queue.isEmpty());

try { _queue.dequeue(); fail();

}catch (EmptyQueueException e) {

//expected

}

}

Having developed the abstract test class, we can now create a concrete test class for the actual FIFO queue implementation. Of course, we haven’t yet defined the implementation class, but that won’t stop us from defining the test case:

package com.wrox.algorithms.queues;

public class ListFifoQueueTest extends AbstractFifoQueueTestCase { protected Queue createFifoQueue() {

return new ListFifoQueue();

}

}

How It Works

The new test class, AbstractFifoQueueTestCase, defines some constants that will be used later in the actual tests. It also defines a local variable, _queue, for holding an instance of a FIFO queue for running the tests against. The setUp() method — called prior to running each individual test — ensures that the local variable always has a value. It achieves this by calling createFifoQueue(), an abstract method you will implement to return an instance of the specific FIFO queue class under test.

In the second and third tests, we ensure that each time a value is enqueued and dequeued, our actions are reflected accurately in the size of the queue, and, importantly, that when we retrieve values, they are returned to us in exactly the same order as they were stored. That is, of course, the definition of a FIFO queue.

The final test simply stores a number of values to the queue, calls clear(), and ensures that the queue is actually empty.

80

Queues

In the creation of the concrete class, the queue class will be named ListFifoQueue, in line with the fact that it is a FIFO queue and uses a list to store the data. Notice how easy it is to extend AbstractFifoQueueTestCase and implement the createFifoQueue method to return an instance of our concrete queue class.

Implementing the FIFO Queue

With the tests in place, you can safely start coding up your implementation class: ListFifoQueue:

package com.wrox.algorithms.queues;

import com.wrox.algorithms.lists.LinkedList; import com.wrox.algorithms.lists.List;

public class ListFifoQueue implements Queue { private final List _list;

public ListFifoQueue(List list) {

assert list != null : “list can’t be null”;

_list = list;

}

public ListFifoQueue() { this(new LinkedList());

}

...

}

Besides implementing the Queue interface, this holds the underlying list and defines two constructors. The first constructor takes as its only argument a list to use for storing the data (naturally it is checked for null). The second — a default constructor — calls the first, passing in an instance of a linked list.

A linked list is perfectly suited for use with a queue, as it is capable of efficiently adding and removing elements from either end. Compare this to an array list, which you may recall incurs the overhead of continually moving elements as they are removed.

Now that you can construct a list-based FIFO queue, you need to be able to add things to the queue. For this there is enqueue():

public void enqueue(Object value) { _list.add(value);

}

Pretty simple. As discussed earlier, all enqueue() does is add the value to the end of the underlying list.

Next you implement dequeue(), which enables you to retrieve items from the queue:

public Object dequeue() throws EmptyQueueException { if (isEmpty()) {

throw new EmptyQueueException();

81

Chapter 4

}

return _list.delete(0);

}

That wasn’t much more complicated. Remember that dequeue() simply removes and returns the last element in the underlying list. The only extra action to do is a quick check to ensure that there is an element to remove. If there isn’t (because the list is empty), you need to throw an EmptyQueueException as defined in the Queue interface.

You could argue here that because the List interface throws an IndexOutOfBoundsException, you might simply catch the exception and throw an EmptyQueueException instead of checking for an empty list. However, as mentioned previously, if an IndexOutOfBoundsException was ever to be thrown, we would like it to propagate out as an indication of a programming error, and not something the caller has done wrong.

The last few methods on the Queue interface are even easier to implement, as all of them (not coincidentally) have a corresponding method of the same name on the List interface:

public void clear() { _list.clear();

}

public int size() { return _list.size();

}

public boolean isEmpty() { return _list.isEmpty();

}

In all three cases, you need do nothing more than delegate the call to the underlying list.

Blocking Queues

Queues are often used in multi-threaded environments as a form of interprocess communication. Unfortunately, your ListFifoQueue is totally unsafe for use in situations where multiple consumers would be accessing it concurrently. Instead, a blocking queue is one way to provide a thread-safe implementation, ensuring that all access to the data is correctly synchronized.

The first main enhancement that a blocking queue offers over a regular queue is that it can be bounded. So far, this chapter has only dealt with unbounded queues — those that continue to grow without limit. The blocking queue enables you to set an upper limit on the size of the queue. Moreover, when an attempt is made to store an item in a queue that has reached its limit, the queue will, you guessed it, block the thread until space becomes available — either by removing an item or by calling clear(). In this way, you guarantee that the queue will never exceed its predefined bounds.

The second major feature affects the behavior of dequeue(). Recall from the implementation of ListFifoQueue presented earlier that an EmptyQueueException is thrown when an attempt is made to retrieve an item from an empty queue. A blocking queue, however, will instead block the current

82

Queues

thread until an item is enqueued — perfect for implementing work queues where multiple, concurrent consumers need to wait until there are more tasks to perform.

By encapsulating all this behind the Queue interface, you free the consumers of the queue from the intricacies and subtleties of thread synchronization. There are two options for creating the blocking queue: extend an existing queue implementation (so far only ListFifoQueue), or try to wrap the behavior around another queue. The first option would lock you into one specific queue implementation, so instead you should use the second option — wrap another queue — as it gives you the flexibility to easily turn any queue implementation (such as the priority queues presented in Chapter 8) into a blocking queue.

Insofar as synchronization is concerned, we use a very common technique for ensuring that the code plays nicely in a multi-threaded environment: A lock object or, in more technical terms, a mutual exclusion semaphore (mutex), will be used as the synchronization point for all the methods in the class. A mutex is one of the least error prone ways of ensuring that only one thread has access to the underlying queue at any given time.

Try It Out

Using the BlockingQueue

This is usually the point at which we say something like “and of course we start with some tests.” For this particular exercise, however, we are going to deviate from the norm and skip writing the tests altogether.

What!? No tests?

Actually, we did indeed write tests, but an explanation of testing multi-threaded applications is entirely beyond the scope of this book, so we chose to omit them from the text. Therefore, you’re just going to have to trust us on this one. You can, of course, still run the tests by downloading the entire source code for the book.

If you would like to learn more about writing multi-threaded code, try starting with Doug Lea’s

Concurrent Programming in Java: Design Principles and Patterns (1999).

The discussion of BlockingQueue code starts with the class declaration:

package com.wrox.algorithms.queues;

public class BlockingQueue implements Queue { private final Object _mutex = new Object(); private final Queue _queue;

private final int _maxSize;

public BlockingQueue(Queue queue, int maxSize) {

assert queue != null : “queue can’t be null”; assert maxSize > 0 : “size can’t be < 1”;

_queue = queue; _maxSize = maxSize;

}

public BlockingQueue(Queue queue) {

83