CMIS 242 

This week learn about stacks.
Java has a builtin Stack class, which we will learn how to use.  
StackTest.java on the class web site is our basic
demo program of how to use this Stack class.

A stack is a list that can be accessed only at one end (called the "top").
A computer stack is like a real-life stack of plates or trays at the
cafeteria except that it's impossible to "cheat" and reach in and
access anything except the item at the top of the stack.    It's
restricted in how its items can be accessed.  Adding an item to the
stack is called "pushing" (pushing that tray onto the top of the
stack), removing an item is called "popping" (pops off the
spring-loaded stack).  With a stack abstract data type the client can
not access the items in any other way.  The item that is popped is the
one that was most recently pushed; this is the "last in, first out"
(LIFO) characteristic of a stack, sometimes known as a LIFO list.
There's no "search" function of a stack (they are not intended for
such a use).  Length is usually irrelevant in most stack applications,
so there's no "length" function.  Nor is there an iterator.  There is
a function to check to see if the stack is empty; this function is
important for preventing stack "underflow" (attempt to pop an empty
stack) and to check if some phase of processing has completed.

Stacks are simpler kinds of lists than an ArrayList.
So why use something that's simpler?  There are
situations that call for a stack-like access of the data.
Some of these situations are when you need to process data in the
reverse order of its creation or input.  The StackTest.java program
on the class web site illustrates this using the built-in Stack class.
Notice it has a loop pushing ints onto a stack, then a loop popping
them off the stack, processing each, thus allowing processing in the
reverse order of the data's generation.  If you're thinking that an
array or ArrayList could be used for the same purpose, you're correct;
the array would be being used as a stack.  But it's better (safer and
more efficient, programmer-timewise) to use an abstract data type
specifically tailored for such data access.

But don't be left with the impression that stacks are only used in
this "loop pushing, then loop popping until empty" style; they can
also be used with a more random mix of pushes and pops.  The
StackTest.java demos this with random pushes and pops. 

The postfix evaluation program Postfix.java on the class web site
illustrates a stack that grows and shrinks unpredictably.
(Parentheses are not needed to indicate order of operations in a
postfix expression.  Postfix expressions are unambiguous.
Compilers typically convert infix expressions to postfix form because
it's easier to evaluate postfix expressions at runtime.)