Java Reference
In-Depth Information
10.
Suppose that instead of doubling the size of an array-based stack when it becomes full, you increase the size of the
array by the following sequence 3
k
, 5
k
, 7
k
, 9
k
, ... for some positive constant
k
.
a.
If you have an empty stack that uses an array whose initial size is
k
, and you perform
n
pushes, how many
resize operations will be performed? Assume that
n
>
k
.
b.
What is the average cost of the
n
push operations?
11.
When an array becomes full, you can double its size or use one of the schemes described in Exercises 9 and 10.
What are the advantages and disadvantages of each of these three schemes?
12.
Imagine several stack operations on an array-based stack. Suppose that the array doubles in size, but later fewer
than half of the array's locations are actually used by the stack. Describe an implementation that halves the size of
the array in this case. What are the advantages and disadvantages of such an implementation?
P
ROJECTS
1.
Implement the ADT stack by using an array
stack
to contain its entries. Expand the array dynamically, as neces-
sary. Maintain the stack's bottom entry in
stack[stack.length
-
1]
.
2.
Repeat Project 1, but maintain the stack's top entry in
stack[stack.length
-
1]
.
3.
Repeat Project 1, but maintain the stack's top entry in
stack[0]
.
4.
Write the implementation of the ADT stack that Exercise 7 describes.
5.
The ADT stack lets you peek at its top entry without removing it. For some applications of stacks, you also need
to peek at the entry beneath the top entry without removing it. We will call such an operation
peek2
. If the stack
has more than one entry,
peek2
returns the second entry from the top without altering the stack. If the stack has
fewer than two entries,
peek2
returns
null
. Write a linked implementation of a stack that includes a method
peek2
.
6.
When the client attempts to either retrieve or remove an item from an empty stack, our stacks return
null
. An
alternative action is to throw an exception.
a.
Modify the interface
StackInterface
so that an
EmptyStackException
is thrown in these cases. (This
exception is defined in the package
java.util
.)
b.
Modify the array-based implementation of the stack to conform to your changes to
StackInterface
.
Write a program that demonstrates the modifications.
c.
Repeat Part
b
for the linked implementation of the stack.
7.
Suppose that we wish to implement the resizing schemes described in Exercises 9 and 10 in addition to the dou-
bling scheme.
a.
Write a new version of the array-based stack that lets the client specify the resizing scheme and the associ-
ated constant when a stack is created.
b.
Write a program that demonstrates the modifications.
c.
Discuss the advantages and disadvantages of adding methods that allow the client to change the resize
scheme and constant after the stack has been created.
8.
Implement the ADT bag by using a vector to contain its entries.
