Generic Classes

The concept of a data structure, such as a stack, can be understood independently of the element type it manipulates. Generic classes provide a means for describing the concept of a stack (or any other class) in a type-independent manner. We can then instantiate type-specific objects of the generic class. This capability provides a wonderful opportunity for software reusability.

Once you have a generic class, you can use a simple, concise notation to indicate the actual type(s) that should be used in place of the class's type parameter(s). At compilation time, the Java compiler ensures the type safety of your code and uses the erasure techniques described in Section 18.3 and Section 18.4 to enable your client code to interact with the generic class.

One generic Stack class, for example, could be the basis for creating many Stack classes (e.g., "Stack of Double," "Stack of Integer," "Stack of Character," "Stack of Employee," etc.). These classes are known as parameterized classes or parameterized types because they accept one or more parameters. Recall that type parameters represent only reference types, which means the Stack generic class cannot be instantiated with primitive types. However, we can instantiate a Stack that stores objects of Java's type-wrapper classes and allow Java to use autoboxing to convert the primitive values into objects. Autoboxing occurs when a value of a primitive type (e.g., int) is pushed onto a Stack that contains wrapper-class objects (e.g., Integer). Auto-unboxing occurs when an object of the wrapper class is popped off the Stack and assigned it to a primitive type variable.

Figure 18.7 presents a generic Stack class declaration. A generic class declaration looks like a non-generic class declaration, except that the class name is followed by a type parameter section (line 4). In this case, type parameter E represents the element type the Stack will manipulate. As with generic methods, the type parameter section of a generic class can have one or more type parameters separated by commas. (You will create a generic class with two type parameters in Exercise 18.8.) Type parameter E is used throughout the Stack class declaration to represent the element type. [ Note: This example implements a Stack as an array.]

Figure 18.7. Generic class Stack declaration.

(This item is displayed on page 881 in the print version)

 1 // Fig. 18.7: Stack.java
 2 // Generic class Stack.
 3
 4 public class Stack< E >
 5 {
 6 private final int size; // number of elements in the stack
 7 private int top; // location of the top element
 8 private E[] elements; // array that stores stack elements
 9
10 // no-argument constructor creates a stack of the default size
11 public Stack()
12 {
13 this( 10 ); // default stack size
14 } // end no-argument Stack constructor
15
16 // constructor creates a stack of the specified number of elements
17 public Stack( int s )
18 {
19 size = s > 0 ? s : 10; // set size of Stack
20 top = -1; // Stack initially empty
21
22 elements = ( E[] ) new Object[ size ]; // create array
23 } // end Stack constructor
24
25 // push element onto stack; if successful, return true;
26 // otherwise, throw FullStackException
27 public void push( E pushValue )
28 {
29 if ( top == size - 1 ) // if stack is full
30 throw new FullStackException( String.format(
31 "Stack is full, cannot push %s", pushValue ) );
32
33 elements[ ++top ] = pushValue; // place pushValue on Stack
34 } // end method push
35
36 // return the top element if not empty; else throw EmptyStackException
37 public E pop()
38 {
39 if ( top == -1 ) // if stack is empty
40 throw new EmptyStackException( "Stack is empty, cannot pop" );
41
42 return elements[ top-- ]; // remove and return top element of Stack
43 } // end method pop
44 } // end class Stack< E >

Class Stack declares variable elements as an array of type E (line 8). This array will store the Stack's elements. We would like to create an array of type E to store the elements. However, the generics mechanism does not allow type parameters in array-creation expressions because the type parameter (in this case, E) is not available at runtime. To create an array with the appropriate type, line 22 in the one-argument constructor creates the array as an array of type Object and casts the reference returned by new to type E[]. Any object could be stored in an Object array, but the compiler's type-checking mechanism ensures that only objects of the array variable's declared type can be assigned to the array via any array-access expression that uses variable elements. Yet when this class is compiled using the -Xlint:unchecked option, e.g.,

 javac -Xlint:unchecked Stack.java

the compiler issues the following warning message about line 22:

 Stack.java:22: warning: [unchecked] unchecked cast
 found : java.lang.Object[]
 required: E[]
 elements = ( E[] ) new Object[ size ]; // create array

