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 ...