Java Cookbook

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). A simple stack for stacking only ints is in class ToyStack :

/** 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];
    }
}

If you are not familiar with the basic idea of a stack, you should work through the code here; if you are, skip ahead. While looking at it, of course, think about what happens if pop( ) 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 ...