7.19. Key Terms

[Page 245 ( continued )]

7.17. (Optional) Case Study: The StackOfIntegers Class

This section gives another example to demonstrate the creation and use of classes. Let us create a class for stacks.

A stack is a data structure that holds objects in a last-in first-out fashion. It has many applications. For example, the compiler uses a stack to process method invocations. When a method is invoked, its parameters and local variables are pushed into a stack. When a method calls another method, the new method's parameters and local variables are pushed into the stack. When a method finishes its work and returns to its caller, its associated space is released from the stack.

For simplicity, assume the stack holds the int values and name the stack class StackOfIntegers . The UML diagram for the class is shown in Figure 7.26.

Figure 7.26. The StackOfIntegers class encapsulates the stack storage and provides the operations for manipulating the stack.

---

[Page 246]

Suppose that the class is available. Let us write a test program in Listing 7.12 that uses the class to create a stack (line 3), stores ten integers , 1 , 2 , and 9 (line 6), and displays them in reverse order (line 9).

Listing 7.12. TestStackOfIntegers.java

 1   public class   TestStackOfIntegers { 2   public static void   main(String[] args) { 3  StackOfIntegers stack =   new   StackOfIntegers();  4 5   for   (   int   i =     ; i <   10   ; i++) 6  stack.push(i);  7 8   while   (!stack.empty()) 9 System.out.print(  stack.pop()  +   " "   ); 10 } 11 } 

How do you implement the StackOfIntegers class? The elements in the stack are stored in an array named elements . When you create a stack, the array is also created. The no-arg constructor creates an array with the default capacity of 16. The variable size counts the number of elements in the stack, and size “ 1 is the index of the element at the top of the stack, as shown in Figure 7.27. For an empty stack, size is .

Figure 7.27. The StackOfIntegers class encapsulates the stack storage and provides the operations for manipulating the stack.

The StackOfIntegers class is implemented in Listing 7.13. The methods empty() , peek() , pop() , and getSize() are easy to implement. To implement push(int value) , assign value to elements[size] if size < capacity (line 24). If the stack is full (i.e., size >= capacity ), create a new array of twice the current capacity (line 19), copy the contents of the current array to the new array (line 19), and assign the reference of the new array to the current array in the stack (line 20). Now you can add the new value to the array (line 24).

Listing 7.13. StackOfIntegers.java

(This item is displayed on pages 246 - 247 in the print version)

 1   public      class  StackOfIntegers   { 2   private int   [] elements; 3   private int   size; 4   public static final int   DEFAULT_CAPACITY = 16; 5 6  /** Construct a stack with the default capacity 16 */  7    public  StackOfIntegers()   { 8   this   (DEFAULT_CAPACITY); 9 } 

---

[Page 247]

 10 11  /** Construct a stack with the specified maximum capacity */  12    public   StackOfIntegers(   int   capacity)  { 13 elements =   new int   [capacity]; 14 } 15 16  /** Push a new integer into the top of the stack */  17   public int   push(   int   value) { 18   if   (size >= elements.length) { 19   int   [] temp =   new int   [elements.length *   2   ]; 20 System.arraycopy(elements,     , temp,     , elements.length); 21 elements = temp; 22 } 23 24   return   elements[size++] = value; 25 } 26 27  /** Return and remove the top element from the stack */  28   public int   pop() { 29   return   elements[ ” ”size]; 30 } 31 32  /** Return the top element from the stack */  33   public int   peek() { 34   return   elements[size -   1   ]; 35 } 36 37  /** Test whether the stack is empty */  38   public boolean   empty() { 39   return   size ==     ; 40 } 41 42  /** Return the number of elements in the stack */  43   public int   getSize() { 44   return   size; 45 } 46 } 

Note

Stacks are frequently used in programming. Java provides the Stack class in the java.util package, which will be introduced in Chapter 22, "Java Collections Framework."