Beginning Algorithms (2006)

Chapter 4

private static final int NUMBER_OF_ARGS = 4; private static final int NUMBER_OF_AGENTS_ARG = 0; private static final int NUMBER_OF_CALLS_ARG = 1; private static final int MAX_CALL_DURATION_ARG = 2; private static final int MAX_CALL_INTERVAL_ARG = 3;

private CallCenterSimulator() {

}

public static void main(String[] args) { assert args != null : “args can’t be null”;

if (args.length != NUMBER_OF_ARGS) { System.out.println(“Usage: CallGenerator <numberOfAgents>”

+“ <numberOfCalls> <maxCallDuration>”

+“ <maxCallInterval>”);

System.exit(-1);

}

CallCenter callCenter =

new CallCenter(Integer.parseInt(args[NUMBER_OF_AGENTS_ARG]));

CallGenerator generator =

new CallGenerator(callCenter, Integer.parseInt(args[NUMBER_OF_CALLS_ARG]), Integer.parseInt(args[MAX_CALL_DURATION_ARG]), Integer.parseInt(args[MAX_CALL_INTERVAL_ARG]));

callCenter.open(); try {

callGenerator.generateCalls(); } finally {

callCenter.close();

}

}

}

How It Works

The main() method is the entry point to the application and will be called by the Java interpreter, passing in an array of command-line arguments. These are then checked to ensure that all the required parameters have been provided:

The number of agents to use

The number of calls to generate

The maximum call duration

The maximum time to wait between generated calls

If parameters are missing, the application prints a message to this effect and terminates immediately. If all of the necessary parameters are there, the application constructs a call center and call generator. The call center is then opened, calls are generated, and finally the call center is closed to ensure that customer service agents are stopped correctly.

94

Queues

Running the Application

Before compiling and running the simulator, let’s summarize the application you’ve just created: A CallGenerator creates Calls with a random duration. These calls are accepted by a CallCenter that places them onto a BlockingQueue. One or more CustomerServiceAgents then answer the calls until they are told to GO_HOME. All these are then tied together by a command-line application,

CallCenterSimulator.

You ran the call center simulator with three customer service agents answering 200 calls. The maximum call duration was set at 1 second (1,000 milliseconds) and the maximum time to wait between generating calls was 100 milliseconds. Here is the output (with a large chunk removed for the sake of space):

Call center opening Agent 0 clocked on Agent 0 waiting Agent 1 clocked on Agent 1 waiting Agent 2 clocked on Agent 2 waiting Call center open

Agent 0 answering Call 0

Call 0 answered; waited 1 milliseconds Call 0 queued

Agent 1 answering Call 1

Call 1 answered; waited 1 milliseconds Call 1 queued

Agent 2 answering Call 2

Call 2 answered; waited 1 milliseconds Call 2 queued

Call 3 queued Call 4 queued Call 5 queued Call 6 queued Call 7 queued Agent 2 waiting

Agent 2 answering Call 3

Call 3 answered; waited 203 milliseconds Call 8 queued

Call 9 queued Call 10 queued Call 11 queued Agent 1 waiting

Agent 1 answering Call 4

Call 4 answered; waited 388 milliseconds

...

Call 195 answered; waited 22320 milliseconds Agent 1 waiting

Agent 1 answering Call 196

Call 196 answered; waited 22561 milliseconds Agent 0 waiting

Agent 0 answering Call 197

Call 197 answered; waited 22510 milliseconds Agent 0 waiting

Agent 0 answering Call 198

95

Chapter 4

Call 198 answered; waited 22634 milliseconds

Agent 1 waiting

Agent 1 answering Call 199

Call 199 answered; waited 22685 milliseconds

Agent 2 waiting

Agent 2 answering Call -1

Agent 2 going home

Agent 0 waiting

Agent 0 answering Call -1

Agent 0 going home

Agent 1 waiting

Agent 1 answering Call -1

Agent 1 going home

Call center closed

This only shows the first and last five calls being answered, but you can still see the program in action. You can observe the call center opening, the three agents signing on, and then the calls being generated and waiting in the queue before being answered by the next available agent. Notice how the wait time starts at much less than a second, but by the time the last call is answered it’s up to around 20 seconds (20,000 milliseconds)! Try playing with the input variables such as number of agents, time between calls, and so on, to see how that affects the results.

Although we have tried to keep the code relatively simple, it is hoped that you have an idea of how you might go about using queues. You might like to try gathering more statistics, such as average wait time for a call or for an agent, or perhaps even extending the code to allow different types of call generators to run against the same call center. In this way, you could simulate different types of calls, peak load times, and so on.

Summar y

In this chapter, you learned the following key points about queues and their operation:

Queues are similar to lists with a simpler interface and a defined order of retrieval.

Queues can be optionally bounded such that limits are placed on the number of items in a queue at any one time.

A linked list is an ideal data structure upon which to build a FIFO queue.

