Stacks and queues - Data Structures and Problem Solving Using Java - page 599

1 /**
2 * Get the most recently inserted item in the stack.
3 * Does not alter the stack.
4 * @return the most recently inserted item in the stack.
5 * @throws UnderflowException if the stack is empty.
6 */
7 public AnyType top( )
8 {
9 if( isEmpty( ) )
10 throw new UnderflowException( "ArrayStack top" );
11 return theArray[ topOfStack ];
12 }
13
14 /**
15 * Remove the most recently inserted item from the stack.
16 * @throws UnderflowException if the stack is empty.
17 */
18 public void pop( )
19 {
20 if( isEmpty( ) )
21 throw new UnderflowException( "ArrayStack pop" );
22 topOfStack--;
23 }

figure 16.6
The top and pop
methods for the
ArrayStack class

1 /**
2 * Return and remove the most recently inserted item
3 * from the stack.
4 * @return the most recently inserted item in the stack.
5 * @throws Underflow if the stack is empty.
6 */
7 public AnyType topAndPop( )
8 {
9 if( isEmpty( ) )
10 throw new UnderflowException( "ArrayStack topAndPop" );
11 return theArray[ topOfStack-- ];
12 }

figure 16.7
The topAndPop method
for the ArrayStack
class

it is when the tax is paid that varies. The same is true for the time spent in the
push operations. We can charge for the array doubling at the time it occurs, or
we can bill each push operation equally. An amortized bound requires that we
bill each operation in a sequence for its fair share of the total cost. In our
example, the cost of array doubling therefore is not excessive.