Version 6.1¹

Handouts:

• Reverse.java
• Printing.java

Reading:

• Chapter 4, "Stacks and Queues."

Principal points to understand:

1. The Stack interface: how to declare it, what it does.
2. Generics: why they were added to Java, how to use them.
3. The call stack: how it supports execution of method calls.
4. Exceptions: what are they, how to use them.
5. The Queue interface: how to declare it, what it does.

Part A: Pages 87–100

Stacks and queues are similar: both are collections ordered by time of insertion.

Differences: stacks allow access to the most recently inserted element; queues, least recently inserted.

We study the stack and queue ADTs (represented as interfaces) in this chapter, deferring their implementations to the next two chapters.

[So now we see some of the value of interfaces!]

4.1 A Stack Interface

• Top of stack—Fig. 4-1, p. 88
• Operations: push, pop, peek, isEmpty
• LIFO (Last In, First Out): remove elements in opposite order from insertion
• The interface declaration, version 1 (non-generic, i.e., a stack of Objects): Fig. 4-2 pp. 88–89

The Class java.util.Stack

Although Drake presents the stack ADT as an interface, that is not the only way. The standard Java library includes the class java.util.Stack. Find its documentation in the Java API documentation. How does it compare with Drake's stack interface?

Note: although java.util.Stack is a class, not an interface, to us it's still an abstract data type, because we do not know how it is implemented. (Since Java is now largely open, we could peek at the source code to find out. But we don't have to!)

Generics

• Motivation: if we have a stack of Objects, we can push a Die, but pop an Object
  • Need to cast the Object as Die in order to use Die methods
  • Awkward
• Also we might intend it to be a stack containing only Dice, but accidentally push something else into the stack.
• Generic types (classes and interfaces) were introduced in Java 1.5. [Also called parametric types in some programming languages.]
• Main idea: a generic type has one or more type parameters, typically specifying the types of elements it can contain.
  • Type parameters are written e.g. <E> in the class declaration
  • This becomes E in the class's field and method declarations.
  • To instantiate the type we substitute a specific type for E, e.g., Stack<Integer> mystack;
  • The default value for E is Object; we can still have this degree of flexibility. I.e., Stack mystack; is equivalent to Stack<Object> mystack;
• The Stack interface declaration, version 2 (generic):
  • Code, Fig. 4-2 p. 90
  • Compare to version 1

  • Instantiating the generic type: p. 89 near bottom shows this code:

    Stack<Die> s = new Stack<Die>();

    but this is incorrect; we cannot instantiate an interface.
  • We must instantiate instead a class that implements the interface.

  • Assuming that StackImpl<E> is a class that implements Stack<E>, we could write

    Stack<Die> s = new StackImpl<Die> ();

• Advantages of generic types:
  • Stricter type checking: cannot push a Beetle onto a Stack<Die>

  • Avoid ugly casts, e.g., if we have a stack of Objects,

    myStack.push(new Beetle());
    Beetle tony = (Beetle) (myStack.pop());

• Disadvantage: additional complexity sometimes creates problems.
  • Confusion: more syntax!
  • The type parameters exist only at compile time. This sometimes leads to confusion, because ...?
• Generic types are an option. We are not required to use them. But in many cases it's a good idea.

A Stack Example

• Reversing the order of words in a message, using a stack:
  • Reverse.java

Exercises

(???) p. 97: #4.1, 4.2, 4.3.

4.2 The Call Stack

[The problem that a call stack solves: Suppose we have the method calls graphed below (method name: local variables, including formal arguments):

main (args)
   ↓
A(x, y)
   ↓
B(y, z)
   ↓
C(z, w)

Two problems arise:

1. Since A, B, and C all share variable names, how can these be kept from conflicting?
2. How does each method know where to return to?

The problem also occurs, of course, with recursive method calls:

main(args)
   ↓
fact(n)
   ↓
fact(n)
   ↓
fact(n)

Here, each call to fact requires its own argument n, typically proceeding as n → n − 1. How can these multiple n's keep out of each other's hair?]

Solution: Java, like most programming languages, uses a stack, known as the call stack (or just the stack) to keep track of what's going on (the state of each method call, including local variables and where to return to—also which instruction is next, but that's tracked by the hardware).

• The call stack contains call frames as elements— also called activation records.
  • Each call frame represents a particular call or activation of a particular method. It stores the parameters and other local variables of the method call, and the return address.
