Figure 4-15 shows a program for computing the length of the hypotenuse of a right triangle, given the lengths of the other two sides.

Figure 4-15. To keep things simple, all of the methods in the Hypotenuse class are static.

1 /** Compute the hypotenuse of a right triangle. */ 2 public class Hypotenuse { 3 4 /** Return the square of the number x. */ 5 public static double square(double x) { 6 return x * x; 7 } 8 9 /** 10 * Return the hypotenuse of a right triangle with side lengths x 11 * and y. 12 */ 13 public static double hypotenuse(double x, double y) {14 double x2 = square(x); 15 double y2 = square(y); 16 return Math.sqrt(x2 + y2); 17 } 18 19 /** Test the methods. */ 20 public static void main(String[] args) { 21 double result = hypotenuse(3, 4); 22 System.out.println(result); 23 } 24 25 } |

The `hypotenuse()` method invokes the `square()` method twice: once on line 13 and once on line 14. When Java finishes an invocation of `square()`, how does it know where to go next? Should it invoke `square()` again or go on to `Math.sqrt()`?

The vague answer is that Java somehow "keeps track of" what it was doing before the invocation started. How? Using a stack.

This stack, called the call stack, exists behind the scenes. It is not an object that we can access, but we can understand it now that we know about stacks.

Every time a method is invoked, a behind-the-scenes object called a call frame is created. The call frame keeps track of the current state of the method. Specifically, it stores any arguments or variables for the method. It also keeps track of how far along the method has proceeded.

The history of the call stack for this program is illustrated in Figure 4-16. When Java first starts up, the call stack is empty. When `main()` is invoked, a new call frame is created and pushed onto the stack. This call frame stores the value of `args` (which we ignore in this example) and `result`, as well as the fact that we are at the beginning of the `main()` method (that is, line 20). (The author has carefully crafted the Hypotenuse program so that only one method invocation happens on each line. In a more complicated program, Java would break each line into multiple steps.)

Figure 4-16. History of the call stack for the Hypotenuse program.

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

On line 20, the `main()` method invokes `hypotenuse(3, 4)`. Java creates a call frame for `hypotenuse()` and pushes it onto the stack. In this new call frame, `x` is 3, `y` is 4, and the method is at the beginning, on line 13. The variables `x2` and `y2` have not yet been initialized.

The `hypotenuse()` method then needs `square(3)`, which causes yet another call frame to be pushed onto the stack. At any point, only the top frame on the call stack is active. The others are waiting for answers from methods they invoked. This clears up any confusion between arguments and variables with the same name in different methods, or in different invocations of the same method.

When `square()` finishes, its call frame is popped off the stack. The next frame down, the invocation of `hypotenuse()`, stores the returned value 9 in the variable `x2` and moves on to ask for `square(4)`.

Eventually, `main()` finishes, the last call frame is popped off the stack, and the program is done.

This was a lot of work, and we can be thankful that Java does it for us. We normally don't even have to think about the call stack, although it will be useful knowledge when we discuss recursion in Chapter 9.

Knowledge of the call stack also helps us understand some of Java's error messages. Suppose we are playing Idiot's Delight and decide to deal out all of the cards before discarding any. Unfortunately, we aren't paying attention to the number of cards left and we try to deal from any empty deck. The program crashes with a message like the one shown in Figure 4-17.

Figure 4-17. Stack trace in an error message from Java.

1 Exception in thread "main" 2 java.lang.ArrayIndexOutOfBoundsException: -1 3 at Deck.deal(Deck.java:25) 4 at IdiotsDelight.deal(IdiotsDelight.java:24) 5 at IdiotsDelight.play(IdiotsDelight.java:58) 6 at IdiotsDelight.main(IdiotsDelight.java:81) |

