Java Reference
In-Depth Information
Assume we have the following situation, where a number, like
100
, represents the
return address
, which is the
address of the next instruction to be executed when the function returns:
function A function B function C function D
. . . .
C; D; B; .
100: 200: 300:
. . . .
When
A
calls
C
, the address
100
is pushed onto a stack,
S
. When
C
calls
B
,
300
is pushed onto
S
. When
B
calls
D
,
200
is pushed onto
S
. At this stage, the stack looks like the following, and control is in
D
:
(bottom of stack) 100 300 200 (top of stack)
When
D
finishes and is ready to return, the address at the top of the stack (
200
) is popped, and execution
continues at this address. Note that this is the address immediately following the call to
D
.
Next, when
B
finishes and is ready to return, the address at the top of the stack (
300
) is popped, and execution
continues at this address. Note that this is the address immediately following the call to
B
.
Finally, when
C
finishes and is ready to return, the address at the top of the stack (
100
) is popped, and execution
continues at this address. Note that this is the address immediately following the call to
C
.
Naturally, queue data structures are used in simulating real-life queues. They are also used to implement
queues in the computer. In a multiprogramming environment, several jobs may have to be queued while waiting on a
particular resource such as processor time or a printer.
Stacks and queues are also used extensively in working with more advanced data structures such as trees and
graphs. We will discuss trees in Chapter 8.
eXerCISeS 4
1.
What is an
abstract data type
?
2.
What is a
stack
? What are the basic operations that can be performed on a stack?
3.
What is a
queue
? What are the basic operations that can be performed on a queue?
4.
Modify program p4.5 to recognize infix expressions with mismatched brackets.
5.
program p4.5 works with single-digit operands. Modify it to handle any integer operands.
6.
Modify program p4.5 to handle expressions with operations such as
%
, square root, sine,
cosine, tangent, logarithm, and exponential.
7.
Write declarations/functions to implement a stack of
double
values.
8.
Write declarations/functions to implement a queue of
double
values.
Search WWH ::
Custom Search