4.5 Generic Implementations
How can we develop one stack implementation that allows us to build both a stack of integers and a stack of characters as required, for example, by the clients in Section 4.3? The most straightforward way to do so in Java is to use inheritance: we define an interface and implementation for stacks of items of type Object, then cast each item to the desired type when we pop it from the stack. Since all objects in Java are derived from type Object, the cast is always valid.
Program 4.9 is a generic stack implementation that uses an array representation. It is the same code as Program 4.7, except with the types of s, push's parameter, and pop's return value all changed to Object. We can push any Java object onto the stack, then cast it to the required type when we pop it. For example, if a and b are objects of type Item, the following code would exchange them:
Stack S = new Stack(2); s.push(a); s.push(b); a = ((Item) s.pop()); b = ((Item) s.pop());
This approach is widely used to develop generic implementations in Java, but it has two limitations, which we now consider.
First, to use stacks of items of type Object for primitive types such as int or char, we have to make use of wrapper classes such as Integer or Character. For example, rather than writing s.push(x) to push a variable x of type int onto the stack, we have to write
s.push(new Integer(x))
and rather than using s.pop() as an integer value in an expression, we would have to use
((Integer) s.pop()).intValue() .
This approach adds an extra level of indirection, as illustrated in Figure 4.6: a stack of objects is a stack of references. In an application where we are using huge numbers of items of a primitive type, this extra cost may be unacceptable.
Figure 4.6. Array representations
When we use an array to represent a stack of primitive types such as characters (top), we reserve space for one character per stack entry. For any other type of object, we have to reserve space for one reference per object, in addition to the objects themselves (bottom).
The second problem with using inheritance from Object to develop generic implementations is that doing so can expose us to subtle bugs in our programs that cannot be detected until runtime. For example, there is nothing to stop a programmer from putting different types of objects on the same stack, then encountering a runtime type-checking error, as in the following example:
Apple a = new Apple(); Orange b = new Orange(); s.push(a); s.push(b); a = ((Apple) s.pop()); // throws a ClassCastException b = ((Orange) s.pop());
This toy example illustrates a basic problem, which could arise even in a stack whose items are all of the same type. The code cannot be type-checked at compile time: there might be an incorrect cast that occurs in a complex piece of code that could escape detection until some particular runtime circumstance arises. Such an error is to be avoided at all costs because it could happen long after an implementation is delivered to a client, who would have no way to fix it.
In other words, when we use type casting with an implementation such as Program 4.9 to reuse code for different types of items, we are assuming that clients will cast objects popped from the stack to the proper type. This implicit assumption contradicts our requirement for ADTs that operations are to be accessed only through an explicit interface. One reason that programmers use precisely defined ADTs such as Program 4.4 is to protect future clients against errors that arise from such implicit assumptions.
One way to address this problem is to use the generic Stack class to implement the intStack interface, as shown in Program 4.10.We still have to have a class for every type of object, but their implementations are trivial and we do not have to duplicate the (potentially complicated) algorithm and data-structure implementations. It is actually quite common in Java programming to define a class whose sole purpose is to match the needs of a client with the capability of an existing class. Such a class is called an adapter class.
Another approach that we could use to enable compile-time type checking is to define an ADT for the items that we are going to put on stacks so that we can get stacks of different types of items by using different implementations of that ADT. We will use this approach in the more complicated algorithms and data structures that we consider in Parts III and IV because they make certain assumptions about the item type that we need to build into the ADT. This approach still leaves us with an extra level of indirection for primitive types and requires that we use adapter classes to have, for example, stacks of two different types of items in a single program.
Program 4.9 Generic pushdown stack
This code implements a pushdown stack ADT for the Object type. It does not implement the interface of Program 4.4 because push's parameter and pop's return value do not match the specification.
The code for pop is more complicated than in Program 4.7 because the reference to the popped item in the array has to be replaced by null otherwise, the Java garbage collection system has no way to know that this reference will never be used and will not reclaim the memory associated with the popped object.
class Stack { private Object[] s; private int N; Stack(int maxN) { s = new Object[maxN]; N = 0; } boolean isEmpty() { return (N == 0); } void push(Object item) { s[N++] = item; } Object pop() { Object t = s[--N]; s[N] = null; return t; } } In client programs, we use specified classes like intStack. This approach will accommodate either a direct implementation for primitive types or a a generic implementation with an adapter class while still using code that can be fully type-checked at compile time.
Exercises
4.25 Give a class that implements that same interface as Program 4.9 but uses a linked-list representation.
Program 4.10 Adapter class for stack of integers
This code does implement the interface of Program 4.4. With this technique, we can reuse the code of Program 4.9 for different types of data, while still being sure that clients and implementations agree on an explicit interface.
class intStack { private Stack S; intStack(int maxN) { S = new Stack(maxN); } boolean isEmpty() { return S.isEmpty(); } void push(int item) { S.push(new Integer(item)); } int pop() { return ((Integer) S.pop()).intValue(); } }4.26 Write a generic static method that exchanges two items in an array. Test your code in a driver program that creates one array of items of type Integer and another array of type Character and then uses your method to exchange objects in each array.
4.27 Implement an infix-expression evaluation program for integers based upon Programs 4.5 and 4.6, that uses the generic stack class in Program 4.9. Note: You have to cope with the fact that the stack has to contain items of different types (see Exercise 4.23).
| Top |
EAN: 2147483647
Pages: 158