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.
theparticle.com
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.
theparticle.com
0 Komentar untuk "Array Stack 2"