At the abstract level, a stack is an ordered group of elements.  The removal 
of existing elements and the 
addition of new elements can take place only at the top of the stack.  For 
instance, if your favorite blue shirt is 
underneath a faded, old, red one in a stack of shirts, you first must remove 
the red shirt (the top element) from 
the stack.  Only then can you remove the desired blue shirt, which is now the 
top element in the stack.  Then you 
may replace the red shirt on the top of the stack or throw it away.
The stack is considered an "ordered" group of items because elements occur in 
a sequence according to 
how long they've been in the stack.  The items that have been in the stack the
 longest are at the bottom; the most 
recent are at the top.  At any time, given any two elements in a stack, one is
 higher than the other.  (For instance, 
the red shirt was higher in the stack than the blue shirt.)
Because items are added and removed only from the top of the stack, the last 
element to be added is the 
first to be removed.  There is a handy mnemonic to help you remember this rule
 of stack behavior: A stack is a 
"last in, first out" (LIFO) structure.  The accessing operation of a stack is 
summarized as follows:  Both to 
retrieve elements and to assign new elements, access only the top of the stack.
Operations on Stacks
The logical picture of the structure is only half the definition of a class.  
The other half is a set of operations that 
allows the user to access and manipulate the elements stored in the structure.  
Given the abstract structure of a 
stack, what kinds of operations do we need in order to use a stack?
A stack is a dynamic structure; it changes as elements are added to and removed 
from it.  When we begin 
using a stack, it should be empty (contain no elements).  The operation that 
adds an element to the top of a stack 
is usually called Push, and the operation that takes the top element off the 
stack is referred to as Pop.  We also 
must be able to tell whether a stack contains any elements before we pop it, 
so we need a Boolean operation 
Empty.  As a logical data structure, a stack is never conceptually "full," but 
for a particular implementation you 
may need to test whether a stack is full before pushing.  We'll call this Boolean 
operation Full.  We also might 
want an operation that destroys a stack, getting rid of all the elements left in 
it and leaving the stack empty.  
We'll call this operation Clear.  Figure 6-2 shows how a stack, envisioned as a 
stack of building blocks, is 
modified by several Push and Pop operations.
Next we must formalize the stack operations we have described.  As with our set 
and string classes, we use 
a package specification to accurately describe our class.  We'll make this a generic 
package so that our stack 
abstraction can be easily reused in different applications.  We then can instantiate 
stack packages for stacks 
containing any type of objects.  Our generic stack specification is given in 
Specification 6-1.

Exceptions
In addition to the stack operations we discussed earlier, this package contains 
the declarations for two exceptions.  
If a stack is empty when we try to pop an element from it, the resulting error 
condition is called stack 
underflow.  The exception comments for procedure Pop indicate that the exception 
UNDERFLOW is raised if this 
condition is detected.  Stack overflow is the condition resulting from trying to 
push a new element onto a stack 
that is already full,  Procedure Push raises the exception OVERFLOW if this condition 
is detected.  
Why bother declaring these exceptions in the stack package?  Why not just display 
an error message?  For 
example, instead of raising UNDERFLOW when the Pop operation detects an erroneous 
condition Pop could 
display an error message on the console such as 
Error!  The stack is empty, you can't remove an item at this time.
One problem of this approach is that the error message we choose when we write 
the stack package body 
probably has little meaning in the context of the client program that uses a 
stack.  Imagine the confusion if the 
above message were displayed when someone running a word processing program 
clicks their mouse on the 
"undo" command.  A more meaningful error message in this situation would be "There 
are no more commands to 
undo."  
Part of the task of writing a reusable component is to allow errors that are 
detected by the component to be 
dealt with at the appropriate level of abstraction.  Ada's exceptions are the 
perfect tool for this job.  When the 
stack package detects a problem, it raises an exception that is propagated back 
to the client program to deal with.  
Exception propagation also ensures that the error condition is not ignored.  
If the client has no handler for the 
exception, it is propagated back to the operating system which ends execution 
of the program and displays a 
(usually cryptic) error message.  
Exceptions and Postconditions 
Postconditions are assertions that state what results are to be expected at the 
exit of an operation or procedure.  
Our style of commenting postconditions for package operations is to divide the 
exit assertions into two groups.  
The assertions in the group labeled Postconditions: are true if the operation 
terminates normally; that is, when 
no exception is raised.  The comment section labeled Exceptions: contains 
assertions that are true if the package 
operation terminates abnormally by raising an exception.  Notice how our 
exception comments specify exactly 
what the state of the stack is after the package raises the exception.  Other 
people prefer to have just a single 
postcondition comment section that includes the exit assertions found in both 
of our comment sections.  
The Application Level
Now let's look at an example of how the operations in the stack package might 
be used in a program.  Since you 
were in elementary school you have written arithmetic expressions using a format 
known as infix notation.  This 
same notation is used for writing arithmetic expressions in Ada.  The operator 
in an infix expression is written in 
between its operands.  When an expression contains multiple operations such as
we need to use a set of rules to determine which operation to carry out first.  
You learned in your mathematics 
classes that multiplication is done before addition.  You learned Ada's operator 
precedence rules in your first 
programming class.  In both situations, we use parentheses to override the normal 
ordering rules.  It is easy to 
make a mistake writing or interpreting an infix expression containing multiple 
nested sets of parentheses.  


That is the end of the story!