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