The reason for this message is that the compiler cannot ensure with 100% certainty that an array of type Object will never contain objects of types other than E. Assume that E represents type Integer, so that array elements should store Integer objects. It is possible to assign variable elements to a variable of type Object[], as in

 Object[] objectArray = elements;

Then any object can be placed into the array with an assignment statement like

 objectArray[ 0 ] = "hello";

which places a String in an array that should contain only Integers, which would lead to runtime problems when the Stack is manipulated. As long as you do not perform statements like those shown here, your Stack will contain objects of only the correct element type.

Method push (lines 2734) first determines whether an attempt is being made to push an element onto a full Stack. If so, lines 3031 throw a FullStackException. Class FullStackException is declared in Fig. 18.8. If the Stack is not full, line 33 increments the top counter and places the argument in that location of array elements.

Figure 18.8. FullStackException class declaration.

 1 // Fig. 18.8: FullStackException.java
 2 // Indicates a stack is full.
 3 public class FullStackException extends RuntimeException
 4 {
 5 // no-argument constructor
 6 public FullStackException()
 7 {
 8 this( "Stack is full" );
 9 } // end no-argument FullStackException constructor
10
11 // one-argument constructor
12 public FullStackException( String exception )
13 {
14 super( exception );
15 } // end one-argument FullStackException constructor
16 } // end class FullStackException

Method pop (lines 3743) first determines whether an attempt is being made to pop an element from an empty Stack. If so, line 40 throws an EmptyStackException. Class EmptyStackException is declared in Fig. 18.9. Otherwise, line 42 returns the top element of the Stack, then postdecrements the top counter to indicate the position of the next top element.

Figure 18.9. EmptyStackException class declaration.

 1 // Fig. 18.9: EmptyStackException.java
 2 // Indicates a stack is full.
 3 public class EmptyStackException extends RuntimeException
 4 {
 5 // no-argument constructor
 6 public EmptyStackException()
 7 {
 8 this( "Stack is empty" );
 9 } // end no-argument EmptyStackException constructor
10
11 // one-argument constructor
12 public EmptyStackException( String exception )
13 {
14 super( exception );
15 } // end one-argument EmptyStackException constructor
16 } // end class EmptyStackException

Classes FullStackException (Fig. 18.8) and EmptyStackException (Fig. 18.9) each provide the conventional no-argument constructor and one-argument constructor of exception classes (as discussed in Section 13.11). The no-argument constructor sets the default error message, and the one-argument constructor sets a custom exception message.

As with generic methods, when a generic class is compiled, the compiler performs erasure on the class's type parameters and replaces them with their upper bounds. For class Stack (Fig. 18.7), no upper bound is specified, so the default upper bound, Object, is used. The scope of a generic class's type parameter is the entire class. However, type parameters cannot be used in a class's static declarations.

Now, let's consider the test application (Fig. 18.10) that uses the Stack generic class. Lines 910 declare variables of type Stack< Double > (pronounced "Stack of Double") and Stack< Integer > (pronounced "Stack of Integer"). The types Double and Integer are known as the Stack's type arguments. They are used by the compiler to replace the type parameters so that the compiler can perform type checking and insert cast operations as necessary. We'll discuss the cast operations in more detail shortly. Method testStack (called from main) instantiates objects doubleStack of size 5 (line 15) and integerStack of size 10 (line 16), then calls methods testPushDouble (lines 2544), testPopDouble (lines 4767), testPushInteger (lines 7089) and testPopInteger (lines 92112) to demonstrate the two Stacks in this example.

Figure 18.10. Generic class Stack test program.

(This item is displayed on pages 883 - 886 in the print version)

 1 // Fig. 18.10: StackTest.java
 2 // Stack generic class test program.
 3 
 4 public class StackTest
 5 {
 6 private double[] doubleElements = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };
 7 private int[] integerElements = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
 8 
 9 private Stack< Double > doubleStack; // stack stores Double objects 
