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

1 package weiss.nonstandard;
2
3 // ArrayStack class
4 //
5 // CONSTRUCTION: with no initializer
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // void push( x ) --> Insert x
9 // void pop( ) --> Remove most recently inserted item
10 // AnyType top( ) --> Return most recently inserted item
11 // AnyType topAndPop( ) --> Return and remove most recent item
12 // boolean isEmpty( ) --> Return true if empty; else false
13 // void makeEmpty( ) --> Remove all items
14 // ******************ERRORS********************************
15 // top, pop, or topAndPop on empty stack
16
17 public class ArrayStack<AnyType> implements Stack<AnyType>
18 {
19 public ArrayStack( )
20 { /* Figure 16.3 */ }
21
22 public boolean isEmpty( )
23 { /* Figure 16.4 */ }
24 public void makeEmpty( )
25 { /* Figure 16.4 */ }
26 public AnyType top( )
27 { /* Figure 16.6 */ }
28 public void pop( )
29 { /* Figure 16.6 */ }
30 public AnyType topAndPop( )
31 { /* Figure 16.7 */ }
32 public void push( AnyType x )
33 { /* Figure 16.5 */ }
34
35 private void doubleArray( )
36 { /* Implementation in online code */ }
37
38 private AnyType [ ] theArray;
39 private int topOfStack;
40
41 private static final int DEFAULT_CAPACITY = 10;
42 }

figure 16.2
Skeleton for the
array-based stack
class

array doubling that involves N elements must be preceded by at least N /2
push es that do not involve an array doubling. Consequently, we can charge
the O ( N ) cost of the doubling over these N / 2 easy push es, thereby effectively
raising the cost of each push by only a small constant. This technique is
known as amortization .