Transcript TestDPL2.java - Cengage Learning

Programming and Problem Solving
With Java
Chapter 13: Stacks
and Queues
Stacks
Applications of Stacks
Implementation of a Stack Class
Queues
Implementation of the Queue Class
Simulation
Copyright 1999, James M. Slack
Stacks
Common in real world
Papers
Books
CDs
Plates
Bowls
What can we do
with a stack?
Put new item on top
Take topmost item off
Programming and Problem Solving With Java
2
Stacks: Operations
Java has a standard Stack class
java.util.Stack
Methods:
push(): put a new item on top of a stack
pop(): get the topmost item from the stack, and remove it
from the stack
peek(): get the value of the topmost item from the stack,
but don't remove the item from the stack
empty(): return true if the stack is empty
search(): tell how far a value is from the top of the stack,
or -1 if the value is not in the stack
A stack is a LIFO structure
Last-in, first-out
Programming and Problem Solving With Java
3
Stacks: Push and Pop
A
Push A
C
B
A
Pop C
Programming and Problem Solving With Java
C
B
B
A
A
Push B
Push C
B
A
Pop B
A
Pop A
4
Stacks: Demonstration
// This program is a simple demonstration of how to
// use Java's standard Stack class.
import java.util.Stack;
public class SimpleStackDemo
{
public static void main(String[] args)
throws java.io.IOException
{
Stack myStack = new Stack();
// Push some values on the stack (all must be objects)
myStack.push("Hello");
myStack.push(new Integer(123));
myStack.push(new Double(5.678));
// Display the stack
System.out.println("The contents of the stack: " + myStack);
// Pop the objects off the stack and display them
double dValue = ((Double) myStack.pop()).doubleValue();
System.out.println("Popped " + dValue);
int iValue = ((Integer) myStack.pop()).intValue();
System.out.println("Popped " + iValue);
String sValue = (String) myStack.pop();
System.out.println("Popped " + sValue);
// Display the stack
System.out.println("The contents of the stack: " + myStack);
}
The contents of the stack: [Hello, 123, 5.678]
}
Popped 5.678
Popped 123
Popped Hello
Programming and Problem Solving With Java
5
The contents of the stack: []
Stacks: Demonstration
Longer demonstration of Java’s Stack class
//
//
//
//
This program lets you push characters onto the
stack, and pop them off. It makes sure you don't try to pop
a character from an empty stack. This is a demonstration of
how to use the Stack class.
import java.util.Stack;
import TextMenu;
import Keyboard;
public class StackDemoApp extends TextMenu
{
static final int PUSH_COMMAND = 1;
static final int POP_COMMAND = 2;
static final int TOP_COMMAND = 3;
// Constructor
public StackDemoApp()
{
super("Stack Test Menu");
addSelection("Push a new element", '1', PUSH_COMMAND);
addSelection("Pop an element", '2', POP_COMMAND);
addSelection("Get topmost element", '3', TOP_COMMAND);
addSelection("Quit program", 'q', TextMenu.QUIT);
}
Programming and Problem Solving With Java
6
Stacks: Demonstration
StackDemoApp
(continued)
// Handle each event as user selects a command
public int handleEvent(int event)
throws java.io.IOException
{
char character;
}
switch (event)
{
case PUSH_COMMAND:
character = Keyboard.readChar("Character to push: ");
charStack.push(new Character(character));
break;
case POP_COMMAND:
if (charStack.empty())
{
System.out.println("Stack is empty");
}
else
{
character = ((Character) charStack.pop()).charValue();
System.out.println("Character popped: " + character);
}
break;
case TOP_COMMAND:
if (charStack.empty())
{
System.out.println("Stack is empty");
}
else
{
character = ((Character) charStack.peek()).charValue();
System.out.println("Character on top: " + character);
}
break;
}
return event;
Programming and Problem Solving With Java
7
Stacks: Demonstration
StackDemoApp (continued)
// Instance variables
private Stack charStack = new Stack();
}
public static void main(String[] args)
throws java.io.IOException
{
StackDemoApp stackDemo = new StackDemoApp();
stackDemo.run();
}
Programming and Problem Solving With Java
8
Stacks: Demonstration
StackDemoApp (sample run)
+--- Stack Test Menu --| 1) Push a new element 2) Pop an element
| q) Quit program
| Enter selection: 1
Character to push: X
+--- Stack Test Menu --| 1) Push a new element 2) Pop an element
| q) Quit program
| Enter selection: 1
Character to push: Y
+--- Stack Test Menu --| 1) Push a new element 2) Pop an element
| q) Quit program
| Enter selection: 2
Character popped: Y
+--- Stack Test Menu --| 1) Push a new element 2) Pop an element
| q) Quit program
| Enter selection: 2
Character popped: X
+--- Stack Test Menu --| 1) Push a new element 2) Pop an element
| q) Quit program
| Enter selection: q
Programming and Problem Solving With Java
3) Get topmost element
3) Get topmost element
3) Get topmost element
3) Get topmost element
3) Get topmost element
9
Stacks: Postfix Expressions
Postfix notation
Also called reverse Polish notation (RPN)
Enter operator after operands
Example: 6+8 is 6 8 + in Postfix
Infix notation
Conventional notation: 6 + 8
Advantages of postfix
Parentheses not needed
(8 + 7) x (2 - 8)  8 7 + 2 8 - x
Easy to evaluate by computer
Programming and Problem Solving With Java
10
Stacks: Postfix Expressions
Evaluation of postfix expression
Get symbol from expression
If symbol is number, push on stack
If symbol is operator, pop two numbers from stack, do
operation, push result back onto stack
Repeat until all symbols read from expression. At end,
result is on top of stack
Programming and Problem Solving With Java
11
Stacks: Postfix Expressions
Example
a. Ready to
start
 Evaluate 6 8 +
