HomeDigital EditionSys-Con RadioSearch Java Cd
Advanced Java AWT Book Reviews/Excerpts Client Server Corba Editorials Embedded Java Enterprise Java IDE's Industry Watch Integration Interviews Java Applet Java & Databases Java & Web Services Java Fundamentals Java Native Interface Java Servlets Java Beans J2ME Libraries .NET Object Orientation Observations/IMHO Product Reviews Scalability & Performance Security Server Side Source Code Straight Talking Swing Threads Using Java with others Wireless XML
 

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.

Table 1 Table 2

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!

About the Author
Luke Cassady-Dorion is currently finishing his degree in Computer Science at Drexel University in Philadelphia, PA. Additionally he heads up Java Development for Odyssey Systems Corporation (www.iliad.com) in Manayunk, PA.

	

Listing 1: Conversion from an int to an Integer

//first we declare the variables
int		myInt;
Integer	myInteger;

//give myInt a value of 5
myInt = 5;

//now create a new Integer object with contains the value 5
myInteger = new Integer( myInt );

//the value can be pulled out of the Integer object 
//with the following line
int theInt = myInteger.intValue();

Listing 2: The floatStack class extends Stack to allow floats as input

//declare the class
//note that most of this code can be explained 
//by tables x.1, and x.2 in
//cases where
//it is not, comments have been added.
class floatStack extends java.util.Stack {

//we'll need to be able to push onto the stack
public Object Push( float f ) {
Float myFloat = new Float( f );
return super.push( myFloat );
} //Push

//and we will need to be able to pop back off the stack
public float Pop() {
try { return (super.pop()).floatValue(); }
catch ( EmptyStackException e ) {}
} //Pop

//we will need to check if the stack is empty, this class
//actually does not need to appear in our floatStack 
//declaration as it is identical to the empty method 
//contained in java.util.Stack. It was provided for 
//stylistic reasons only.
public boolean Empty() {
return super.empty()
}
} //class

Listing 3: The postFixExal function

public float postFixEval( String inputString ) {
char token;
int intToken;
//length = size of array
len = inputString.length();
//make array of characters in input string
char[] inputArray = new char[len];
inputArray = inputString.toCharArray();
//computations go on here
while ( moreTokens(inputArray[]) ) {
	//get next token
	token = inputArray[i];
	//is it an int? if so push onto evalStack
	if ( this.isInt(token) ) {
		intToken = toInt(token);
		evalStack.Push((float)intToken);
	}

//binary operator, eval top two ints and 
//push result onto stack
else if ( this.isBinary(token) ){
try { float opp2 = evalStack.Pop(); }
catch ( EmptyStackException e ) {}
try { float opp1 = evalStack.Pop(); }
catch ( EmptyStackException e ) {}
evalStack.Push( evalBinary(opp1, opp2, token) );
}

//unary operator
	else {
	try { float opp = evalStack.Pop(); }
	catch ( EmptyStackException e ) { }
	evalStack.Push( evalUnary(opp, token) );
	}
}
try { return evalStack.Pop(); }
catch ( EmptyStackException e ) { }
}

Listing 4: A queue class

class queue {
private Vector queueVector = new Vector();
private Object tempObject;

//constructor
public queue() {
queueVector = new Vector();
}

//our put method
public void put( Object i ) {
//addElement adds at the vector, this is what we need
queueVector.addElement( i );
}

//the get method
public Object get() {
try { tempObject = queueVector.firstElement(); }
catch ( NoSuchElementException e ) {}
try { queueVector.removeElementAt( 0 ); }
catch ( ArrayIndexOutOfBoundsException e) {}
return tempObject;
}

public Object top() {
try { tempObject = queueVector.firstElement(); }
catch ( NoSuchElementException e ) {}
return tempObject;
}

public boolean isEmpty() {
return queueVector.isEmpty()
}

}

 note that the line numbers
next to this method are so i can easily refer to the code as I step through
it. The code should be laid out in a way such that the line numbers are
obviously not part of the code.


Listing 5: The insert method

1.	public void insert( int i ) {
2.	if (i < key) {
3.	  if (left != null)
4.	    left.insert( i );
5.	  else
6.	    left = new binaryTree( i );
7.	} else if (i > key) {
8.	if (right != null)
9.	  right.insert( i );
10.	else
11.	right = new binaryTree( i );
12.   }
13. }

Listing 6: Our binaryTree class

class binaryTree {
private int key;
public binaryTree left;
public binaryTree right;

//constructor
public binaryTree( int i ) {
	key = i;
	this.left = null;
	this.right = null;
}

//returns the current value of key
public int getKey() {
return this.key;
}

//allows us to alter the value of key
private void setKey( int k ) {
this.key = k;
}

//inserts the new int at its correct position
public void insert( int i ) {
if (i <= key) {
      if (left != null)
                left.insert( i );
            else
                left = new binaryTree( i );
        } else if (i >= key) {
            if (right != null)
                right.insert( i );
            else
                right = new binaryTree( i );
        }
    }
}


 

All Rights Reserved
Copyright ©  2004 SYS-CON Media, Inc.
  E-mail: [email protected]

Java and Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. SYS-CON Publications, Inc. is independent of Sun Microsystems, Inc.