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.

 1 /** A last-in, first-out stack of Objects. */
 2 public interface Stack {
 3
 4 /** Return true if this Stack is empty. */
 5 public boolean isEmpty();
 6
 7 /**
 8 * Return the top Object on this Stack. Do not modify the Stack.
 9 * @throws EmptyStructureException if this Stack is empty.
10 */
11 public Object peek();
12

13 /** 14 * Remove and return the top Object on this Stack. 15 * @throws EmptyStructureException if this Stack is empty. 16 */ 17 public Object pop(); 18 19 /** Add target to the top of the Stack. */ 20 public void push(Object target); 21 22 }

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'.

 1 /** A last-in, first-out stack. */
 2 public interface Stack {
 3
 4 /** Return true if this Stack is empty. */
 5 public boolean isEmpty();
 6
 7 /**
 8 * Return the top item on this Stack, but do not modify the Stack.
 9 * @throws EmptyStructureException if this Stack is empty.
10 */
11 public E peek();
12
13 /**
14 * Remove and return the top item on this Stack.
15 * @throws EmptyStructureException if this Stack is empty.
16 */
17 public E pop();
18
19 /** Add target to the top of the Stack. */
20 public void push(E target);
21
22 }

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).

Idiot's Delight

Players: 1

Object: To clear all the cards off the table.

Setup: Shuffle a deck of cards and deal four cards face up in a row, forming four stacks.

Play: On your turn, you may do any one of the following:

• If there are two cards of the same rank showing, discard both of them.
• If there are two cards of the same suit showing, discard the one with lower rank.
• Deal four new cards, one on top of each stack.

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.

 1 import java.util.Scanner;
 2
 3 /** The solitaire card game Idiot's Delight. */
 4 public class IdiotsDelight {
 5
 6 /** For reading from the console. */
 7 public static final Scanner INPUT = new Scanner(System.in);
 8
 9 /** The four Stacks of Cards. */
10 private Stack[] stacks;
11
12 /** The Deck of Cards. */
13 private Deck deck;
14
15 /** Create and play the game. */
16 public static void main(String[] args) {
17 System.out.println("Welcome to Idiot's Delight.");
18 IdiotsDelight game = new IdiotsDelight();
19 game.play();
20 }
21
22 }

Figure 4-8. Constructor for the IdiotsDelight class.

 1 /** Create and shuffle the Deck. Deal one Card to each Stack. */
 2 public IdiotsDelight() {
 3 deck = new Deck();
 4 deck.shuffle();
 5 stacks = new Stack[4]; // This causes a compiler warning
 6 for (int i = 0; i < 4; i++) {
 7 stacks[i] = new ArrayStack();
 8 }
 9 deal();
10 }

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.

1 /** Deal one Card from the Deck onto each Stack. */
2 public void deal() {
3 for (Stack s : stacks) {
4 s.push(deck.deal());
5 }
6 }

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.

 1 /** Play the game. */
 2 public void play() {
 3 while (true) {
 4 // Print game state
 5 System.out.println("
" + this);
 6 // Check for victory
 7 boolean done = true;
 8 for (Stack s : stacks) {
 9 if (!(s.isEmpty())) {
10 done = false;
11 break;
12 }
13 }
14 if (done) {
15 System.out.println("You win!");
16 return;
17 }
18 // Get command
19 System.out.print("Your command (pair, suit, deal, or quit)? ");
20 String command = INPUT.nextLine();
21 // Handle command
22 if (command.equals("pair")) {
23 removePair();
24 } else if (command.equals("suit")) {
25 removeLowCard();
26 } else if (command.equals("deal")) {
27 deal();
28 } else {
29 return;
30 }
31 }
32 }

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.

 1 /**
 2 * Remove the lower of two Cards of the same suit, as specified by
 3 * the user.
 4 */
 5 public void removeLowCard() throws IllegalMoveException {
 6 System.out.print("Location (1-4) of low card? ");
 7 int i = INPUT.nextInt();
 8 System.out.print("Location (1-4) of high card? ");
 9 int j = INPUT.nextInt();
10 INPUT.nextLine(); // To clear out input
11 stacks[i - 1].pop();
12 }
13
14 /**
15 * Remove two Cards of the same rank, as specified by the user.
16 */
17 public void removePair() throws IllegalMoveException {
18 System.out.print("Location (1-4) of first card? ");
19 int i = INPUT.nextInt();
20 System.out.print("Location (1-4) of second card? ");
21 int j = INPUT.nextInt();
22 INPUT.nextLine(); // To clear out input
23 stacks[i - 1].pop();
24 stacks[j - 1].pop();
25 }

Figure 4-12. The toString() method.

 1 public String toString() {
 2 String result = "";
 3 for (int i = 0; i < 4; i++) {
 4 if (stacks[i].isEmpty()) {
 5 result += "-- ";
 6 } else {
 7 result += stacks[i].peek() + " ";
 8 }
 9 }
10 return result + "
" + deck.size() + " cards left in the deck";
11 }

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."

 1 Welcome to Idiot's Delight.
 2
 3 3c 7h Kd As
 4 48 cards left in the deck
 5 Your command (pair, suit, deal, or quit)? deal
 6
 7 9h 9s 2d Tc
 8 44 cards left in the deck
 9 Your command (pair, suit, deal, or quit)? pair
10 Location (1-4) of first card? 1
11 Location (1-4) of second card? 2
12
13 3c 7h 2d Tc
14 44 cards left in the deck
15 Your command (pair, suit, deal, or quit)? suit
16 Location (1-4) of low card? 1
17 Location (1-4) of high card? 4
18
19 -- 7h 2d Tc
20 44 cards left in the deck

Exercises

4.1	The following sequence of methods are to be invoked on an initially empty stack. Draw the state of the stack (in the style of Figure 4-1) after each step. Indicate what is returned by any methods that return values. push("a"); push("b"); push("c"); pop(); push("d"); push("e"); peek(); pop(); pop();
4.2	Discuss whether a PEZ candy dispenser is a good analogy for a stack.
4.3	Both the IdiotsDelight class and the Deck class have a method called deal(). Is this an example of overloading, overriding, neither, or both?
4.4	Discuss whether line 11 in the play() method (Figure 4-10) is necessary.