This lab illustrates the following concepts

• stacks
• trees
• hash functions

Some useful links:

Sun libraries documentation

UW library documentation

I) Stacks

Sample: EmptyStackException.java, ExpressionFormatException.java, PostfixInfixCalculator.java, Stack.java

Solution: Stack.java

II) Trees

Sample: BSTree.java, TestTree.java

Solution (close but not exactly the solution to the sample. This solution has more features): BSTree.java, TestTree.java

III) Hashing

Given the input {4371, 1323, 6173, 4199, 4344, 9679, 1989}, a fixed table size of 10, and hash function hash(x) = x % 10, show the resulting

• Linear probing hash table
• Quadratic probing hash table
• Separate chaining hash table

Solution