The Stack Interface

A stack is a data structure holding several items. As seen in Figure 4-1, we can think of the items in a stack as being arranged vertically. When a new item is added, it is added to the top of the stack. This is called pushing an item onto the stack. We can pop the stack to extract the topmost item. We can also peek at the top item or check if the stack is empty.

Figure 4-1. A stack changes as various operations are performed on it. Peeking at the final (rightmost) stack would return B, but not alter the stack. A real stack would start out empty, but we included a few items here to make the example more interesting.

Since the most recently pushed item is always on top of the stack (and hence available for popping), a stack is said to follow a last-in, first-out or LIFO policy. One consequence is that if we push a sequence of ten items onto a stack and then pop the stack ten times, the items are returned in reverse order. The standard analogy for a stack is a spring-loaded stack of plates found in a cafeteria: we can push a new plate on top or we can pop off the top plate, but we can't (directly) get at the plates underneath.

We can formalize the stack abstract data type in the Stack interface (Figure 4-2). We will explain lines 9 and 15 later in this chapter. There is more than one way to implement this interface. We will see one way in Chapter 5 and a very different one in Chapter 6.

Figure 4-2. First draft of the Stack interface.

Before moving on to an example of using a Stack, we introduce a new feature of Java 1.5 that allows us to avoid some casting.

Generics

The Stack interface in Figure 4-2 describes a stack of Objects. We can push any kind of Object onto a Stack. For example, if s is a Stack:

s.push (new Die(3));

When we pop a Stack, on the other hand, we get back an Object. Even if we remember that the item on the Stack is an instance of some more specific class, we have to remind Java of this fact by casting:

((Die)(s.pop())).roll();

This is not only inconvenient, it is slightly unsafe. If we misremember what we put on the Stack, we might try to cast something that is not really a Die to be a Die. This would crash our program.

Java 1.5 introduces a new solution: generic classes and interfaces. A generic class or interface has one or more type parameters, indicating what sorts of things it holds. Every time we use a generic type, we have to specify a type for each type parameter. In the case of Stacks, there is only type parameter: the type of the elements stored on the Stack. To make a Stack of Die instances, we say:

Stack s = new Stack();

Now we can safely do:

s.push(new Die()); s.pop().roll();

Java won't let us push anything of the wrong type onto this Stack. Furthermore, the pop() method's return type is specified by the type parameter. In our example, the return type is Die.

The revised Stack interface is shown in Figure 4-3.

Figure 4-3. Generic version of the Stack interface. The type parameter is E, which stands for 'element'.

In UML diagrams, type parameters are shown in dashed boxes at the upper right of a class, interface, or instance (Figure 4-4).

Figure 4-4. UML class diagram of the generic Stack interface.

Example: Idiot's Delight

One advantage of specifying an abstract data type is that we can write programs which use the ADT before we've implemented it. We now use the Stack interface to implement some parts of the game of Idiot's Delight (Figure 4-5).

A game of Idiot's Delight involves a Deck, which in turn includes up to 52 Cards. (There are fewer than 52, once some have been dealt from the Deck.) The game also needs four Stacks, each of which contains 0 or more Cards. This is illustrated in Figure 4-6.

Figure 4-6. UML class diagram of the Idiot's Delight program.

The fields and main() method of the IdiotsDelight class are shown in Figure 4-7. Note that the field stacks contains an array of Stacks of Cards. Also, importing the Scanner class allows us to declare and initialize the constant INPUT more concisely.

The constructor, shown in Figure 4-8, is the most complicated constructor we've written yet. Line 3 invokes the constructor for the Deck class, which we'll write later. Line 4 invokes the shuffle() method from that class. Shuffling is something a Deck should know how to do, not part of this game in particular, so it is encapsulated inside the Deck class.

Figure 4-7. Fields and main() method for IdiotsDelight.

Figure 4-8. Constructor for the IdiotsDelight class.

Line 5 allocates the array stacks, but each element of that array still has the default value null. The for loop on lines 68 is needed to initialize the elements. Line 7 invokes the constructor for the ArrayStack class. This class, which we will write in Chapter 5, uses an array to implement the Stack interface.

In a stroke of bad luck, the ugliest feature of generics rears its head here: generics do not play well with arrays. We can declare an array field or variable involving type parameters, like the field stacks in Figure 4-7. For complicated reasons involving the Java compiler, however, we cannot actually allocate an array involving a type parameter. We would like line 5 of Figure 4-8 to read

stacks = new Stack[4];

but Java will not let us do this. If we leave the line as it is in Figure 4-8, we get the following cryptic message when we try to compile the program:

Note: IdiotsDelight.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.

Following these instructions, we invoke the command

javac -Xlint:unchecked IdiotsDelight.java

and get the following:

IdiotsDelight.java:20: warning: [unchecked] unchecked conversion found : Stack[] required: Stack[] stacks = new Stack[4]; // This causes a compiler warning ^ 1 warning

Significantly, this is a warning, not an error. The compiler is telling us, "I think this is a bad idea, but I'm not going to stop you from doing it." Surprisingly, this is the best we can do. By the end of Chapter 5, we'll have hidden this unpleasantness behind a layer of encapsulation.

Returning to the task at hand, line 9 of Figure 4-8 calls the deal() method from the IdiotsDelight class. This method, shown in Figure 4-9, deals one card onto each Stack.

Figure 4-9. The deal() method from the IdiotsDelight class.

Line 4 does a lot of work. The expression deck.deal() invokes the deal() method of deck, which removes and returns the top Card in deck. The value of the expression is therefore of type Card. We pass this as an argument to the push() method from s, which is a Stack of Cards.

The play() method (Figure 4-10) is by far the longest in the class. In addition to invoking deal(), it invokes two other methods, removeLowCard() and removePair(). Notice that play() uses the isEmpty() Stack method.

Figure 4-10. The play() method.

Both removeLowCard() and removePair() (Figure 4-11) use pop(). The pop() method returns a value, but we don't use that value in this particular program.

Since we print the IdiotsDelight instance on line 5 of play(), we need to provide a toString() method. This method, shown in Figure 4-12, uses peek() to look at the top card on each Stack.

Figure 4-11. The removeLowCard() and removePair() methods.

Figure 4-12. The toString() method.

We'll write the Card, Deck, and ArrayStack classes in Chapter 5. We will certainly have to provide the methods we've invoked on instances of these classes. Our knowledge of the program so far is shown in Figure 4-13.

Figure 4-13. UML class diagram of the Idiot's Delight program so far. The four Stacks to which an instance of IdiotsDelight is related are actually instances of the ArrayStack class, which implements the Stack interface.

While we cannot actually run our program at this stage, Figure 4-14 shows how it will behave when it's done.

Figure 4-14. The first few turns of a game of IdiotsDelight. Tc stands for "10 of clubs."

Exercises