Background
Stacks are an abstract data type designed to simplify data management. They are designed to hold a collection of elements all of the same type (such as int, for example). Their interface is very simple: if the stack is not full, then you can push a new element onto the stack. If the stack is not empty, then you can pop the newest element off the stack.
Elements on the stack are accessed in a LIFO (last in, first out) order. In other words, at any given moment, the item most recently put on the stack is the one that will pop off first. You can think of this as analagous to a stack of cafeteria trays, where the top tray is always accessible. If you put a new tray on top (push), the rest sink down so that the new tray is the only one available. If you take a tray off the top (pop), the rest rise up so that there is a new tray in its place.
A Simple Example
Stacks can be implemented using arrays or as a null-terminated, singly linked list. The Java Collections class Stack is based upon Vector, which uses a resizable array. The program TestStack shows some simple uses of the Stack class.
Run TestStack and observe what it does. Make small alterations in the program until you understand how it works. For example, see if you can push the number 4 onto the stack before the 1, and pop it off again after the 1 is popped.
Using a Stack
Of course, the interesting uses of a stack don't involve pushing constants on and popping them off again. Take a look at StackOdds.java, which asks the user to enter a number, then finds a sequence of odd numbers that add up to it. The algorithm is simple: First, it pushes the user's number onto the stack. Then, until the stack is empty, it pops a number off the stack and examines it. If the number is odd, it outputs it. Otherwise, it splits it in two and pushes the two halves onto the stack. For teaching purposes, the contents of the stack are printed after every step. Thus, depending on the initial number, the stack may store an arbitrarily large number of values. Compile the program, and try a few out on a few sample numbers: 10, 7, 16, 26, 28, 256.
Exercise One
Your task is to write a program similar to StackOdds.java, but a bit more useful. Your program will ask the user for a number, and the find its prime factorization. (Recall that the prime factorization of n is the unique collection of prime numbers that have n as their product. For example, the prime factorization of 1400 is 2*2*2*5*5*7.) It will do this with the help of the function getFactor(), provided below. Here's the algorithm (note the similarities with the above): Put the user's number on the stack. Now, until the stack is empty, pop a number off the stack and examine it. If the number is prime (i.e., getFactor() returns 1), then output it. Otherwise, divide the number into two factors and push them both on the stack. By the time the stack is empty, the prime factorization has been output.
When you have written the program, try it out on a few numbers (both prime and composite) and see how it works. Now, here's the code for getFactor():
/**
* getFactor() returns some factor of the argument a.
* If the number is prime, it will return 1.
*
* @param a: number to get a factor for.
* @return the largest integral factor of a
*/
public static int getFactor(int a) {
int i = (int)Math.sqrt(a);
while (a%i != 0) {
i--;
}
return i;
} // end of getFactor()