You can implement a thread-safe wrapper that works with any queue implementation.

You can implement a bounded queue — one with a maximum size limit.

Exercises

1.Implement a thread-safe queue that performs no waiting. Sometimes all you need is a queue that will work in a multi-threaded environment without the blocking.

2.Implement a queue that retrieves values in random order. This could be used for dealing cards from a deck or any other random selection process.

96

5

Stacks

Now that you are familiar with lists and queues, it’s time to move on to describing stacks. You are probably familiar with some real-world examples of stacks: Plates are usually stacked — you place the first one on the shelf and add to the top. If you need a plate, you remove the top one first. The newspapers at your local convenience store are stacked, as are the books on your desk that you’ve been meaning to read.

Stacks can also be used to implement a simple Most-Recently-Used (MRU) cache and are often used for parsing programming languages.

This “everything stacks” chapter will familiarize you with the following topics:

What stacks are

What stacks look like

How you use stacks

How stacks are implemented

We start by introducing the basic operations of a stack. We then cover the tests required to validate the correctness of any stack implementation. Finally, you’ll look at the most common form of stack, based on a list.

Stacks

A stack is like a list with access restricted to one end. Figure 5-1 shows a graphical representation of a stack.

Top C

B

A

Figure 5-1: A stack is pictured vertically.

Chapter 5

You’ll notice that whereas lists and queues are usually thought of as running from left to right, stacks are pictured vertically — hence, the term “top” to refer to the first and only directly accessible element of a stack. A stack both inserts (pushes) and deletes (pops) from the top.

A stack is also known as a last-in-first-out (LIFO) queue, as it guarantees that the next element removed will be the one that has been on the stack for the least amount of time.

Table 5-1 describes the operations provided by a stack.

Table 5-1: Operations on a Stack

Operation Description

push	Adds a value to the top of the stack. The size of the stack will increase by one.
pop	Deletes and returns the value at the top of the stack. The size of the stack will
	decrease by one. Throws EmptyStackException when there are no more ele-
	ments on the stack.
size	Obtains the number of elements in the stack.
peek	Returns but does not delete the value at the top of the stack. Throws
	EmptyStackException when there are no elements on the stack.
isEmpty	Determines whether a stack is empty. Returns true if the stack is empty
	(size() == 0); otherwise, returns false.
clear	Deletes all elements from a stack. The size of the stack is reset to zero.

Pushing a value on a stack adds it to the top. Figure 5-2 shows what happens when the value D is pushed onto the stack shown in Figure 5-1.

	Top	D
Top	C	C
	B	B
	A	A

Figure 5-2: Pushing a value adds it to the top of the stack.

Popping a value from a stack removes it from the top. Figure 5-3 shows what happens when a value is popped from the stack shown in Figure 5-1.

Top C

B	Top	B
A		A

Figure 5-3: Popping a value removes it from the top.

98

Stacks

The last three operations — peek(), isEmpty(), and clear() — are technically provided for convenience, as they can all be implemented on top of the first three.

Now take the operation definitions and convert these into a combination of Java interfaces and tests:

package com.wrox.algorithms.stacks;

import com.wrox.algorithms.queues.Queue;

public interface Stack extends Queue { public void push(Object value);

public Object pop() throws EmptyStackException; public Object peek() throws EmptyStackException; public void clear();

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

}

The Java interface is quite simple because of the relatively small number of operations. The two methods pop() and peek() both declare that they throw an EmptyStackException anytime an attempt is made to access a stack that has no elements, so you also need to define this exception class as well:

package com.wrox.algorithms.stacks;

public class EmptyStackException extends RuntimeException {

}

Notice that, like the EmptyQueueException from Chapter 4, it has been defined as extending RuntimeException. This is because we consider it to be indicative of a programming error — an error in the application logic. There is no legitimate reason that one of these should ever occur during the normal course of application execution, and as such you don’t want to force the developer to have to needlessly catch them.

Lastly, note that the Stack interface extends the Queue interface. That’s because, as previously discussed, a stack is really a LIFO queue (and you’d like it to be plug-compatible as such), with enqueue() and dequeue() acting as synonyms for push() and pop(), respectively.

The Tests

Now we can proceed to create the test cases necessary to ensure the correct operation of a stack. You will define separate test cases for each of the push(), pop(), peek(), and clear() methods. The size() and isEmpty() methods have no explicit tests of their own because they are tested as part of the others just mentioned.

Although we will only describe one stack implementation in this chapter, it is entirely possible to create your own variations. For that reason, you will create a generic test class that can be extended by concrete test classes specific to each implementation.

99

Chapter 5

Try It Out Creating a Generic Test Class

package com.wrox.algorithms.stacks;

import junit.framework.TestCase;

public abstract class AbstractStackTestCase extends TestCase { protected static final String VALUE_A = “A”;

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

protected abstract Stack createStack();

...

}

How It Works

