Java Data Structures - Contents
A D V E R T I S E M E N T
The next and more serious data structure we'll
examine is the Stack. A stack is a FILO (First In, Last Out), structure. For now, we'll
just deal with the array representation of the stack. Knowing that we'll be using an
array, we automatically think of the fact that our stack has to have a maximum size.
A stack has only one point where data enters or
leaves. We can't insert or remove elements into or from the middle of the stack. As I've
mentioned before, everything in Java is an object, (since it's an Object Oriented
language), so, lets write a stack object!
public class pArrayStackInt{
protected int head[];
protected int pointer;
public pArrayStackInt(int capacity){
head = new int[capacity];
pointer = -1;
}
public boolean isEmpty(){
return pointer == -1;
}
public void push(int i){
if(pointer+1 < head.length)
head[++pointer] = i;
}
public int pop(){
if(isEmpty())
return 0;
return head[pointer--];
}
}
As you can see, that's the stack class. The
constructor named pArrayStackInt() accepts an integer. That integer is to
initialize the stack to that specific size. If you later try to push() more
integers onto the stack than this capacity, it won't work. Nothing is complete without
testing, so, lets write a test driver class to test this stack.
import java.io.*;
import pArrayStackInt;
class pArrayStackIntTest{
public static void main(String[] args){
pArrayStackInt s = new pArrayStackInt(10);
int i,j;
System.out.println("starting...");
for(i=0;i<10;i++){
j = (int)(Math.random() * 100);
s.push(j);
System.out.println("push: " + j);
}
while(!s.isEmpty()){
System.out.println("pop: " + s.pop());
}
System.out.println("Done ;-)");
}
}
The test driver does nothing special, it inserts ten
random numbers onto the stack, and then pops them off. Writing to standard output exactly
what it's doing. The output gotten from this program is:
starting...
push: 33
push: 66
push: 10
push: 94
push: 67
push: 79
push: 48
push: 7
push: 79
push: 32
pop: 32
pop: 79
pop: 7
pop: 48
pop: 79
pop: 67
pop: 94
pop: 10
pop: 66
pop: 33
Done ;-)
As you can see, the first numbers to be pushed on,
are the last ones to be popped off. A perfect example of a FILO structure. The output also
assures us that the stack is working properly.
Now that you've had a chance to look at the source,
lets look at it more closely.
The pArrayStackInt class is using an
array to store it's data. The data is int type (for simplicity). There is a
head data member, that's the actual array. Because we're using an array, with limited
size, we need to keep track of it's size, so that we don't overflow it; we always look at head.length
to check for maximum size.
The second data member is pointer.
Pointer, in here, points to the top of the stack. It always has the position which had the
last insertion, or -1 if the stack is empty.
The constructor: pArrayStackInt(),
accepts the maximum size parameter to set the size of the stack. The rest of the functions
is just routine initialization. Notice that pointer is initialized to -1, this makes the
next position to be filled in an array, 0.
The isEmpty() function is self
explanatory, it returns true if the stack is empty (pointer is
-1), and false otherwise. The return type is boolean.
The push(int) function is fairly easy
to understand too. First, it checks to see if the next insertion will not overflow the
array. If no danger from overflow, then it inserts. It first increments the pointer and
then inserts into the new location pointed to by the updated pointer. It
could easily be modified to actually make the array grow, but then the whole point of
"simplicity" of using an array will be lost.
The int pop() function is also very
simple. First, it checks to see if stack is not empty, if it is empty, it will return 0.
In general, this is a really bad error to pop of something from an empty stack. You may
want to do something more sensible than simply returning a 0 (an exception throw would not
be a bad choice). I did it this way for the sake of simplicity. Then, it returns the value
of the array element currently pointed to by pointer, and it decrements the pointer. This
way, it is ready for the next push or pop.
I guess that just about covers it. Stack is very
simple and is very basic. There are tons of useful algorithms which take advantage of this
FILO structure. Now, lets look at alternative implementations...
Given the above, a lot of the C++ people would look
at me strangely, and say: "All this trouble for a stack that can only store
integers?" Well, they're probably right for the example above. It is too much
trouble. The trick I'll illustrate next is what makes Java my favorite Object Oriented
language.
In C, we have the void* type, to make
it possible to store "generic" data. In C++, we also have the void*
type, but there, we have very useful templates. Templates is a C++ way to make generic
objects, (objects that can be used with any type). This makes quite a lot of sense for a
data storage class; why should we care what we're storing?
The way Java implements these kinds of generic
classes is by the use of parent classes. In Java, every object is a descendent of the Object
class. So, we can just use the Object class in all of our structures, and
later cast it to an appropriate type. Next, we'll write an example that uses this
technique inside a generic stack.
public class pArrayStackObject{
protected Object head[];
protected int pointer;
public pArrayStackObject(int capacity){
head = new Object[capacity];
pointer = -1;
}
public boolean isEmpty(){
return pointer == -1;
}
public void push(Object i){
if(pointer+1 < head.length)
head[++pointer] = i;
}
public Object pop(){
if(isEmpty())
return null;
return head[pointer--];
}
}
The above is very similar to the int
only version, the only things that changed are the int to Object.
This stack, allows the push() and pop() of any Object.
Lets convert our old test driver to accommodate this new stack. The new test module will
be inserting java.lang.Integer objects (not int; not primitive
type).
import java.io.*;
import pArrayStackObject;
class pArrayStackObjectTest{
public static void main(String[] args){
pArrayStackObject s = new pArrayStackObject(10);
Integer j = null;
int i;
System.out.println("starting...");
for(i=0;i<10;i++){
j = new Integer((int)(Math.random() * 100));
s.push(j);
System.out.println("push: " + j);
}
while(!s.isEmpty()){
System.out.println("pop: " + ((Integer)s.pop()));
}
System.out.println("Done ;-)");
}
}
And for the sake of being complete, I'll include the
output. Notice that here, we're not inserting elements of int type, we're
inserting elements of java.lang.Integer type. This means, that we can insert
any Object.
starting...
push: 45
push: 7
push: 33
push: 95
push: 28
push: 98
push: 87
push: 99
push: 66
push: 40
pop: 40
pop: 66
pop: 99
pop: 87
pop: 98
pop: 28
pop: 95
pop: 33
pop: 7
pop: 45
Done ;-)
I guess that covers stacks. The main idea you should
learn from this section is that a stack is a FILO data structure. After this section, non
of the data structures will be working with primitive types, and everything will be done
solely with objects. (now that you know how it's done...)
And now, onto the array relative of Stack, the
Queue.
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
| 
Add to Favorites
Make Home Page
