At the abstract level, a  removed. There is a       elements before we pop  
stack is an ordered       handy mnemonic to help    it, so we need a Boolean
group of elements. The    you remember this rule    operation Empty. As a   
removal of existing       of stack behavior: A      logical data structure, 
elements and the          stack is a "last in,      a stack is never        
addition of new elements  first out" (LIFO)         conceptually "full," but
can take place only at    structure. The accessing  for a particular        
the top of the stack.     operation of a stack is   implementation you may  
For instance, if your     summarized as follows:    need to test whether a  
favorite blue shirt is    Both to retrieve          stack is full before    
underneath a faded, old,  elements and to assign    pushing. We'll call this
red one in a stack of     new elements, access      Boolean operation Full. 
shirts, you first must    only the top of the       We also might want an   
remove the red shirt      stack. Operations on      operation that destroys 
(the top element) from    Stacks The logical        a stack, getting rid of 
the stack. Only then can  picture of the structure  all the elements left in
you remove the desired    is only half the          it and leaving the stack
blue shirt, which is now  definition of a class.    empty. We'll call this  
the top element in the    The other half is a set   operation Clear. Figure 
stack. Then you may       of operations that        6-2 shows how a stack,  
replace the red shirt on  allows the user to        envisioned as a stack of
the top of the stack or   access and manipulate     building blocks, is     
throw it away. The stack  the elements stored in    modified by several Push
is considered an          the structure. Given the  and Pop operations. Next
"ordered" group of items  abstract structure of a   we must formalize the   
because elements occur    stack, what kinds of      stack operations we have
in a sequence according   operations do we need in  described. As with our  
to how long they've been  order to use a stack? A   set and string classes, 
in the stack. The items   stack is a dynamic        we use a package        
that have been in the     structure; it changes as  specification to        
stack the longest are at  elements are added to     accurately describe our 
the bottom; the most      and removed from it.      class. We'll make this a
recent are at the top.    When we begin using a     generic package so that 
At any time, given any    stack, it should be       our stack abstraction   
two elements in a stack,  empty (contain no         can be easily reused in 
one is higher than the    elements). The operation  different applications. 
other. (For instance,     that adds an element to   We then can instantiate 
the red shirt was higher  the top of a stack is     stack packages for      
in the stack than the     usually called Push, and  stacks containing any   
blue shirt.) Because      the operation that takes  type of objects. Our    
items are added and       the top element off the   generic stack           
removed only from the     stack is referred to as   specification is given  
top of the stack, the     Pop. We also must be      in Specification 6-1.   
last element to be added  able to tell whether a    Exceptions In addition  
is the first to be        stack contains any        to the stack operations 
we discussed earlier,     that uses a stack.        an operation or         
this package contains     Imagine the confusion if  procedure. Our style of 
the declarations for two  the above message were    commenting              
exceptions. If a stack    displayed when someone    postconditions for      
is empty when we try to   running a word            package operations is to
pop an element from it,   processing program        divide the exit         
the resulting error       clicks their mouse on     assertions into two     
condition is called       the "undo" command. A     groups. The assertions  
stack underflow. The      more meaningful error     in the group labeled    
exception comments for    message in this           Postconditions: are true
procedure Pop indicate    situation would be        if the operation        
that the exception        "There are no more        terminates normally;    
UNDERFLOW is raised if    commands to undo." Part   that is, when no        
this condition is         of the task of writing a  exception is raised. The
detected. Stack overflow  reusable component is to  comment section labeled 
is the condition          allow errors that are     Exceptions: contains    
resulting from trying to  detected by the           assertions that are true
push a new element onto   component to be dealt     if the package operation
a stack that is already   with at the appropriate   terminates abnormally by
full, Procedure Push      level of abstraction.     raising an exception.   
raises the exception      Ada's exceptions are the  Notice how our exception
OVERFLOW if this          perfect tool for this     comments specify exactly
condition is detected.    job. When the stack       what the state of the   
Why bother declaring      package detects a         stack is after the      
these exceptions in the   problem, it raises an     package raises the      
stack package? Why not    exception that is         exception. Other people 
just display an error     propagated back to the    prefer to have just a   
message? For example,     client program to deal    single postcondition    
instead of raising        with. Exception           comment section that    
UNDERFLOW when the Pop    propagation also ensures  includes the exit       
operation detects an      that the error condition  assertions found in both
erroneous condition Pop   is not ignored. If the    of our comment sections.
could display an error    client has no handler     The Application Level   
message on the console    for the exception, it is  Now let's look at an    
such as Error! The stack  propagated back to the    example of how the      
is empty, you can't       operating system which    operations in the stack 
remove an item at this    ends execution of the     package might be used in
time. One problem of      program and displays a    a program. Since you    
this approach is that     (usually cryptic) error   were in elementary      
the error message we      message. Exceptions and   school you have written 
choose when we write the  Postconditions            arithmetic expressions  
stack package body        Postconditions are        using a format known as 
probably has little       assertions that state     infix notation. This    
meaning in the context    what results are to be    same notation is used   
of the client program     expected at the exit of   for writing arithmetic  
expressions in Ada. The   first. You learned in     parentheses to override 
operator in an infix      your mathematics classes  the normal ordering     
expression is written in  that multiplication is    rules. It is easy to    
between its operands.     done before addition.     make a mistake writing  
When an expression        You learned Ada's         or interpreting an infix
contains multiple         operator precedence       expression containing   
operations such as we     rules in your first       multiple nested sets of 
need to use a set of      programming class. In     parentheses. That is the
rules to determine which  both situations, we use   end of the story!       
operation to carry out