• Fig. 4-16 p. 99: explain in detail. Identify the call frames. (Actually the line numbers are in the wrong frames.)
• Importance of the call stack:
  • It makes nested method calls possible, including recursive method calls.
  • Usually we can forget about the call stack.
  • But understanding it can shed light on recursion (chapter 9) and on Java error messages which print out a stack trace when the program crashes.
  • See Fig. 4-17 p. 100
    • Interpret the stack trace.
    • Focuses the debugging programmer's attention on two methods: the method where the exception occurred, and the method that called it. Suspect either a bug in the method or that it was improperly called.

Exercises

(???) Page 100: #4-5, 4-6.

(???) Optional: p. 115, #4.16

(???) Lab 2: p. 116, Project 4.20

• Demonstrate the Postfix desktop calculator dc
  • p prints top of stack("peek")
  • [Hello world]p prints "Hello world"
  • Control-D to exit

Part B: Pages 100–110

4.3 Exceptions

• Exceptions and assertions both help us detect erroneous conditions in the program. Compared to assertions, exceptions provide a more graceful, controlled way of dealing with the error. They can also be used for conditions that are simply unusual, not erroneous.
  • What is an error?
• An exception is thrown where the error occurs and then either is caught or causes the program to crash with a stack trace.
• Java exceptions are objects
  • Descended from java.lang.Exception
  • Fig. 4-18 p. 101 shows a few classes of exceptions. Java has many built-in exception types.
  • We can also define our own classes of exception
    • See Fig. 4-19 p. 101. This exception class is minimal: it has only a class name.
    • That by itself only signifies what kind of error occurred, but it is frequently enough information to make the exception class useful.
    • Of course, we can also provide our exception class with fields and methods, providing details of what happened, customized error messages, etc.
• Writing methods that throw exceptions (say, RottenException).
  1. Declare that the method throws RottenException
  2. Document the exception in the method's Javadoc comment, using the keyword @throws

  3. Write code to create and throw the exception, e.g.,

     if (...)
       throw new RottenException();

  4. Example: see Fig. 4-20 p. 102: the deal method in IdiotsDelight.java
• Calling methods that throw exceptions (say, RottenException). There are two choices.
  1. "Pass the buck", ignoring the exception and letting it percolate upwards to the next caller. The calling method must then declare throws RottenException unless RottenException is descended from RuntimeException, which need not be declared.

  2. Catch the exception using a try/catch statement:

     try {
       ...
     }
     catch (RottenException e) {
       ...do-something-with-e...
     }

     • Things you can do with an exception at run time:
       • Try to correct the error, e.g., ask the user for valid input

       • Print a stack trace and exit abnormally:

         e.printStackTrace();
         System.exit(1);

       • The 1 here is a return code, signifying that something went wrong. The convention is to return 0 to the operating system when the program terminates normally, and various non-zero codes otherwise.

       • These return codes can be tested by shell scripts, e.g., the shell logical operators && and ||:

         $ java MyRottenClass || echo "something's wrong here"
         $ java MyRottenClass && echo "success!"

         or using the shell's $? to retrieve the value of the return code:

         $ java MyRottenClass
         $ echo $?

         or using the bash if statement (untested example):

         $ if java MyRottenClass; then
             echo "Hooray!"
           else
             echo "Boo-hoo"
           fi

• A few of the standard Exception classes: see Fig. 4-28 p. 107. Note that methods that throw RuntimeException s do not need to declare them.

4.4 A Queue Interface

• Queues operate according to a FIFO (First In, First Out) policy: the first element in is the first one removed.
• The Queue interface: Fig. 4-30 p. 109
• Important note: many authors use (and I prefer) the terms enqueue for add, and dequeue for remove. How to remember:
  • enqueue as in enter (enter queue)
  • dequeue as in depart (depart queue)
• You could also add a front method, analogous to peek for stacks.
• ??? Exercises: pp. 113–114: #4.12, 4.13, 4.14

A Queue Example

• A queue to manage printing
  • Printing.java

End of Chapter

Problems, p. 115–116:

• #4.15, 4.16—discuss, do not code
• #4.18: the Deque data type
  • Our solution: Deque.java (restricted access)
• #4.19 The DoubleStackQueue
  • Our solution: DoubleStackQueue.java (restricted access)

Project (Lab L2)

• Basic problem: pp. 116–117 #4.20: postfix calculator
• Detailed instructions

Footnotes