b. Read 6
and push it
68+
Input
c. Read 8
and push it
8+
+
Input
Input
8
Stack
d. Read +
+
Input
6
6
Stack
Stack
e. Pop 2
numbers, add
them
6 + 8 Input
f. Result is
14, push it
14
Input
8
Programming and Problem Solving With Java
6
Stack
14
12
Stack
Stack
Stacks: Postfix Expressions
Example: Program to evaluate postfix expressions
Single digit numbers only
No spaces
No error checking
// This program evaluates postfix expressions. The
// operators +, -, *, and /. This program does NO error checking.
import java.util.Stack;
import Keyboard;
public class EvaluatePostFix
{
Programming and Problem Solving With Java
13
Stacks: Postfix Expressions
// doOperation: Returns firstOperand oper secondOperand
// Note: oper must be '+', '-', '*', or '/'. If oper is '/',
//
then secondOperand cannot be zero
static int doOperation(int firstOperand, int secondOperand,
char oper)
{
int returnValue = 0;
switch (oper)
{
case '+':
returnValue = firstOperand + secondOperand;
break;
case '-':
returnValue = firstOperand - secondOperand;
break;
case '*':
returnValue = firstOperand * secondOperand;
break;
case '/':
returnValue = firstOperand / secondOperand;
break;
}
}
return returnValue;
Programming and Problem Solving With Java
14
Stacks: Postfix Expressions
public static void main(String[] args)
throws java.io.IOException
{
Stack stack = new Stack();
char inputChar;
System.out.println("--- Evaluate postfix expressions ---");
System.out.println("--- (Single digit integers ONLY) ---");
System.out.println();
String expression
= Keyboard.readString("Enter a postfix expression: ");
Programming and Problem Solving With Java
15
Stacks: Postfix Expressions
}
}
for (int pos = 0; pos < expression.length(); pos++)
{
inputChar = expression.charAt(pos);
System.out.println();
System.out.println("Next character is " + inputChar
+ ", stack is " + stack);
switch (inputChar)
{
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
System.out.println(" Push " + inputChar);
stack.push(new Integer(Character.digit(inputChar, 10)));
break;
case '+': case '-': case '*': case '/':
int firstOperand = ((Integer) stack.pop()).intValue();
System.out.println(" Pop " + firstOperand);
int secondOperand = ((Integer) stack.pop()).intValue();
System.out.println(" Pop " + secondOperand);
int result = doOperation(secondOperand, firstOperand,
inputChar);
System.out.println(" Compute " + secondOperand
+ " " + inputChar + " "
+ firstOperand
+ " and push result " + result);
stack.push(new Integer(result));
break;
case ' ':
break; // Do nothing
}
}
System.out.println(" Pop result " + stack.pop());
Programming and Problem Solving With Java
16
Stacks: Postfix Expressions
Sample run of EvaluatePostFix: 6 8 +
--- Evaluate postfix expressions ----- (Single digit integers ONLY) --Enter a postfix expression: 6 8 +
Next character is 6, stack is []
Push 6
Next character is
, stack is [6]
Next character is 8, stack is [6]
Push 8
Next character is
, stack is [6, 8]
Next character is +, stack is [6, 8]
Pop 8
Pop 6
Compute 6 + 8 and push result 14
Pop result 14
Programming and Problem Solving With Java
17
Stacks: Postfix Expressions
Another evaluation: 8 7 + 2 8 - x
--- Evaluate postfix expressions ----- (Single digit integers ONLY) ---
Next character is
Enter a postfix expression: 8 7 + 2 8 - *
Next character is 8, stack is [15, 2]
Push 8
Next character is 8, stack is []
Push 8
Next character is
Next character is
Next character is -, stack is [15, 2, 8]
Pop 8
Pop 2
Compute 2 - 8 and push result -6
, stack is [8]
Next character is 7, stack is [8]
Push 7
Next character is
, stack is [8, 7]
Next character is +, stack is [8, 7]
Pop 7
Pop 8
Compute 8 + 7 and push result 15
Next character is , stack is [15]
Next character is
, stack is [15, 2]
, stack is [15, 2, 8]
, stack is [15, -6]
Next character is *, stack is [15, -6]
Pop -6
Pop 15
Compute 15 * -6 and push result -90
Next character is 2, stack is [15]
Push 2
Programming and Problem Solving With Java
18
Stacks: Translate Infix to Postfix
Translation of infix to postfix
If we can translate expression to postfix, then can use
EvalPostfix to evaluate
Can use a stack to convert infix to postfix
Will require fully parenthesized infix expressions
Fully parenthesized: parentheses for each operator
Example: (1 + (8 x 2))
Not fully parenthsized: ((9 + 3 - 2) / 5)
Keeps translation algorithm simple
Programming and Problem Solving With Java
19
Stacks: Translate Infix to Postfix
Translation of infix to postfix by hand
Move each
operators to its
right parenthesis
( 1+( 8x 2 ) )
Programming and Problem Solving With Java
Remove the
parentheses
1 8 2x+
20
Stacks: Translate Infix to Postfix
Algorithm to translate infix to postfix
For each input character
•If character is operand, output character
•If character is operator, push character on stack
•If character is right parenthesis, pop operator and output operator
•If character is left parenthesis, ignore
Resulting output is postfix equivalent of infix expression
Programming and Problem Solving With Java
21
Stacks: Translate Infix to Postfix
Example: translate (1 + (8 * 2))
Input
(1 + ((8 * 2))
1 + ((8 * 2))
+ ((8 * 2))
((8 * 2))
(8 * 2))
8 * 2))
* 2))
2))
))
)
Next
Character
(
1
+
(
(
8
*
2
)
)
Programming and Problem Solving With Java
Action
(start)
ignore
output
push
ignore
ignore
output
push
output
pop and output
pop and output
Stack
[]
[]
[]
[+]
[+]
[+]
[+]
[+, *]
[+, *]
[+]
[]
Output
1
1
1
1
1
1
1
1
1
8
8
8 2
8 2 *
8 2 * +
22
Stacks: Activation Records
Computer uses run-time stack
Each running method has activation record on the stack
Keeps track of method calls and returns
Each method’s activation record contains
Return point
Local variable values
Parameter values
Stack works well here
if A calls B, then B must finish before A can resume
Last-in, first-out  stack
Programming and Problem Solving With Java
23
Stacks: Activation Records (DPL)
Example: Simple programming language DPL
No parameters
No variables
No return values
Basically just method calls
DPL statements
COMMENT: ignored
TYPE: display argument
END: end program (ends automatically if no more
statements)
METHOD: Begin method definition
RETURN: Return from method
CALL: Call method
Programming and Problem Solving With Java
24
Stacks: Activation Records (DPL)
Control starts with first statement (ignores
COMMENT)
First statement should be TYPE, END, or CALL
Example DPL program
CALL SomeMethod
TYPE Finished!
END
METHOD SomeMethod
TYPE Now in SomeMethod
RETURN
Output
Now in SomeMethod
Finished!
Next slide shows activation records on run-time
stack for this program
Programming and Problem Solving With Java
25
Now in SomeMethod
Push return
address
Pop return
address
Display
CALL SomeMethod
TYPE Finished!
END
return to
METHOD SomeMethod
TYPE Now in SomeMethod
RETURN
Stack
Display
CALL SomeMethod
TYPE Finished!
END
return to
METHOD SomeMethod
TYPE Now in SomeMethod
RETURN
Stack
Now in SomeMethod
Return from
method
Start method
Display
CALL SomeMethod
TYPE Finished!
END
METHOD SomeMethod
TYPE Now in SomeMethod
RETURN
return to
Stack
In method
METHOD SomeMethod
TYPE Now in SomeMethod
RETURN
METHOD SomeMethod
TYPE Now in SomeMethod
RETURN
Ready to end
Display
CALL SomeMethod
TYPE Finished!
END
return to
Programming and Problem Solving With Java
Stack
Display
CALL SomeMethod
TYPE Finished!
END
CALL SomeMethod
TYPE Finished!
END
METHOD SomeMethod
TYPE Now in SomeMethod
RETURN
Stack
Now in SomeMethod
Finished!
Display
Stack
26
Stacks: Activation Records (DPL)
COMMENT This is an example of the
COMMENT demonstration programming language DPL.
COMMENT It shows how methods work.
COMMENT ---- Main program ---TYPE >> Starting main program
TYPE -- Call FirstMethod from main ...
CALL FirstMethod
TYPE -- Back in main from FirstMethod
TYPE -- Call SecondMethod from main ...
CALL SecondMethod
TYPE -- Back in main from SecondMethod
TYPE << Ending main program
END
METHOD FirstMethod
TYPE >> Entering FirstMethod
TYPE << Leaving FirstMethod
RETURN
METHOD
TYPE
TYPE
CALL
TYPE
TYPE
RETURN
>>
->>
<<
-->>
->>
<<
-<<
-<<
Starting main program
Call FirstMethod from main ...
Entering FirstMethod
Leaving FirstMethod
Back in main from FirstMethod
Call SecondMethod from main ...
Entering SecondMethod
Call FirstMethod from SecondMethod ...
Entering FirstMethod
Leaving FirstMethod
Back in SecondMethod from FirstMethod
Leaving SecondMethod
Back in main from SecondMethod
Ending main program
SecondMethod
>> Entering SecondMethod
-- Call FirstMethod from SecondMethod ...
FirstMethod
-- Back in SecondMethod from FirstMethod
<< Leaving SeconMMdMethod
Programming and Problem Solving With Java
27
Stacks: Activation Records (DPL)
DPL interpreter logic
Read program from file into memory
Set program counter to first statement
While haven't reached END statement or past end
•If TYPE: display the argument
•If CALL: push address of CALL statement, set program counter to
address of METHOD statement
•If RETURN: pop program counter
•If COMMENT or blank line: ignore line
•If METHOD: error
•Increment program counter
Programming and Problem Solving With Java
28
Stacks: Activation Records (DPL)
Error if control reaches METHOD statement
TYPE The next statement should give a run-time error
METHOD Wrong
TYPE Control shouldn't reach here!
RETURN
Output
$ java TestDPL test1.dpl
The next statement should give a run-time error
Error: METHOD without CALL
2: METHOD Wrong
Program halted
Programming and Problem Solving With Java
29
Stacks: Activation Records (DPL)
//
//
//
//
This program implements an interpreter for a
small demonstration programming language (DPL). Each line
in DPL is a statement. Each statement begins with a keyword
and may be followed by an argument. The statements are:
//
//
//
//
//
//
//
//
//
COMMENT:
TYPE:
END:
METHOD:
RETURN:
CALL:
Line is ignored by the interpreter.
Display the argument (rest of the line) on the
screen.
End the program. The program ends automatically
if there are no more statements.
Begin a method definition. The name follows.
Return from a method. Each method must have
a RETURN statement.
Call a method by name.
// DPL is case insensitive, and allows blank lines.
import java.io.*;
import java.util.Stack;
// ----------------- DPLstatement class -----------------class DPLstatement
{
static final int
static final int
static final int
static final int
static final int
static final int
static final int
static final int
Programming and Problem Solving With Java
TYPE_COMMAND = 1;
END_COMMAND = 2;
METHOD_COMMAND = 3;
RETURN_COMMAND = 4;
CALL_COMMAND = 5;
COMMENT_COMMAND = 6;
BLANK_LINE = 7;
UNKNOWN_COMMAND = 8;
30
Stacks: Activation Records (DPL)
// Constructor: Converts a program line into an internal form
public DPLstatement(String line)
{
String commandString;
// Remove blanks on both ends of line
line = line.trim();
// Look for first blank (separates command from argument)
int blankLoc = line.indexOf(" ");
// Separate command from argument
if (blankLoc == -1)
{
commandString = line.toUpperCase();
}
else
{
commandString
= line.substring(0, blankLoc).toUpperCase();
argument = line.substring(blankLoc + 1).trim();
}
Programming and Problem Solving With Java
31
Stacks: Activation Records (DPL)
}
// Convert command to internal form
if (commandString.equals("TYPE"))
{
command = TYPE_COMMAND;
}
else if (commandString.equals("END"))
{
command = END_COMMAND;
}
else if (commandString.equals("METHOD"))
{
command = METHOD_COMMAND;
}
else if (commandString.equals("RETURN"))
{
command = RETURN_COMMAND;
}
else if (commandString.equals("CALL"))
{
command = CALL_COMMAND;
}
else if (commandString.equals("COMMENT"))
{
command = COMMENT_COMMAND;
}
else if (commandString.trim().equals(""))
{
command = BLANK_LINE;
}
else
{
command = UNKNOWN_COMMAND;
argument = line;
}
Programming and Problem Solving With Java
32
Stacks: Activation Records (DPL)
// getCommand: Returns the command as an integer
public int getCommand()
{
return command;
}
// getArgument: Returns the argument as a string (null if no
//
argument)
public String getArgument()
{
return argument;
}
Programming and Problem Solving With Java
33
Stacks: Activation Records (DPL)
// toString: Returns the statement
//
messages)
public String toString()
{
String result = "";
switch (command)
{
case TYPE_COMMAND:
result =
case END_COMMAND:
result =
case METHOD_COMMAND: result =
case RETURN_COMMAND: result =
case CALL_COMMAND:
result =
case COMMENT_COMMAND: result =
case BLANK_LINE:
result =
case UNKNOWN_COMMAND: result =
}
as a string (for error
"TYPE "; break;
"END"; break;
"METHOD "; break;
"RETURN"; break;
"CALL "; break;
"COMMENT "; break;
""; break;
""; break;
if (argument != null)
{
result = result + argument;
}
}
}
return result;
private int command;
private String argument;
Programming and Problem Solving With Java
34
Stacks: Activation Records (DPL)
// ----------------- DPL class -----------------class DPL
{
static final int MAX_STATEMENTS = 100; // Maximum number of
// statements in
// a program
// Constructor: Reads the program from the given file, returns
//
true if successful
public DPL(String fileName)
throws java.io.IOException
{
String line;
// Initialize the input file variable
File inFile = new File(fileName);
if (inFile.exists() && inFile.canRead())
{
// Create an input stream and attach it to the file
BufferedReader fileInStream
= new BufferedReader(new FileReader(inFile));
Programming and Problem Solving With Java
35
Stacks: Activation Records (DPL)
// Read lines from the file into the array
line = fileInStream.readLine();
while (numStatements < statement.length
&& line != null)
{
statement[numStatements]
= new DPLstatement(line);
numStatements++;
line = fileInStream.readLine();
}
// Make sure all lines were read
if (line != null)
{
error("Too many statements");
}
// Close the stream
fileInStream.close();
}
}
else
{
// Can't open input file
error("Can't open input file " + fileName);
}
Programming and Problem Solving With Java
36
Stacks: Activation Records (DPL)
// interpretProgram: Interprets the statements of the program
public void interpretProgram()
{
Stack runTimeStack = new Stack();
boolean stop = false;
String argument;
// Step through the program, executing statements
while (programCounter < numStatements && !stop)
{
switch (statement[programCounter].getCommand())
{
case DPLstatement.TYPE_COMMAND:
argument
= statement[programCounter].getArgument();
if (argument == null)
{
argument = "";
}
System.out.println(argument);
break;
case DPLstatement.END_COMMAND:
stop = true;
break;
case DPLstatement.METHOD_COMMAND:
error("METHOD without CALL");
break;
Programming and Problem Solving With Java
37
Stacks: Activation Records (DPL)
case DPLstatement.RETURN_COMMAND:
if (runTimeStack.empty())
{
error("RETURN command without CALL");
}
else
{
programCounter
= ((Integer) runTimeStack.pop()).intValue();
}
break;
case DPLstatement.CALL_COMMAND:
runTimeStack.push(new Integer(programCounter));
programCounter
= findMethod(statement
[programCounter].getArgument());
break;
case DPLstatement.COMMENT_COMMAND:
case DPLstatement.BLANK_LINE:
// Do nothing
break;
}
}
}
case DPLstatement.UNKNOWN_COMMAND:
error("Unknown command");
break;
programCounter++;
Programming and Problem Solving With Java
38
Stacks: Activation Records (DPL)
// findMethod: Returns the location of the METHOD command
//
with the given name
private int findMethod(String methodName)
{
methodName.toUpperCase();
for (int position = 0;
position < numStatements;
position++)
{
if (statement[position].getCommand()
== DPLstatement.METHOD_COMMAND
&& statement[position].getArgument().
equals(methodName))
{
return position;
}
}
}
error("Undefined METHOD " + methodName);
return 0;
Programming and Problem Solving With Java
39
Stacks: Activation Records (DPL)
// error: Displays the error message and halts the program
private void error(String message)
{
System.out.println("Error: " + message);
if (statement[programCounter] != null)
{
System.out.println((programCounter + 1) + ": "
+ statement[programCounter]);
}
System.out.println("Program halted");
System.exit(2);
}
}
// Instance variables
DPLstatement[] statement = new DPLstatement[MAX_STATEMENTS];
int programCounter = 0, numStatements = 0;
Programming and Problem Solving With Java
40
Stacks: Activation Records (DPL)
// ----------------- TestDPL class -----------------public class TestDPL
{
public static void main(String[] args)
throws java.io.IOException
{
DPL program = new DPL(args[0]);
program.interpretProgram();
}
}
Programming and Problem Solving With Java
41
Stacks: Activation Records (DPL2)
DPL2: Add a LOOP statement to DPL
Syntax
LOOP
...
ASK x
...
AGAIN
LOOP -- marks the top of the loop
ASK x -- user enters character, if it matches x, control
goes to statement after AGAIN, otherwise statement after
ASK
AGAIN -- jump to LOOP
Programming and Problem Solving With Java
42
Stacks: Activation Records (DPL2)
Loop statement example
LOOP
TYPE What's 4 + 5?
ASK 9
TYPE No, try again.
AGAIN
TYPE That's right!
Output
What's 4 + 5?
8
No, try again.
What's 4 + 5?
9
That's right!
Programming and Problem Solving With Java
Nested loop example
LOOP
TYPE Enter the number 1
ASK 1
LOOP
TYPE Do you know your numbers? (y/n)
ASK y
TYPE A number is between 0 and 9
AGAIN
AGAIN
TYPE Correct!
Output
Enter the number 1
X
Do you know your numbers? (y/n)
n
A number is between 0 and 9
Do you know your numbers? (y/n)
y
Enter the number 1
1
Correct!
43
Stacks: Activation Records (DPL2)
More realistic example of DPL2 (capitals.dpl)
COMMENT This is an example of the second version
COMMENT of the demonstration programming language. This
COMMENT version has loops of the form LOOP ... ASK ... AGAIN.
CALL Introduction
LOOP
CALL USAcapital
CALL NewZealandCapital
CALL GreatBritainCapital
CALL AustraliaCapital
TYPE Do you want to take this quiz again (y/n)?
ASK n
AGAIN
TYPE Bye!
END
METHOD
TYPE
TYPE
TYPE
TYPE
RETURN
Introduction
This is a quiz that tests your knowledge of country
capitals.
Here is the first question ...
Programming and Problem Solving With Java
44
Stacks: Activation Records (DPL2)
METHOD AustraliaCapital
LOOP
TYPE What is the capital city of Australia?
TYPE 1. Canberra
TYPE 2. London
TYPE 3. Washington, DC
TYPE 4. Wellington
ASK 1
TYPE Hint: The design of the capital of Australia won an
TYPE international competition in 1911.
AGAIN
RETURN
METHOD GreatBritainCapital
LOOP
TYPE What is the capital city of Great Britain?
TYPE 1. Canberra
TYPE 2. London
TYPE 3. Washington, DC
TYPE 4. Wellington
ASK 2
TYPE Hint: The capital of Great Britain is on both sides
TYPE of the Thames River.
AGAIN
RETURN
Programming and Problem Solving With Java
45
Stacks: Activation Records (DPL2)
METHOD NewZealandCapital
LOOP
TYPE What is the capital city of New Zealand?
TYPE 1. Canberra
TYPE 2. London
TYPE 3. Washington, DC
TYPE 4. Wellington
ASK 4
TYPE Hint: The capital of New Zealand is at the southern tip of
TYPE Cook Strait.
AGAIN
RETURN
METHOD USAcapital
LOOP
TYPE What is the capital city of the United States of America?
TYPE 1. Canberra
TYPE 2. London
TYPE 3. Washington, DC
TYPE 4. Wellington
ASK 3
TYPE Hint: The capital of the United States of America was named
TYPE after it's first president.
AGAIN
RETURN
Programming and Problem Solving With Java
46
Stacks: Activation Records (DPL2)
Sample run of capitals.dpl
This is a quiz that tests your knowledge of country
capitals.
Here is the first question ...
What is the capital city of the United States of America?
1. Canberra
2. London
3. Washington, DC
4. Wellington
2
Hint: The capital of the United States of America was named
after it's first president.
What is the capital city of the United States of America?
1. Canberra
2. London
3. Washington, DC
4. Wellington
3
Programming and Problem Solving With Java
47
Stacks: Activation Records (DPL2)
Sample run of capitals.dpl (continued)
What is the capital
1. Canberra
2. London
3. Washington, DC
4. Wellington
4
What is the capital
1. Canberra
2. London
3. Washington, DC
4. Wellington
2
What is the capital
1. Canberra
2. London
3. Washington, DC
4. Wellington
1
Do you want to take
n
Bye!
Programming and Problem Solving With Java
city of New Zealand?
city of Great Britain?
city of Australia?
this quiz again (y/n)?
48
Stacks: Activation Records (DPL2)
//
//
//
//
This program implements DPL2. It extends the DPL
small demonstration programming language (DPL). Each line
in DPL is a statement. Each statement begins with a keyword
and may be followed by an argument. The statements are:
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
COMMENT:
TYPE:
Line is ignored by the interpreter.
Display the argument (rest of the line) on the
screen.
END:
End the program. The program ends automatically
if there are no more statements.
METHOD:
Begin a method definition. The name follows.
RETURN:
Return from a method. Each method must have
a RETURN statement.
CALL:
Call a method by name.
LOOP ... ASK ... AGAIN:
The LOOP command begins a loop. The ASK command
asks the user for a response, and compares it to
the single character argument. If equal, control
continues with the statement following AGAIN. If
not equal, control continues with the statement
following ASK. When control reaches the AGAIN
command, it continues with the statement following
the associated LOOP command.
// DPL2 is case insensitive, and allows blank lines.
Programming and Problem Solving With Java
49
Stacks: Activation Records (DPL2)
import Keyboard;
import java.io.*;
import java.util.Stack;
// ----------------- DPLstatement class -----------------class DPLstatement
{
static final int
static final int
static final int
static final int
static final int
static final int
static final int
static final int
static final int
static final int
static final int
Programming and Problem Solving With Java
TYPE_COMMAND = 1;
END_COMMAND = 2;
METHOD_COMMAND = 3;
RETURN_COMMAND = 4;
CALL_COMMAND = 5;
COMMENT_COMMAND = 6;
BLANK_LINE = 7;
UNKNOWN_COMMAND = 8;
LOOP_COMMAND = 9;
ASK_COMMAND = 10;
AGAIN_COMMAND = 11;
50
Stacks: Activation Records (DPL2)
// Constructor: Converts a program line into an internal form
public DPLstatement(String line)
{
String commandString;
// Remove blanks on both ends of line
line = line.trim();
// Look for first blank (separates command from argument)
int blankLoc = line.indexOf(" ");
// Separate command from argument
if (blankLoc == -1)
{
commandString = line.toUpperCase();
}
else
{
commandString
= line.substring(0, blankLoc).toUpperCase();
argument = line.substring(blankLoc + 1).trim();
}
Programming and Problem Solving With Java
51
Stacks: Activation Records (DPL2)
// Convert command to internal form
if (commandString.equals("TYPE"))
{
command = TYPE_COMMAND;
}
else if (commandString.equals("END"))
{
command = END_COMMAND;
}
else if (commandString.equals("METHOD"))
{
command = METHOD_COMMAND;
}
else if (commandString.equals("RETURN"))
{
command = RETURN_COMMAND;
}
else if (commandString.equals("CALL"))
{
command = CALL_COMMAND;
}
Programming and Problem Solving With Java
52
Stacks: Activation Records (DPL2)
}
else if (commandString.equals("LOOP"))
{
command = LOOP_COMMAND;
}
else if (commandString.equals("ASK"))
{
command = ASK_COMMAND;
}
else if (commandString.equals("AGAIN"))
{
command = AGAIN_COMMAND;
}
else if (commandString.equals("COMMENT"))
{
command = COMMENT_COMMAND;
}
else if (commandString.trim().equals(""))
{
command = BLANK_LINE;
}
else
{
command = UNKNOWN_COMMAND;
argument = line;
}
Programming and Problem Solving With Java
53
Stacks: Activation Records (DPL2)
// getCommand: Returns the command as an integer
public int getCommand()
{
return command;
}
// getArgument: Returns the argument as a string (null if no
//
argument)
public String getArgument()
{
return argument;
}
Programming and Problem Solving With Java
54
Stacks: Activation Records (DPL2)
// toString: Returns the statement
//
messages)
public String toString()
{
String result = "";
switch (command)
{
case TYPE_COMMAND:
result =
case END_COMMAND:
result =
case METHOD_COMMAND: result =
case RETURN_COMMAND: result =
case CALL_COMMAND:
result =
case COMMENT_COMMAND: result =
case BLANK_LINE:
result =
case UNKNOWN_COMMAND: result =
case LOOP_COMMAND:
result =
case ASK_COMMAND:
result =
case AGAIN_COMMAND:
result =
}
as a string (for error
"TYPE "; break;
"END"; break;
"METHOD "; break;
"RETURN"; break;
"CALL "; break;
"COMMENT "; break;
""; break;
""; break;
"LOOP"; break;
"ASK "; break;
"AGAIN"; break;
if (argument != null)
{
result = result + argument;
}
}
}
return result;
private int command;
private String argument;
Programming and Problem Solving With Java
55
Stacks: Activation Records (DPL2)
// ----------------- DPL2 class -----------------class DPL2
{
static final int MAX_STATEMENTS = 100; // Maximum number of
// statements in
// a program
// Constructor: Reads the program from the given file, returns
//
true if successful
public DPL2(String fileName)
throws java.io.IOException
{
String line;
// Initialize the input file variable
File inFile = new File(fileName);
if (inFile.exists() && inFile.canRead())
{
// Create an input stream and attach it to the file
BufferedReader fileInStream
= new BufferedReader(new FileReader(inFile));
Programming and Problem Solving With Java
56
Stacks: Activation Records (DPL2)
// Read lines from the file into the array
line = fileInStream.readLine();
while (numStatements < statement.length
&& line != null)
{
statement[numStatements]
= new DPLstatement(line);
numStatements++;
line = fileInStream.readLine();
}
// Make sure all lines were read
if (line != null)
{
error("Too many statements");
}
// Close the stream
fileInStream.close();
}
}
else
{
// Can't open input file
error("Can't open input file " + fileName);
}
Programming and Problem Solving With Java
57
Stacks: Activation Records (DPL2)
// interpretProgram: Interprets the statements of the program
public void interpretProgram()
throws java.io.IOException
{
Stack runTimeStack = new Stack();
boolean stop = false;
char inputChar, correctResponse;
String argument;
// Step through the program, executing statements
while (programCounter < numStatements && !stop)
{
switch (statement[programCounter].getCommand())
{
case DPLstatement.TYPE_COMMAND:
argument
= statement[programCounter].getArgument();
if (argument == null)
{
argument = "";
}
System.out.println(argument);
break;
case DPLstatement.END_COMMAND:
stop = true;
break;
Programming and Problem Solving With Java
58
Stacks: Activation Records (DPL2)
case DPLstatement.METHOD_COMMAND:
error("METHOD without CALL");
break;
case DPLstatement.RETURN_COMMAND:
if (runTimeStack.empty())
{
error("RETURN command without CALL");
}
else
{
programCounter
= ((Integer) runTimeStack.pop()).intValue();
}
break;
case DPLstatement.CALL_COMMAND:
runTimeStack.push(new Integer(programCounter));
programCounter
= findMethod(statement
[programCounter].getArgument());
break;
case DPLstatement.COMMENT_COMMAND:
case DPLstatement.BLANK_LINE:
// Do nothing
break;
Programming and Problem Solving With Java
59
Stacks: Activation Records (DPL2)
case DPLstatement.UNKNOWN_COMMAND:
error("Unknown command");
break;
case DPLstatement.LOOP_COMMAND:
runTimeStack.push(new Integer(programCounter));
break;
case DPLstatement.ASK_COMMAND:
argument
= statement[programCounter].getArgument();
if (argument.length() != 1)
{
error("ASK argument not a single character");
}
correctResponse = argument.charAt(0);
inputChar = Keyboard.readChar();
if (Character.toUpperCase(inputChar)
== Character.toUpperCase(correctResponse))
{
if (runTimeStack.empty())
{
error("ASK command not in LOOP");
}
else
{
// Pop the location of the LOOP and toss it
runTimeStack.pop();
}
programCounter = findAgainCommand();
}
break;
Programming and Problem Solving With Java
60
Stacks: Activation Records (DPL2)
}
}
}
case DPLstatement.AGAIN_COMMAND:
// Note: this is a crude check - see exercises
if (runTimeStack.empty())
{
error("AGAIN command has no LOOP");
}
else
{
// Go back to the top of the loop (leave the LOOP
// command location on the stack)
programCounter
= ((Integer) runTimeStack.peek()).intValue();
}
programCounter++;
Programming and Problem Solving With Java
61
Stacks: Activation Records (DPL2)
// findMethod: Returns the location of the METHOD command
//
with the given name
private int findMethod(String methodName)
{
methodName.toUpperCase();
for (int position = 0;
position < numStatements;
position++)
{
if (statement[position].getCommand()
== DPLstatement.METHOD_COMMAND
&& statement[position].getArgument().
equals(methodName))
{
return position;
}
}
}
error("Undefined METHOD " + methodName);
return 0;
Programming and Problem Solving With Java
62
Stacks: Activation Records (DPL2)
// findAgainCommand: Returns the location of the AGAIN
//
command at the same level as when
//
the method started
private int findAgainCommand()
{
int loopCount = 1, position = programCounter;
while (position < numStatements - 1 && loopCount != 0)
{
position++;
switch (statement[position].getCommand())
{
case DPLstatement.LOOP_COMMAND:
loopCount++;
break;
case DPLstatement.AGAIN_COMMAND:
loopCount--;
break;
}
}
case DPLstatement.METHOD_COMMAND:
case DPLstatement.RETURN_COMMAND:
error("LOOP/AGAIN cannot cross method boundaries");
break;
if (loopCount != 0)
{
error("Missing AGAIN command");
}
}
return position;
Programming and Problem Solving With Java
63
Stacks: Activation Records (DPL2)
// error: Displays the error message and halts the program
private void error(String message)
{
System.out.println("Error: " + message);
if (statement[programCounter] != null)
{
System.out.println((programCounter + 1) + ": "
+ statement[programCounter]);
}
System.out.println("Program halted");
System.exit(2);
}
}
// Instance variables
DPLstatement[] statement = new DPLstatement[MAX_STATEMENTS];
int programCounter = 0, numStatements = 0;
// ----------------- TestDPL2 class -----------------public class TestDPL2
{
public static void main(String[] args)
throws java.io.IOException
{
DPL2 program = new DPL2(args[0]);
program.interpretProgram();
}
}
Programming and Problem Solving With Java
64
Stacks: Implementation
Simple data structure
Common implementations
Array-based (java.util.Stack uses this approach)
Link-based
We’ll examine the linked-based approach
Options
Write from scratch
Use List class (from previous chapter)
Programming and Problem Solving With Java
65
Stacks: Implementing from Scratch
Let’s write from scratch
Stack is a list of nodes (almost like List)
Can use ListNode to store nodes
One instance variable
// Instance variables
private ListNode first;
Constructor
// Constructor
public Stack()
{
first = null;
}
Programming and Problem Solving With Java
66
Stacks: Implementing from Scratch
Steps for push()
Allocate new ListNode
Copy value into node
Link new node to beginning of lis
Make new node first
Similar to List.insertFirst()
Code
// push: Pushes the item onto the stack.
public void push(Object item)
{
ListNode newNode = new ListNode(item, first);
first = newNode;
}
Programming and Problem Solving With Java
67
Stacks: Implementing from Scratch
Steps for pop()
Get value out of first node
Delete first node
Return value
Same as List.removeFirst()
Code
// pop: Returns the last item pushed onto the stack, and
//
removes it from the stack.
// Note: Stack must not be empty
public Object pop()
{
Object item;
}
Debug.assert(!empty(), "Stack.pop(): stack is empty");
item = first.getItem();
first = first.getNext();
return item;
Programming and Problem Solving With Java
68
Stacks: Implementing from Scratch
Steps for peek()
Return value of first node
Code
// peek: Returns the last item pushed onto the stack, but
//
doesn't remove it from the stack.
// Note: Stack is not empty
public Object peek()
{
Debug.assert(!empty(), "Stack.peek(): stack is empty");
return first.getItem();
}
What about this version??
// peek: Returns the last item pushed onto the stack, but
//
doesn't remove it from the stack.
// Note: Stack is not empty
public Object peek()
{
Object element = pop();
push(element);
return element;
}
Programming and Problem Solving With Java
69
Stacks: Implementing from Scratch
Steps for empty()
Return true if there’s at least one element on the stack
Return false if no elements
Code
// empty: Returns true if the stack is empty, false
//
otherwise
public boolean empty()
{
return first == null;
}
Programming and Problem Solving With Java
70
Stacks: Implementing with List
Simpler approach
Use List class to implement Stack
Options
Inheritance
Aggregation
Programming and Problem Solving With Java
71
Stacks: Implementing with List
Inheritance approach
class InheritStack extends List
{
// push: Pushes the item onto the stack.
public void push(Object element)
{
insertFirst(element);
}
// pop: Returns the last item pushed onto the stack, and
//
removes it from the stack. Stack can’t be empty
public Object pop()
{
return removeFirst();
}
// peek: Returns the last item pushed onto the stack, but
//
doesn't remove it from the stack. Stack can’t be empty
public Object peek()
{
goFirst();
return get();
}
}
// empty: Returns true if the stack is empty, false otherwise
public boolean empty()
{
return super.empty();
}
Programming and Problem Solving With Java
72
Stacks: Implementing with List
Problems with inheritance approach
InheritStack has lots of unnecessary methods (from List)
public
public
public
public
public
public
public
public
public
public
public
public
public
public
public
public
public
public
public
void insertFirst(Object item)
void insertFirst(int item)
void insertFirst(long item)
void insertLast(Object item)
void insert(Object item)
void put(Object item)
Object get()
Object removeFirst()
Object removeLast()
Object remove()
void append(List source)
boolean find(Object data)
void goFirst()
void goLast()
void goNext()
void goPrevious()
String toString()
boolean isDefined()
int count()
A stack is not a list! (Inheritance is inappropriate)
Programming and Problem Solving With Java
73
Stacks: Implementing with List
Aggregation approach (skeleton)
import List;
public class Stack
{
// push: Pushes the item onto the stack.
public void push(Object item)
{
}
// pop: Returns the last item pushed onto the stack, and
//
removes it from the stack. Stack can’t be empty
public Object pop()
{
}
// peek: Returns the last item pushed onto the stack, but
//
doesn't remove it from the stack. Stack can’t be empty
public Object peek()
{
}
// empty: Returns true if the stack is empty, false
//
otherwise
public boolean empty()
{
}
}
// Instance variables
private List data = new List();
Programming and Problem Solving With Java
74
Stacks: Implementing with List
Problems with the aggregation approach
More executable code than necessary
•import statement drags in all List methods
•Most of List methods don't apply to stacks
•Executable code size especially important for applets
Operations are slower
•Overhead of additional method calls
•List routines are more general than we need
Summary
Version
From scratch
Inheritance
Aggregation
Executable code size
Small
WRONG
Large
Programming and Problem Solving With Java
Programmer effort
Takes more time
WRONG
Easy
75
Queues
Queue is a waiting line
Common in real life
First person in line is
first person served
Queue is FIFO structure
First-in, first-out
Operations
enqueue -- put element in
dequeue -- take element out
Programming and Problem Solving With Java
76
Queues: Uses
Communication line
Between fast CPU and slow peripheral
Example: print spooler
Computer
Spooler
Printer
Example: Input buffer
Input
Buffer
Programming and Problem Solving With Java
77
Queues: Uses
Can use whenever two systems communicate
Especially when they run at different speeds
Programming and Problem Solving With Java
78
Queues: Palindromes
Palindrome: spelled the same way forward or
backward
A dog, a plan, a canal: pagoda.
A Toyota. Race fast, safe car. A Toyota
Did I draw Della too tall, Edward? I did?
Drab as a fool, aloof as a bard.
Egad, a base tone denotes a bad age.
Go hang a salami, doc. Note: I dissent, a fast never
prevents a fatness. I diet on cod, I'm a lasagna hog.
No, it can, as it is, it is a war. Raw as it is, it is an action.
Cigar? Toss it in a can. It is so tragic.
See http://www.jps.net/msyu/palindromes/ for more
Programming and Problem Solving With Java
79
Queues: Palindromes
Use a stack and queue to test for palindrome
Read input character by character
•If character is alphabetic, push and enqueue
After reading
•Compare output from stack and queue
•If the same, then we have palindrome
Programming and Problem Solving With Java
80
Queues: Palindromes
Program to test palindromes
Setup
// This program uses a stack and a queue to test
// whether the user's input is a palindrome. The user's input
// ends at the end of the line.
import java.io.*;
import java.util.Stack;
import Queue;
// Our queue class
public class TestPalindrome
{
public static void main(String[] args)
throws java.io.IOException
{
Stack stack = new Stack();
Queue queue = new Queue();
BufferedReader in
= new BufferedReader(new InputStreamReader(System.in));
char nextChar;
System.out.println("--- Palindrome Tester ---");
Programming and Problem Solving With Java
81
Queues: Palindromes
Read input, test for palindrome
// Read input from user, put each character into both the
// stack and the queue
System.out.print("Input: ");
nextChar = Character.toLowerCase((char) in.read());
while (nextChar != '\n')
{
if (Character.isLetter(nextChar))
{
stack.push(new Character(nextChar));
queue.enqueue(new Character(nextChar));
}
nextChar = Character.toLowerCase((char) in.read());
}
// Compare output of the stack and queue, stop at first
// difference
while (!stack.empty()
&& !queue.empty()
&& stack.pop().equals(queue.dequeue()))
;
Programming and Problem Solving With Java
82
Queues: Palindromes
Display output
}
}
// Display output
if (!stack.empty() && !queue.empty())
{
System.out.println("Not a palindrome");
}
else if (stack.empty() && queue.empty())
{
System.out.println("Is a palindrome");
}
else
{
System.out.println("Error in program");
}
--- Palindrome Tester --Input: Able was I ere I saw Elba.
Is a palindrome
--- Palindrome Tester --Input: The quick brown fox.
Not a palindrome
Programming and Problem Solving With Java
83
Queues: Radix Sort
Radix sort: algorithm used to sort punch cards
Punch cards used by businesses from 1890 to 1970’s
Each card stores 1 line of up to 80 characters
Characters encoded by punches in columns
12345
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 22 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 22 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 44 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 44 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 55 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 55 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 66 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 66 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 77 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 77 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 88 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 88 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 99 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 99 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9
00000000011111111112222222222333333333344444444445555555555666666666677777777778
12345678901234567890123456789012345678901234567890123456789012345678901234567890
Programming and Problem Solving With Java
84
Queues: Radix Sort
Tabulating machines could copy, print, and sort
punch cards
Sorting machine sorted cards one column at a time
To sort on more
than one character,
sort on least
significant column
first
Then sort on
next-least significant
column, etc.
Programming and Problem Solving With Java
Input bin
Output bins
85
Queues: Radix Sort
Use queues
to simulate
bins in
sorting
machine
Example:
sort 3-digit
numbers
1's Place Pass
1
2
3
4
5
6
7
8
392
485
502
181
452
985
948
385
291
queue[0]
queue[1]
181 291
queue[2]
392
502
452
queue[3]
Enqueue according
to 1's place digit
queue[4]
queue[5]
Dequeue,
copy back queue[6]
to array
485
985
385
queue[7]
First sort on
1’s place
column
Programming and Problem Solving With Java
0
queue[8]
948
queue[9]
0
1
2
3
4
5
6
7
8
181
291
392
502
452
485
985
385
948
86
Queues: Radix Sort
Example:
sort 3-digit
numbers
10's Place Pass
queue[0]
0
1
2
3
4
5
6
7
8
181
291
392
502
452
485
985
385
948
502
queue[1]
Next sort result
of 1’s place on
10’s place
column
queue[2]
queue[3]
Enqueue according
to 10's place digit
queue[4]
948
queue[5]
452
Dequeue,
copy back queue[6]
to array
queue[7]
Programming and Problem Solving With Java
queue[8]
181
485
queue[9]
291 392
985
0
1
2
3
4
5
6
7
8
502
948
452
181
485
985
385
291
392
385
87
Queues: Radix Sort
Example:
sort 3-digit
numbers
100's Place Pass
0
1
2
3
4
5
6
7
8
502
948
452
181
485
985
385
291
392
queue[0]
Finally, sort
result of 10’s
place on
100’s place
column
queue[1]
181
queue[2]
291
queue[3]
385 392
queue[4]
452 485
queue[5]
Dequeue,
copy back queue[6]
to array
Enqueue according
to 100's place digit
502
queue[7]
queue[8]
queue[9]
Programming and Problem Solving With Java
948 985
0
1
2
3
4
5
6
7
8
181
291
385
392
452
485
502
948
985
88
Queues: Radix Sort
// radixSort: The items in array are arranged in ascending order
// Note: maxPowerOf10 should give the largest power of 10 used by a value in the
//
array. For example, if the largest value in the array is 456, then
//
maxPowerOf10 is 100. Doesn't work with negative numbers.
static void radixSort(int[] array, int maxPowerOf10)
{
Queue[] queue = new Queue[10]; // One queue for each digit 0 - 9
// Create each of the 10 queues
for (int queueNum = 0; queueNum < 10; queueNum++)
{
queue[queueNum] = new Queue();
}
for (int powerOf10 = 1;powerOf10 <= maxPowerOf10; powerOf10 = powerOf10 * 10)
{
// Put each item into the queue corresponding with the
// digit in the given powerOf10 position
for (int item = 0; item < array.length; item++)
{
int digit = getDigit(array[item], powerOf10);
queue[digit].enqueue(new Integer(array[item]));
}
// Copy items from queues back to array
int item = 0;
for (int queueNum = 0; queueNum < 10; queueNum++)
{
while (!queue[queueNum].empty())
{
array[item] = ((Integer) queue[queueNum].dequeue()).intValue();
item++;
}
}
}
}
Programming and Problem Solving With Java
89
Queues: Radix Sort
getDigit() method
// getDigit: Returns the digit in the given power of 10
//
position of the number
static int getDigit(int number, int powerOf10)
{
return number % (powerOf10 * 10) / powerOf10;
}
Running time of radixSort() is O(sn), where
s is number of character per value
n is number of values
Very fast for small keys (s is small)
To work for letters, need queue for each letter
Could be improved
Use two sets of queues instead of copying back to array
on each pass
Programming and Problem Solving With Java
90
Queues: Implementation
How to write Queue class?
From scratch, using a linked list to store data
From scratch, using an array to store data
Extend the List class (No! A queue is not a list!)
Use List object inside Queue class (aggregation)
Aggregation approach: should we
Use insertFirst() for enqueueing items, and removeLast()
for dequeueing?
Use insertLast() for enqueueing items, and removeFirst()
for dequeueing?
Which is best?
Programming and Problem Solving With Java
91
Queues: Implementation
// Queue class
import List;
public class Queue
{
// enqueue: Puts a new item onto the queue
public void enqueue(Object item)
{
data.insertLast(item);
}
// dequeue: Returns the item that is on the queue longest, and removes it
// Note: Queue must not be empty
public Object dequeue()
{
return data.removeFirst();
}
// empty: Returns true if the queue is empty, false otherwise
public boolean empty()
{
return data.empty();
}
// count: Returns the number of elements in the queue
public int count()
{
return data.count();
}
}
// Instance variables
private List data = new List();
Programming and Problem Solving With Java
92
Queues: Implementation
Advantages of aggregation approach
Simple
Short
Disadvantages
Drags in the whole List class (larger executable program)
May be slower, because of the overhead of List methods
May take more storage (needs room for List references)
If Queue used a lot, may pay to write from scratch
Programming and Problem Solving With Java
93
Queues: Implementation
Example of how to use the Queue class
// Example use of the Queue class
import Queue;
public class DemonstrateQueue
{
public static void main(String[] args)
{
Queue stringQueue = new Queue();
// Put elements into the queue
stringQueue.enqueue("First");
stringQueue.enqueue("Second");
stringQueue.enqueue("Third");
}
}
// Get elements out of the queue
System.out.println(stringQueue.dequeue());
System.out.println(stringQueue.dequeue());
System.out.println(stringQueue.dequeue());
Programming and Problem Solving With Java
94
Computer Simulation
Simulation: imitate something that exists in the real
world
Goal of simulation
Summarize performance of a system
Predict performance of a design
To simulate, build model
Concentrate on essential features
Abstract model
Mathematical equations or computer program
Programming and Problem Solving With Java
95
Simulation: Advantages
Can test many designs before building physical
prototype
Wright brothers tested about 200 wing designs in a small
wind tunnel
Usually safer
Radar operators, airplane pilots often learn on simulators
Often cheaper
Fighter jet simulators are much cheaper than real jets
($65 million or more for some...)
Programming and Problem Solving With Java
96
Simulation
Many simulations are similar to computer games
Flight simulators are more realistic
Real instruments
Much larger view (several screens)
Hydraulic systems rotate and pitch the simulator
Metal plates push on pilot’s back to simulate acceleration
Virtual reality (VR)
Attempt to put user in new environment
Still expensive for individuals
Programming and Problem Solving With Java
97
Simulation: Uses
Economics
Model economy of nation, region
Business
Model inventories, new management strategies
Science
Visualization of data
Programming and Problem Solving With Java
98
Simulation: Approaches
Two major approaches in simulation
Analytic
Numeric
Analytic approach
In the form of mathematical equations
Solve equations to get exact answer
Use algebra and calculus
Advantage: insight and mathematical relationship
Disadvantage: requires advanced math, may not be
feasible for some models
Programming and Problem Solving With Java
99
Simulation: Approaches
Second approach: numeric
Build model as computer program
Put input in, watch outputs
Deterministic model
Doesn’t depend on random events
Can try all input values (if not too many), giving complete
set of outputs
Usually too many input values for this
Random model
Depends on random events (customer arrivals)
Programming and Problem Solving With Java
100
Simulation: Approaches
Advantage of numeric approach
Works in more cases than analytic
Disadvantages
Can have noise (unlikely outputs) in results
Must do many simulations to smooth over noise
Must vary inputs to see how small changes affect outputs
(sensitivity analysis)
Programming and Problem Solving With Java
101
Simulation: Random Numbers
Use random number generator in random
simulation
Java’s java.util.Random is a class for random number
generation
Random.nextInt() method produces integers between
-2,147,483,648 and 2,147,483,647
Pseudorandom: uses algorithm to produce numbers, not
truly random
Sequence of pseudorandom numbers eventually repeats
(but sequence is long enough to appear random for most
purposes)
Programming and Problem Solving With Java
102
Simulation: Random Numbers
To get a random integer between 3 and 9 (say):
Get a random integer with Random.nextInt()
Make sure the number is positive with Math.abs()
Adjust the number to between 0 and 6 with n % 7
Add 3 to the result to get a number between 3 and 9
To make it easier, let’s write a new class
// An extension of the Random class (first version)
import java.util.Random;
public class ExtendedRandom extends Random
{
// nextIntUniform: Returns an int random value between
//
lowValue and highValue, inclusive
public int nextIntUniform(int lowValue, int highValue)
{
return Math.abs(nextInt()) % (highValue - lowValue + 1)
+ lowValue;
}
}
Programming and Problem Solving With Java
103
Simulation: Random Numbers
Uniform distribution
Each number is equally likely to appear next
Appropriate for simulating the same behavior in the real
world
Example: roll of a six-sided die
// Simulate rolling a six-sided die
import ExtendedRandom; // Get our extended random class
public class SimulateADie
{
public static void main(String[] args)
{
ExtendedRandom gen = new ExtendedRandom();
}
}
System.out.println("The number is " + gen.nextIntUniform(1, 6));
Programming and Problem Solving With Java
104
Simulation: Random Numbers
Uniform distribution
Plot of 50,000 calls to ExtendedRandom.nextIntUniform()
700
600
Count
500
400
300
200
100
0
0
10
20
30
40
50
60
70
80
90
100
V a lu e s
Programming and Problem Solving With Java
105
Simulation: Random Numbers
// Test the random number generator by
// counting the number of times each value is generated.
import ExtendedRandom; // Get our extended random class
class TestRandomUniform
{
static final int LOW_VALUE = 0;
static final int HIGH_VALUE = 100;
static final int NUM_TESTS = 50000;
public static void main(String[] args)
{
ExtendedRandom generator = new ExtendedRandom();
int[] count = new int[HIGH_VALUE - LOW_VALUE + 1];
// Use random number generator, count results
for (int i = 0; i < NUM_TESTS; i++)
{
int uniformValue
= generator.nextIntUniform(LOW_VALUE, HIGH_VALUE);
count[uniformValue]++;
}
}
}
// Display counts
for (int i = 0; i < count.length; i++)
{
System.out.println(i + "\t" + count[i]);
}
Programming and Problem Solving With Java
106
Simulation: Random Numbers
Most naturally-occurring events don’t follow uniform
distribution
Tendency to
cluster around
a central value
Normal
distribution
follows this
pattern
0.4
0.3
y 0.2
0.1
0
-4
-3
-2
-1
0
1
2
3
4
x
Programming and Problem Solving With Java
107
Simulation: Random Numbers
Normal distribution described by
Average
Standard deviation from the average
0.4
0.3
Average of 75
Standard deviation of 10
y 0.2
0.1
0
35
45
55
65
75
85
95
105
115
x
Programming and Problem Solving With Java
108
Simulation: Random Numbers
Normal distribution
Area under curve one standard deviation from average is
about 68% of all cases
0.4
0.3
Average of 75
Standard deviation of 10
y 0.2
0.1
0
35
45
55
65
75
85
95
105
115
x
Programming and Problem Solving With Java
109
Simulation: Random Numbers
Normal distribution
Area under curve two standard deviations from average
is about 95% of all cases
0.4
0.3
Average of 75
Standard deviation of 10
y 0.2
0.1
0
35
45
55
65
75
85
95
105
115
x
Programming and Problem Solving With Java
110
Simulation: Random Numbers
Random.nextGaussian() simulates normal
distribution
Returns double with average 0.0, standard deviation 1.0
To simulate other normal distributions
Multiply result by desired standard deviation
Add desired average
Example: want average 75, standard deviation 10
Suppose Random.nextGaussian() returns 0.65
Multipy by 10  65.0
Add 75  140.0
Programming and Problem Solving With Java
111
Simulation: Random Numbers
To make generating other normal distributions
easier, let’s add to the ExtendedRandom class
// An extension of the Random class (second version)
import java.util.Random;
public class ExtendedRandom extends Random
{
// nextIntUniform: Returns an int random value between
//
lowValue and highValue, inclusive
public int nextIntUniform(int lowValue, int highValue)
{
return Math.abs(nextInt()) % (highValue - lowValue + 1)
+ lowValue;
}
}
// nextGaussian: Returns a double random value from the
//
the normal distribution with the given average
//
and standard deviation
public double nextGaussian(double average,
double standardDeviation)
{
return super.nextGaussian() * standardDeviation + average;
}
Programming and Problem Solving With Java
112
Simulation: Random Numbers
Program example: normal distribution
// This program shows how to use the nextGaussian()
// method to simulate a normal distribution.
import ExtendedRandom; // Get our extended random class
import Keyboard;
public class DemonstrateNormalDistribution
{
public static void main(String[] args)
throws java.io.IOException
{
ExtendedRandom gen = new ExtendedRandom();
System.out.println("--- Generate normally distributed "
+ "random numbers ---");
double average = Keyboard.readDouble("Average: ");
double stDev = Keyboard.readDouble("Standard deviation: ");
int numValues = Keyboard.readInt("Number of values: ");
System.out.println();
}
}
for (int i = 0; i < numValues; i++)
{
System.out.println(gen.nextGaussian(average, stDev));
}
Programming and Problem Solving With Java
113
Simulation: Random Numbers
Program output
--- Generate normally distributed random numbers --Average: 50
Standard deviation: 20
Number of values: 10
25.950240164331642
44.12825318419088
29.18331540214599
34.67382968777139
55.861038140391315
57.50616024442746
28.79122430095662
63.642425108500944
63.01636566587443
58.50500464319739
Programming and Problem Solving With Java
114
Simulation: Random Numbers
Normal distribution
Plot of 50,000 calls to ExtendedRandom.nextGaussian()
2500
Count
2000
1500
1000
500
0
0
10 20 30 40 50 60 70 80 90 100 110 120 130 140
Values
Programming and Problem Solving With Java
115
Simulation: Random Numbers
// Test the random number generator by counting
// the number of times each (integer) value is generated.
import ExtendedRandom; // Get our extended random class
class TestRandomNormal
{
static final int AVERAGE = 75;
// Must be positive and
// at least 3 * STD_DEV
static final int STD_DEV = 10;
// Must be positive
static final int NUM_TESTS = 50000;
public static void main(String[] args)
{
ExtendedRandom generator = new ExtendedRandom();
int[] count = new int[AVERAGE * 2];
// Use random number generator, count results
for (int i = 0; i < NUM_TESTS; i++)
{
double normalValue = generator.nextGaussian(AVERAGE, STD_DEV);
int arrayLocation = (int) Math.round(normalValue);
count[arrayLocation]++;
}
}
}
// Display counts
for (int i = 0; i < count.length; i++)
{
System.out.println(i + "\t" + count[i]);
}
Programming and Problem Solving With Java
116
Simulation: Waiting Lines
Queueing model
Customers: wait in line for service
Servers: provide service to customers
Simulate
Waiting lines in stores
Street intersections
Logistic problems in factories
Computer job processing
Programming and Problem Solving With Java
117
Simulation: Waiting Lines
By the way...
That’s a lot of vowels in a row!
(The most of any word in English)
Programming and Problem Solving With Java
118
Simulation: Waiting Lines
Simplest waiting line simulation
One waiting line
One server
Server
Programming and Problem Solving With Java
Customers
119
Simulation: Waiting Lines
Another common type of waiting line
Servers
Customers
Programming and Problem Solving With Java
120
Simulation: Waiting Lines
Yet another...
Servers
Programming and Problem Solving With Java
Customers
121
Simulation: Waiting Lines
Ways to service the lines
FIFO: First in first out (most common)
LIFO: Last in first out (sometimes used in inventory
accounting)
Priority first: Customer with highest priority served first
(print queue -- shortest printout printed first)
Circular: The customers arranged in a circle; each
customer gets a little service, then the server moves on.
(CPU allocation)
Random: A random customer served first
Programming and Problem Solving With Java
122
Simulation: Waiting Lines
We’ll write a program that simulates waiting lines
Single waiting line
Several servers
Use FIFO for serving each line
Simplifying assumptions
Arrival rate of customers uniformly distributed
Service time is normally distributed
Servers are equally efficient
One customer arrives during each time unit
Several servers can start serving customers during each
time unit
Customers don’t leave the line
Programming and Problem Solving With Java
123
Simulation: Waiting Lines
General approach
Get user input (number of servers, average service time,
time to simulate, etc.)
For each time from 0 to time to simulate,
•If new customer arrives, put at end of line
•While there's someone in line and a server available,
–Have an available server serve customer from front of line
–Accumulate statistics on this customer
Display the statistics
Programming and Problem Solving With Java
124
Simulation: Waiting Lines
In simulation, time is an integer counter
Don’t have to make the program run in real time
Let it run as fast as computer can run it
Arrival probability
User enters number between 0 and 100
This is probability that customer will arrive during any
time unit
Will use Random.nextInt() to generate a number between
0 and 100
If the random number < arrival probability, then will
simulate customer arrival
Programming and Problem Solving With Java
125
Simulation: Waiting Lines
Keep track of customer by arrival time
Store customers in queue: just store arrival time for each
When customer ready to be served
Server will choose random service time from normal
distribution
Departure time = arrival time + service time
Server will store customer’s departure time
Use list to store servers
Programming and Problem Solving With Java
126
Simulation: Waiting Lines
Servers class: stores all servers
Instance variables
// Instance variables
List serverList = new List();
double average, standardDeviation;
Random randGen = new Random();
Constructor
Puts -1 in each server’s departure time, so its departure
time < current time (means ready)
// Constructor
public Servers(int numServers,
double average, double standardDeviation)
{
this.average = average;
this.standardDeviation = standardDeviation;
}
// Initialize servers
for (int i = 0; i < numServers; i++)
{
serverList.insertFirst(-1);
}
Programming and Problem Solving With Java
127
Simulation: Waiting Lines
Servers.findAvailable()
Server is available if departure time < current time
// findAvailable: Returns true if at least one server is
//
available, and if so, sets the current
//
server to an available one
public boolean findAvailable(int currentTime)
{
for (serverList.goFirst(); serverList.isDefined();
serverList.goNext())
{
int serverTimeUp
= ((Integer) serverList.get()).intValue();
if (serverTimeUp < currentTime)
{
return true;
}
}
return false;
}
Programming and Problem Solving With Java
128
Simulation: Waiting Lines
Server.serveCustomer()
Requires a server to be available first
// serveCustomer: Adds a customer to an available server, sets the
//
departure time for the customer in the server
// Note: A server must be available and that server is the current
//
server
public void serveCustomer(int currentTime)
{
// Check precondition
int serverTimeUp
= ((Integer) serverList.get()).intValue();
Debug.assert(serverTimeUp < currentTime,
"Server.serveCustomer(): No server available");
}
// Record the departure time for this customer in the server
int departureTime = currentTime
+ (int) (Math.round(randGen.nextGaussian())
* standardDeviation + average);
serverList.put(new Integer(departureTime));
Programming and Problem Solving With Java
129
Simulation: Waiting Lines
Server.numServing()
// numServing: Returns the number of servers serving customers at
//
currentTime. Also resets current server.
public int numServing(int currentTime)
{
int count = 0;
}
for (serverList.goFirst(); serverList.isDefined();
serverList.goNext())
{
int serverTimeUp
= ((Integer) serverList.get()).intValue();
if (serverTimeUp >= currentTime)
{
count++;
}
}
return count;
Programming and Problem Solving With Java
130
Simulation: Waiting Lines
WaitingLine class
Does most of the work
Keeps track of servers, line of customers, all statistics
Instance variables
// Instance variables
Servers servers;
Random randGen = new Random();
Queue customerLine = new Queue();
int totalWaitTime = 0;
int longestWaitTime = 0;
int longestLine = 0;
int customersServed = 0;
int customersBeingServed;
Programming and Problem Solving With Java
131
Simulation: Waiting Lines
WaitiingLine constructor steps:
For each time from 0 to the time to simulate,
•If new customer arrives, put that customer at end of the line
•While there's someone in the line and a server available,
–Have an available server serve the customer at front of line
–Accumulate statistics on this customer
Constructor code
// Constructor: Simulates a single waiting line with numServers
//
servers for timeToSimulate time units. Each
//
server takes the given average amount of time
//
to service one customer, with the given standard
//
deviation
public WaitingLine(int numServers, int arrivalProb,
double averageServeTime,
double standardDev,
int timeToSimulate)
{
int arriveTime, waitTime;
Programming and Problem Solving With Java
132
Simulation: Waiting Lines
Constructor code (continued)
servers = new Servers(numServers, averageServeTime,
standardDev);
for (int currentTime = 0; currentTime < timeToSimulate;
currentTime++)
{
if (Math.abs(randGen.nextInt()) % 100 < arrivalProb)
{
// Have a new arrival - put into the queue
customerLine.enqueue(new Integer(currentTime));
}
// Keep servers busy if anyone in line
while (!customerLine.empty()
&& servers.findAvailable(currentTime))
{
// Available server serve customer at front of line
arriveTime
= ((Integer) customerLine.dequeue()).intValue();
servers.serveCustomer(currentTime);
Programming and Problem Solving With Java
133
Simulation: Waiting Lines
Constructor code (continued)
// Accumulate statistics on this customer
waitTime = currentTime - arriveTime;
totalWaitTime = totalWaitTime + waitTime;
if (waitTime > longestWaitTime)
{
longestWaitTime = waitTime;
}
if (customerLine.count() > longestLine)
{
longestLine = customerLine.count();
}
customersServed++;
}
}
}
customersBeingServed
= servers.numServing(timeToSimulate);
Programming and Problem Solving With Java
134
Simulation: Waiting Lines
WaitingLine:displayResults()
// displayResults: Displays the results of the simulation
public void displayResults()
{
System.out.println("---- Results ----");
System.out.println(" Customers served:
"
+ customersServed);
if (customersServed > 0)
System.out.println(" Average wait time:
"
+ Format.pad((double) totalWaitTime
/ customersServed, 0, 2));
System.out.println(" Longest wait time:
"
+ longestWaitTime);
System.out.println(" Longest line:
"
+ longestLine);
System.out.println(" Customers still waiting:
"
+ customerLine.count());
System.out.println(" Customers still being served: "
+ customersBeingServed);
}
Programming and Problem Solving With Java
135
Simulation: Waiting Lines
Example use of program
Restaurant has two cashiers
30% chance that a new customer will arrive in any
minute
Average of 5 minutes to serve a customer, standard
deviation of 3 minutes
Should the manager hire another cashier?
Programming and Problem Solving With Java
136
Simulation: Waiting Lines
Two sample runs of the program
Number of servers: 2
Probability of arrival during each time unit: 30
Average service time: 5
Standard deviation of service time: 3
Time to simulate: 600
---- Results ---Customers served:
184
Average wait time:
0.97
Longest wait time:
8
Longest line:
4
Customers still waiting:
1
Customers still being served: 2
---- Waiting Line Simulation ---Number of servers: 3
Probability of arrival during each time unit: 30
Average service time: 5
Standard deviation of service time: 3
Time to simulate: 600
---- Results ---Customers served:
170
Average wait time:
0.56
Longest wait time:
6
Longest line:
3
Customers still waiting:
0
Customers still being served: 3
Programming and Problem Solving With Java
137
Simulation: Waiting Lines
Other runs give different results
---- Waiting Line Simulation ---Number of servers: 2
Probability of arrival during each time unit: 30
Average service time: 5
Standard deviation of service time: 3
Time to simulate: 600
---- Results ---Customers served:
186
Average wait time:
11.95
Longest wait time:
46
Longest line:
15
Customers still waiting:
4
Customers still being served: 1
---- Waiting Line Simulation ---Number of servers: 2
Probability of arrival during each time unit: 30
Average service time: 5
Standard deviation of service time: 3
Time to simulate: 600
---- Results ---Customers served:
183
Average wait time:
6.80
Longest wait time:
20
Longest line:
7
Customers still waiting:
1
Customers still being served: 2
Programming and Problem Solving With Java
138
Simulation: Waiting Lines
Different runs give very different results
Should run the simulation longer (or more times) to get a
better feel for results
Also should do sensitivity analysis: how do small input
changes affect the output?
Programming and Problem Solving With Java
139
Simulation: Other Distributions
The gamma distribution
Often used to simulate servers
Is a skewed distribution
Takes two parameters,,  (must be determined
empirically
Add to ExtendedRandom...
// nextDoubleGamma: Returns a double random value from
//
the gamma distribution given by alpha
//
and beta
public double nextDoubleGamma(int alpha, int beta)
{
double product = 1.0;
for (int i = 0; i < alpha; i++)
{
product = product * nextDouble();
}
}
return (-beta) * Math.log(product);
Programming and Problem Solving With Java
140
Simulation: Other Distributions
Gamma distribution
 determines amount of skew
1.2
1
f(x)
0.8
=1
0.6
0.4
=2
=3
0.2
0
0
3
0.
6
0.
9
0.
2
1.
5
1.
8
1.
1
2.
4
2.
7
2.
3
3
3.
6
3.
9
3.
2
4.
5
4.
8
4.
x
Programming and Problem Solving With Java
141
Simulation: Other Distributions
Gamma distribution with  = 2,  = 1
2000
1800
1600
Count
1400
1200
1000
800
600
400
200
19
18
16
15
14
13
11
10
9.
7.
6.
5.
3.
2.
1.
0
0
Values
Programming and Problem Solving With Java
142
Simulation: Other Distributions
The Poisson distribution
Used to simulate customer arrivals in waiting line
simulations (also number of accidents, cars arriving at
intersection, telephone calls at a switchboard, ...)
Models time from one customer to the next one
Takes one parameter,  (average events per time unit)
Add to ExtendedRandom...
// nextDoublePoisson: Returns a normally distributed random
//
value from the Poisson distribution given
//
by alpha
double nextDoublePoisson(int alpha)
{
double product = 1.0;
int k = 0;
while (product >= Math.exp(-alpha))
{
product = product * nextDouble();
k++;
}
}
return k;
Programming and Problem Solving With Java
143
Simulation: Other Distributions
Poisson distribution with  = 75
2500
Count
2000
1500
1000
500
0
0
10
20
30
40
50
60
70
80
90
100 110
Values
Programming and Problem Solving With Java
144