10 private Stack< Integer > integerStack; // stack stores Integer objects
11 
12 // test Stack objects
13 public void testStacks()
14 {
15 doubleStack = new Stack< Double >( 5 ); // Stack of Doubles 
16 integerStack = new Stack< Integer >( 10 ); // Stack of Integers
17 
18 testPushDouble(); // push double onto doubleStack
19 testPopDouble(); // pop from doubleStack
20 testPushInteger(); // push int onto intStack
21 testPopInteger(); // pop from intStack
22 } // end method testStacks
23 
24  // test push method with double stack
25  public void testPushDouble()
26 {
27 // push elements onto stack
28 try
29 {
30 System.out.println( "
Pushing elements onto doubleStack" );
31 
32 // push elements to Stack
33 for ( double element : doubleElements )
34 {
35 System.out.printf( "%.1 f ", element );
36 doubleStack.push( element ); // push onto doubleStack
37 } // end for
38 } // end try
39 catch ( FullStackException fullStackException )
40 {
41 System.err.println();
42 fullStackException.printStackTrace();
43 } // end catch FullStackException
44 } // end method testPushDouble
45 
46 // test pop method with double stack
47 public void testPopDouble()
48 {
49 // pop elements from stack
50 try
51 {
52 System.out.println( "
Popping elements from doubleStack" );
53 double popValue; // store element removed from stack
54 
55 // remove all elements from Stack
56 while ( true )
57 {
58 popValue = doubleStack.pop(); // pop from doubleStack
59 System.out.printf( "%.1 f ", popValue );
60 } // end while
61 } // end try
62 catch( EmptyStackException emptyStackException )
63 {
64 System.err.println();
65 emptyStackException.printStackTrace();
66 } // end catch EmptyStackException
67 } // end method testPopDouble
68 
69 // test push method with integer stack
70 public void testPushInteger()
71 {
72 // push elements to stack
73 try
74 {
75 System.out.println( "
Pushing elements onto intStack" );
76 
77 // push elements to Stack
78 for ( int element : integerElements )
79 {
80 System.out.printf( "%d ", element );
81 integerStack.push( element ); // push onto integerStack
82 } // end for
83 } // end try
84 catch ( FullStackException fullStackException )
85 {
86 System.err.println();
87 fullStackException.printStackTrace();
88 } // end catch FullStackException
89 } // end method testPushInteger
90 
91 // test pop method with integer stack
92 public void testPopInteger()
93 {
94 // pop elements from stack
95 try
96 {
97 System.out.println( "
Popping elements from intStack" );
98 int popValue; // store element removed from stack
99 
100 // remove all elements from Stack
101 while ( true )
102 {
103 popValue = integerStack.pop(); // pop from intStack
104 System.out.printf( "%d ", popValue );
105 } // end while
106 } // end try
107 catch( EmptyStackException emptyStackException )
108 {
109 System.err.println();
110 emptyStackException.printStackTrace();
111 } // end catch EmptyStackException
112 } // end method testPopInteger
113 
114 public static void main( String args[] )
115 {
116 StackTest application = new StackTest();
117 application.testStacks();
118 } // end main
119 } // end class StackTest

 

Pushing elements onto doubleStack
1.1 2.2 3.3 4.4 5.5 6.6
FullStackException: Stack is full, cannot push 6.6
 at Stack.push(Stack.java:30)
 at StackTest.testPushDouble(StackTest.java:36)
 at StackTest.testStacks(StackTest.java:18)
 at StackTest.main(StackTest.java:117)

Popping elements from doubleStack
5.5 4.4 3.3 2.2 1.1
EmptyStackException: Stack is empty, cannot pop
 at Stack.pop(Stack.java:40)
 at StackTest.testPopDouble(StackTest.java:58)
 at StackTest.testStacks(StackTest.java:19)
 at StackTest.main(StackTest.java:117)

Pushing elements onto integerStack
1 2 3 4 5 6 7 8 9 10 11
FullStackException: Stack is full, cannot push 11
 at Stack.push(Stack.java:30)
 at StackTest.testPushInteger(StackTest.java:81)
 at StackTest.testStacks(StackTest.java:20)
 at StackTest.main(StackTest.java:117)

Popping elements from integerStack
10 9 8 7 6 5 4 3 2 1
EmptyStackException: Stack is empty, cannot pop
 at Stack.pop(Stack.java:40)
 at StackTest.testPopInteger(StackTest.java:103)
 at StackTest.testStacks(StackTest.java:21)
 at StackTest.main(StackTest.java:117)

 

Method testPushDouble (lines 2544) invokes method push to place the double values 1.1, 2.2, 3.3, 4.4 and 5.5 stored in array doubleElements onto doubleStack. The for loop terminates when the test program attempts to push a sixth value onto doubleStack (which is full, because doubleStack can store only five elements). In this case, the method throws a FullStackException (Fig. 18.8) to indicate that the Stack is full. Lines 3943 catch this exception and print the stack trace information. The stack trace indicates the exception that occurred and shows that Stack method push generated the exception at lines 3031 of the file Stack.java (Fig. 18.7). The trace also shows that method push was called by StackTest method testPushDouble at line 36 of StackTest.java, that method testPushDouble was called from method testStacks at line 18 of StackTest.java and that method testStacks was called from method main at line 117 of StackTest.java. This information enables you to determine the methods that were on the method-call stack at the time that the exception occurred. Because the program catches the exception, the Java runtime environment considers the exception to have been handled and the program can continue executing. Note that autoboxing occurs in line 36 when the program tries to push a primitive double value onto the doubleStack, which stores only Double objects.

Method testPopDouble (lines 4767) invokes Stack method pop in an infinite while loop to remove all the values from the stack. Note in the output that the values indeed pop off in last-in-first-out order (this, of course, is the defining characteristic of stacks). The while loop (lines 5761) continues until the stack is empty (i.e., until an EmptyStackException occurs), which causes the program to proceed to the catch block (lines 6266) and handle the exception, so the program can continue executing. When the test program attempts to pop a sixth value, the doubleStack is empty, so the pop tHRows an EmptyStackException. Auto-unboxing occurs in line 58 when the program assigns the Double object popped from the stack to a double primitive variable. Recall from Section 18.4 that the compiler inserts cast operations to ensure that the proper types are returned from generic methods. After erasure, Stack method pop returns type Object. However, the client code in method testPopDouble expects to receive a double when method pop returns. So the compiler inserts a Double cast, as in

 popValue = ( Double ) doubleStack.pop();

to ensure that a reference of the appropriate type is returned, auto-unboxed and assigned to popValue.

Method testPushInteger (lines 7089) invokes Stack method push to place values onto integerStack until it is full. Method testPopInteger (lines 92112) invokes Stack method pop to remove values from integerStack until it is empty. Once again, note that the values pop off in last-in-first-out order. During the erasure process, the compiler recognizes that the client code in method testPopInteger expects to receive an int when method pop returns. So the compiler inserts an Integer cast, as in

 popValue = ( Integer ) integerStack.pop();

to ensure that a reference of the appropriate type is returned, auto-unboxed and assigned to popValue.

Creating Generic Methods to Test Class Stack< E >

Note that the code in methods testPushDouble and testPushInteger is almost identical for pushing values onto a Stack< Double > or a Stack< Integer >, respectively, and the code in methods testPopDouble and testPopInteger is almost identical for popping values from a Stack< Double > or a Stack< Integer >, respectively. This presents another opportunity to use generic methods. Figure 18.11 declares generic method testPush (lines 2646) to perform the same tasks as testPushDouble and testPushInteger in Fig. 18.10that is, push values onto a Stack< T >. Similarly, generic method testPop (lines 4969) performs the same tasks as testPopDouble and testPopInteger in Fig. 18.10that is, pop values off a Stack< T >. Note that the output of Fig. 18.11 precisely matches the output of Fig. 18.10.

Figure 18.11. Passing a generic type Stack to a generic method.

(This item is displayed on pages 887 - 889 in the print version)

 1 // Fig. 18.11: StackTest2.java
 2 // Stack generic class test program.
 3
 4 public class StackTest2
 5 {
 6 private Double[] doubleElements = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };
 7 private Integer[] integerElements =
 8 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
 9
10 private Stack< Double > doubleStack; // stack stores Double objects
11 private Stack< Integer > integerStack; // stack stores Integer objects
12
13 // test Stack objects
14 public void testStacks()
15 {
16 doubleStack = new Stack< Double >( 5 ); // Stack of Doubles
17 integerStack = new Stack< Integer >( 10 ); // Stack of Integers
18
19 testPush( "doubleStack", doubleStack, doubleElements ); 
20 testPop( "doubleStack", doubleStack ); 
21 testPush( "integerStack", integerStack, integerElements );
22 testPop( "integerStack", integerStack ); 
23 } // end method testStacks
24
25 // generic method testPush pushes elements onto a Stack
26 public < T > void testPush( String name, Stack< T > stack,
27  T[] elements ) 
28 {
29 // push elements onto stack
30 try
31 {
32 System.out.printf( "
Pushing elements onto %s
", name );
33
34 // push elements onto Stack
35 for ( T element : elements )
36 {
37 System.out.printf( "%s ", element );
38 stack.push( element ); // push element onto stack
39 }
40 } // end try
41 catch ( FullStackException fullStackException )
42 {
43 System.out.println();
44 fullStackException.printStackTrace();
45 } // end catch FullStackException
46 } // end method testPush
47
48 // generic method testPop pops elements from a Stack
49 public < T > void testPop( String name, Stack< T > stack )
50 {
51 // pop elements from stack
52 try
53 {
54 System.out.printf( "
Popping elements from %s
", name );
55 T popValue; // store element removed from stack
56
57 // remove elements from Stack
58 while ( true )
59 {
60 popValue = stack.pop(); // pop from stack
61 System.out.printf( "%s ", popValue );
62 } // end while
63 } // end try
64 catch( EmptyStackException emptyStackException )
65 {
66 System.out.println();
67 emptyStackException.printStackTrace();
68 } // end catch EmptyStackException
69 } // end method testPop
70
71 public static void main( String args[] )
72 {
73 StackTest2 application = new StackTest2();
74 application.testStacks();
75 } // end main
76 } // end class StackTest2

 

Pushing elements onto doubleStack
1.1 2.2 3.3 4.4 5.5 6.6
FullStackException: Stack is full, cannot push 6.6
 at Stack.push(Stack.java:30)
 at StackTest2.testPush(StackTest2.java:38)
 at StackTest2.testStacks(StackTest2.java:19)
 at StackTest2.main(StackTest2.java:74)

Popping elements from doubleStack
5.5 4.4 3.3 2.2 1.1
EmptyStackException: Stack is empty, cannot pop
 at Stack.pop(Stack.java:40)
 at StackTest2.testPop(StackTest2.java:60)
 at StackTest2.testStacks(StackTest2.java:20)
 at StackTest2.main(StackTest2.java:74)

Pushing elements onto integerStack
1 2 3 4 5 6 7 8 9 10 11
FullStackException: Stack is full, cannot push 11
 at Stack.push(Stack.java:30)
 at StackTest2.testPush(StackTest2.java:38)
 at StackTest2.testStacks(StackTest2.java:21)
 at StackTest2.main(StackTest2.java:74)

Popping elements from integerStack
10 9 8 7 6 5 4 3 2 1
EmptyStackException: Stack is empty, cannot pop
 at Stack.pop(Stack.java:40)
 at StackTest2.testPop(StackTest2.java:60)
 at StackTest2.testStacks(StackTest2.java:22)
 at StackTest2.main(StackTest2.java:74)

 

The testStacks method (lines 1423) creates the Stack< Double > (line 16) and Stack< Integer > (line 17) objects. Lines 1922 invoke generic methods testPush and testPop to test the Stack objects. Recall that type parameters can represent only reference types. Therefore, to be able to pass arrays doubleElements and integerElements to generic method testPush, the arrays declared in lines 68 must be declared with the wrapper types Double and Integer. When these arrays are initialized with primitive values, the compiler autoboxes each primitive value.

Generic method testPush (lines 2646) uses type parameter T (specified at line 26) to represent the data type stored in the Stack< T >. The generic method takes three argumentsa String that represents the name of the Stack< T > object for output purposes, a reference to an object of type Stack< T > and an array of type Tthe type of elements that will be pushed onto Stack< T >. Note that the compiler enforces consistency between the type of the Stack and the elements that will be pushed onto the Stack when push is invoked, which is the real value of the generic method call. Generic method testPop (lines 4969) takes two argumentsa String that represents the name of the Stack< T > object for output purposes and a reference to an object of type Stack< T >.