Recipe 7.14 Stack

Problem

You need to process data in "last-in, first-out" ( LIFO) or "most recently added" order.

Solution

Write your own code for creating a stack; it's easy. Or, use a java.util.Stack.

Discussion

You need to put things into a holding area quickly and retrieve them in last-in, first-out order. This is a common data structuring operation and is often used to reverse the order of objects. The basic operations of any stack are push( ) (add to stack), pop( ) (remove from stack), and peek( ) (examine top element without removing). ToyStack is a simple class for stacking only ints:

/** Toy Stack. */ public class ToyStack {     /** The maximum stack depth */     protected int MAX_DEPTH = 10;     /** The current stack depth */     protected int depth = 0;     /* The actual stack */     protected int[] stack = new int[MAX_DEPTH];     /* Implement a toy stack version of push */     protected void push(int n) {         stack[depth++] = n;     }     /* Implement a toy stack version of pop */     protected int pop( ) {         return stack[--depth];     }     /* Implement a toy stack version of peek */     protected int peek( ) {         return stack[depth - 1];     } }

If you are not familiar with the basic idea of a stack, you should work through the code here; if you are familiar with it, you can skip ahead. While looking at it, of course, think about what happens if pop( ) or peek( ) is called when push( ) has never been called, or if push( ) is called to stack more data than will fit.

The java.util.Stack operation behaves in a similar fashion. However, instead of being built just for one type of primitive, such as Java int, the methods of java.util.Stack are defined in terms of java.lang.Object so that any kind of object can be put in and taken out. A cast is needed when popping objects, if you wish to call any methods defined in a class below Object. (In JDK 1.5, you can avoid the cast; see Recipe 8.1.)

For an example of a java.util.Stack in operation, Recipe 5.19 provides a simple stack-based numeric calculator.