A common occurrence on comp.lang. java is a post questioning the ability to create growable data structures in Java. The common belief tends to be that pointers are necessary to implement a growable data structure. This obviously stems from experience with languages like C or Pascal, where one is forced to manipulate pointers to track memory in growable data structures. If you think about the data structures, however, all that is really necessary to implement these systems is the ability to dynamically allocate memory. Dynamic memory allocation, a fundamental part of any modern programming language, is actually much easier to handle in Java than in C or Pascal. This is obviously due, in part, to Java's automatic garbage collection. Not only does Java provide for easier memory management, but it also provides several useful classes and interfaces which aid in the creation of data structures. This month's General Java column will cover creation of stacks, queues, and trees in Java.

Two classes: java.util.Stack and java.util.Vector, provide a series of methods which make the implementation of stacks and queues very easy. Java.util.Stack, as the name implies, implements the standard suite of stack methods. Java.util.Vector is a growable array which lends itself to the creation of not only queues, but also to a variety of data structures. Since Java is almost completely object based, these classes were written to handle Objects. While this is usually what we will want to store, there are times when one might want to create a stack which deals with the primitive data types. For instance, if I were writing an application which takes a reverse-Polish equation as a command line argument, and returns the value of that expression, I would want to create a stack which manages floats (or doubles, or longs, depending on the required precision).

Fortunately, all basic data types have corresponding objects, called wrapper classes, and conversion between a data-type and its wrapper class is quite easy. Listing 1 demonstrates conversion between the int type, and the Integer object.

Table 1 shows all primitive data types, and their corresponding wrapper classes. Table 2 gives examples for initializing each primitive type, its corresponding wrapper class, and gives examples for converting back and forth between the two. As you can see the methods are all quite syntactically similar.

Now that we understand how the wrapper classes work, let's try out an implementation which realizes our earlier example: reverse Polish computations. Since we will be handling floats and not objects we will want, in true OO principle, to write a class which extends java.util.Stack to facilitate the conversion between the float primitive type and its wrapper class, Float. This will make the translation between float and Object completely transparent to the user. Listing 2 shows the class floatStack.

Obviously push, pop, and empty are not the only methods supported by java.util.Stack; there additionally are peek, and search methods. Full descriptions are contained in the API. To demonstrate our floatStack, we will need to develop a driver which will handle the reverse Polish algorithm. Additionally one would have to write a main method which would handle the i/o, and calling of the postFixEval method. The driver is shown in Listing 3. Note that for space reasons, all of the helper methods are not listed. Their names are totally intuitive however.

Obviously it is quite easy to work with stacks in Java. This ease with which we manipulate growable data structures carries over to the next two examples that we will develop, queues and trees. Once we develop all three data structures, we will combine them together. It should not be a problem for you to understand how the data structures operate however.

Where a stack is a LIFO (last-in first-out) data structure, a queue is a FIFO (first-in first-out) data structure. In C or Pascal if we were developing a queue, we would have to write functions to dynamically allocate memory, and then free it back to the system heap after we were done with it. Also we would need to manipulate pointers so we could access the values stored in our stack. As previously stated, it is possible to build a queue which takes advantage of the class java.util.Vector. In contrast to the stack which we built, the queue will handle standard Objects. Perhaps you built a program which accepted an ToDo object. Each instance would have a job, its cost, who ordered it, etc. As new job were given to you, they would be added to the queue. Then when you were ready to work on a job you would take one off the queue. In taking advantage of java.util.Vector, we will use the following methods: addElement( Object ). This will be modified to act as our put( Object ) method, isEmpty() this will be modified to act as our isEmpty() method, and elementAt( int ), and removeElementAt( int ) will be used to act as our get( Object ) method. The class is shown Listing 4.

Again we see how easy it is to take advantage of readily available classes to develop our own classes. I have found that by curling up with a copy of the API every night, I have been able to find classes which are a large time-saver.

While the first two data structures were not too difficult, the third, our binary tree, will be slightly more complex. While most of this code will be pretty self explanatory, the insert method might arouse some need for question. Of course you are familiar with the new operator when creating new objects; using it recursively is no different. This method is shown in Listing 5; we will examine it prior to presenting the entire class.

Since trees are inherently recursive, writing this method any other way would be too difficult. Binary trees store data which is increasing less as we descend down through its left children. Conversely data which is increasing greater is stored in the tree's right children. On line 2 of the method we test to see if the int in question is less than int which is in that position. If it is, we know that the int in question must be a left child of the current node. Knowing this we must decide whether the tree continues down deeper, or whether the left child is null. Line 3 tests to see if the left child is null, if it is we recursively call the method with left as the current node, and attempt the same tests. Once we get to the point were a node is not null we know that our int has found its home. Since the child of any node is also a node with children of its own, we create a new node with the int in question as the parent. This node becomes attached to its parent, and our tree grown indefinitely.

Now let's examine the entire class (shown in Listing 6). Note that the init() method takes care of setting the int passed to the tree to null, and sets its children to null.

We have our tree structure; now what? What most of you are probably thinking is that our postfix algorithm could be coupled with a tree structure to allow for the creation on an infix calculator. Try this out; the implementation is rather simple and would be a great test of your understanding of the subject matter!