test1.java is designed to test either version of stringQueue. As you recall, stringQueue is an abstract class with no implementation of its own. We extended it to have a fixed (array) and a dynamic (linked list) implementation. It is designed so that user can specify a datafile, the version to test, and if necessary, the number of cells for the array in the "fixed" version. This information is taken from the command line. Here are two examples of running this program:
java test1 test1.dat fixed 10 will test the fixed version using test1.dat as the data file. Also, the size 10 is chosen here for the array that keeps the queue elements.
java test1 test1.dat dynamic will test the dynamic version using test1.dat as the data file. Notice that no size is specified, as it is not relevant in the dynamic case.
Processing of command line parameters is mostly useful in utility programs, such as, mv and ls. In test1.java, it helps to test the different versions stringQueue quickly, without engaging in long dialog with the program to set things up.
In test1.java, the main method has an array of strings as a parameter (arg). This array is filled with the space separated strings on the command line that appear after the program name. arg[0] in the examples shown above is test1.dat. When looking at the code for this program, you will notice that the file opened for input gets its name from arg[0].
One of the things that I like you to notice is the use of the equals method when trying to figure out which version is being tested. You ask yourself, why couldn't we simply say if (arg[1] == dynamic). The reason is simple, "==" testes equality of the references and not what the objects contain. In other words, we can only find out if arg[1] and dynamic are both referencing the same memory cell.
Note that the declaration of q occurs before we know which kind the user is testing. Recall that you can't make objects of stringQueue, it is an abstract class. Once the program figures out which version is to be tested, either q = new dynamicStringQueue();, or q = new fixedStringQueue(size); are used to creat the right version of the queue.
Consider the code segment:
while(!q.empty()) {
text = q.dequeue();
System.out.println(text+" was removed from the queue");
}
What if we want to take this out of the main method and put in its own
method, say, named out. It would be invoked from main with a call
like out(q);. Here is the catch, what kind parameter, do you
think, out needs to accept? It needs to be stringQueue,
as you don't know which implementation is used, so how can you use
either of its subclasses. But, this not a problem, as this is
one of the fundamental advantages for Object Orientation which we call
Polymorphism. Here is a look at the out method:
static void out(stringQueue q) {
while(!q.empty()) {
String text = q.dequeue();
System.out.println(text+" was removed from the queue");
}
}
genStack.java is designed to allow for any object to be stored in the stack. As long as, the element being stored is an object of a class that is a descendant of the class Object, we can put the element on and later take it off the stack. For example, in test1.java we use a generic stack to hold strings.
Notice that an object of the Vector Class is used to hold our elements.
the one tricky issue that is easy to over look is how do you know what kind of an object you are poping off the stack? As I said earlier, the stack itself doesn't what you put on or take off. The test program used for testing this know puts strings on and thus know that it is taking strings off. But, the following syntax is necessary to successfully pop the strings off the stack: text = (String)s.pop();. The use of (String) identifies the object coming back from the stack as a string. Be aware, this technique is not for changing an apple into an orange, it is more like saying, I got a fruit and I know its an orange.
Recursion is grounded in mathematical induction and is one of our most significant problem solving tools in computer science. We will discuss mathematical induction first through an example and we will then move into a discussion about recursion.
Although, your first experience here will be in using recursion for solving problems that you have previously solved iteratively, you must not lose sight of the fact that there are many problems that have a natural recursive solution. We will discuss the classic Tower of Honoi problem as an example with a naturally recursive solution. Tower of Honoi is not easy to solve without recursion.
It seems to make sense to talk about induction proofs in mathematics before discussing recursion. Induction proofs are often used in proving theorems in mathematics especially those in number theory.
The basic idea here is that you have a base case for the theorem that is
easyly provable and your main task is to prove that assuming that the theorem
holds for the case n-1, it also holds for case n (usually, we assume the nth
case and prove the (n+1)th case, but it is the same idea). Think about what
that says--if I can prove that the theorem holds when n is 0, for instance, a
nd can also prove that if it holds for case n-1, it also holds for case n,
doesn't that mean that it holds when n is 1, then when n is 2, and then when
n is 3, and so on ...? neat!
Here is an example:
I hope you have all heard of the theorem that says ...
the sum of all positive integers up to N is equal to N(N+1)/2 Let us use induction proof to prove this theorem. Base Case: Base case here is when N is 1. Note that the sum of all positive numbers from 1 to 1 is 1 and that 1(1+1)/2 is also 1. Done. Inductive Step: Lets assume that 1 + 2 + ... + (N-1) == (N-1)N/2 Now, we will show that 1 + 2 + ... + (N-1) + N == N(N+1)/2 To prove this, we add N to each side of == in the assumed case: 1 + 2 + ... + (N-1) + N == (N-1)N/2 + N ==> 1 + 2 + ... + (N-1) + N == ((N-1)N + 2N)/2 ==> 1 + 2 + ... + (N-1) + N == (N2 - N + 2N)/2 ==> 1 + 2 + ... + (N-1) + N == (N2 + N)/2 ==> 1 + 2 + ... + (N-1) + N == N(N+1)/2 Done!