The error message shows a stack trace (a snapshot of the call stack) indicating what was going on when the program crashed. The actual error occurred in the `deal()` method of the Deck class, so the top call frame was an invocation of this method. It was invoked in line 24 of the `deal()` method from the IdiotsDelight class, which was invoked on line 58 of the `play()` method, which was invoked on line 81 of the `main()` method. (These line numbers are from the complete files, so they won't match the numbers in our figures. Your numbers may differ due to whitespace, comments, and so on.)

Examining a stack trace makes our debugging much easier, because we can immediately tell that the `deal()` method from Deck either contains a bug or (as in this example) was called inappropriately. The next section discusses how to deal with such bad input without crashing the program.

Exercises

4.5 |
Can two call frames ever be waiting for each other? Explain. |

4.6 |
Every method invocation involves pushing a frame onto the call stack, which takes up time and memory. Discuss whether we should avoid this by writing every program in a single, monolithic |

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

- Inheritance
- Extending a Class
- The Object Class
- Packages and Access Levels
- Summary
- Vocabulary
- Problems
- Projects

Part II: Linear Structures

Stacks and Queues

- Stacks and Queues
- The Stack Interface
- The Call Stack
- Exceptions
- The Queue Interface
- Summary
- Vocabulary
- Problems
- Projects

Array-Based Structures

- Array-Based Structures
- Shrinking and Stretching Arrays
- Implementing Stacks and Queues
- The List Interface
- Iterators
- The Java Collections Framework: A First Look
- Summary
- Vocabulary
- Problems
- Projects

Linked Structures

- Linked Structures
- List Nodes
- Stacks and Queues
- The LinkedList Class
- The Java Collections Framework Revisited
- Summary
- Vocabulary
- Problems
- Projects

Part III: Algorithms

Analysis of Algorithms

- Analysis of Algorithms
- Timing
- Asymptotic Notation
- Counting Steps
- Best, Worst, and Average Case
- Amortized Analysis
- Summary
- Vocabulary
- Problems
- Projects

Searching and Sorting

- Searching and Sorting
- Linear Search
- Binary Search
- Insertion Sort
- The Comparable Interface
- Sorting Linked Lists
- Summary
- Vocabulary
- Problems
- Projects

Recursion

- Recursion
- Thinking Recursively
- Analyzing Recursive Algorithms
- Merge Sort
- Quicksort
- Avoiding Recursion
- Summary
- Vocabulary
- Problems
- Projects

Part IV: Trees and Sets

Trees

Sets

- Sets
- The Set Interface
- Ordered Lists
- Binary Search Trees
- Hash Tables
- The Java Collections Framework Again
- Summary
- Vocabulary
- Problems
- Projects

Part V: Advanced Topics

Advanced Linear Structures

- Advanced Linear Structures
- Bit Vectors
- Sparse Arrays
- Contiguous Representation of Multidimensional Arrays
- Advanced Searching and Sorting
- Summary
- Vocabulary
- Problems
- Projects

Strings

Advanced Trees

- Advanced Trees
- Heaps
- Disjoint Set Clusters
- Digital Search Trees
- Red-Black Trees
- Summary
- Vocabulary
- Problems
- Projects

Graphs

- Graphs
- Terminology
- Representation
- Graph Traversal
- Topological Sorting
- Shortest Paths
- Minimum Spanning Trees
- Summary
- Vocabulary
- Problems
- Projects

Memory Management

Out to the Disk

- Out to the Disk
- Interacting with Files
- Compression
- External Sorting
- B-Trees
- Summary
- Vocabulary
- Problems
- Projects

Part VI: Appendices

A. Review of Java

- A. Review of Java
- A.1. The First Program
- A.2. Variables and Types
- A.3. Loops
- A.4. Interacting with the User
- A.5. Branching
- A.6. Methods and Breaking Out
- A.7. Constants
- A.8. Operators
- A.9. Debugging
- A.10. Coding Conventions

B. Unified Modeling Language

C. Summation Formulae

- C. Summation Formulae
- C.1. Sum Notation
- C.2. Sum of Constants
- C.3. Sum of First n Integers
- C.4. Sums of Halves and Doubles
- C.5. Upper Limit on Sum of a Function
- C.6. Constant Factors

D. Further Reading

Index

Data Structures and Algorithms in Java

ISBN: 0131469142

EAN: 2147483647

EAN: 2147483647

Year: 2004

Pages: 216

Pages: 216

Authors: Peter Drake

Flylib.com © 2008-2020.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net