The stack interface is very simple, as reflected in the small number of test cases. Still, it is important not to become complacent and presume that due to the simplicity, no testing is required.

Try It Out

Using the push() and pop() Methods

Besides peek(), which you will test next, the only way of accessing a stack is via the push() and pop() methods. It is, therefore, all but impossible to test one without the other:

public void testPushAndPop() { Stack stack = createStack();

stack.push(VALUE_B); stack.push(VALUE_A); stack.push(VALUE_C);

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

assertSame(VALUE_C, stack.pop());

assertEquals(2, stack.size()); assertFalse(stack.isEmpty());

assertSame(VALUE_A, stack.pop()); assertEquals(1, stack.size()); assertFalse(stack.isEmpty());

assertSame(VALUE_B, stack.pop()); assertEquals(0, stack.size()); assertTrue(stack.isEmpty());

}

You also need to ensure that any attempt to call pop() on an empty list results in an appropriate exception being thrown:

100

Stacks

public void testCantPopFromAnEmptyStack() { Stack stack = createStack();

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

try { stack.pop(); fail();

}catch (EmptyStackException e) {

//expected

}

}

How It Works

This test pushes the three values B, A, and C onto the stack and then pops them off one at a time, ensuring that they are removed in the correct order: C; then A; and finally B.

After first ensuring the stack is empty, you attempt to pop a value. If the call to pop() is successful, you fail the test because this is incorrect behavior — you shouldn’t be able to pop from an empty stack. If instead an EmptyStackException is thrown, the stack is working as expected.

Try It Out

Testing the peek() Method

In addition to pushing and popping values on and off the stack, the peek() method gives us a “sneak preview” of the topmost element, hence the name:

public void testPeek() {

Stack stack = createStack();

stack.push(VALUE_C); stack.push(VALUE_A);

assertEquals(2, stack.size());

assertSame(VALUE_A, stack.peek()); assertEquals(2, stack.size());

}

To test peek, you push two values — C and then A — and ensure that not only does peek() return the last value pushed — in this case, an A — but also that nothing has been removed from the stack as a consequence:

public void testCantPeekIntoAnEmptyStack() { Stack stack = createStack();

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

try { stack.peek(); fail();

101

Chapter 5

}catch (EmptyStackException e) {

//expected

}

}

Last but not least, you confirm that clear() performs as expected and removes all elements from the stack:

public void testClear() {

Stack stack = createStack();

stack.push(VALUE_A); stack.push(VALUE_B); stack.push(VALUE_C);

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

stack.clear();

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

try { stack.pop(); fail();

}catch (EmptyStackException e) {

//expected

}

}

}

How It Works

After initially filling the stack with some values, the stack is then cleared, after which the size is checked and an attempt is made to pop a value, which should fail: Popping a value from an empty stack should throw an EmptyStackException.

Implementation

Although you could try to implement a stack from first principles, there is really no need to. Instead, in the same way you did during the chapter on queues, you can take advantage of the fact that a list provides you with everything you need to implement a stack.

You’ll see that it is trivial to implement a stack based on the methods already provided by a list. This being the case, anything you could implement with a stack could be done with a list instead. However, by using a specific construct for the purpose, you enforce a clean separation between the concept of a list and that of a stack. This separation of concerns is critically important when designing software.

Having chosen to use a list to implement the stack, you now need to decide how best this can be achieved. You have a few options here: Enhance an existing list implementation, extend an existing list implementation, or create a new class altogether.

102

Stacks

Each of these solutions has pros and cons. Enhancing or extending an existing implementation would be trivial — you would simply have the class implement the Stack in addition to the List interface, and add the methods necessary to satisfy the requirements of a stack. However, this approach has one major drawback: Given that there are at least two known, and no doubt countless unknown, list implementations, you would need to repeat the process for each different type of list you wished to use. Clearly, this is not a particularly elegant solution.

Your other option, and the one discussed here, is to write an entirely new class, ListStack, that uses composition. That is, your new class will hold and wrap an instance of a list. This has a number of advantages, not the least of which is that, if implemented wisely, your stack should be capable of operating on top of any type of list you choose, with no code changes.

At this point in the book, it should be clear to you how important we deem tests to be, so as always, we need a concrete test class:

package com.wrox.algorithms.stacks;

public class ListStackTest extends AbstractStackTestCase { protected Stack createStack() {

return new ListStack();

}

}

Try It Out Implementing the ListStack Class

Next, you define the ListStack class itself, which, among other things, must implement the Stack interface defined earlier:

package com.wrox.algorithms.stacks;

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

public class ListStack implements Stack { private final List _list = new LinkedList();

...

}

Pushing a value onto the stack is as easy as adding to the end of the list:

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

}

public void enqueue(Object value) { push(value);

}

How It Works

The only thing this class needs to hold is a list to use as the underlying data structure. A linked list has been used because it is very efficient at adding and removing items from the ends — something a stack

103