Java Reference
In-Depth Information
The stack operations are O(1) for an array-based implementation. However, when the array is full,
push
dou-
bles the size of the array. In that case,
push
is O(
n
). If you spread this extra cost over all other pushes, and if
doubling the array is not frequent,
push
is almost O(1).
●
You can implement a stack by using a vector. You maintain the stack's bottom entry at the beginning of
the vector.
●
Since the implementation of
Vector
is based on an array that can be resized dynamically, the performance of
a vector-based implementation is like that of the array-based implementation.
●
E
XERCISES
1.
Discuss the advantages and disadvantages of an array-based implementation of the ADT stack as compared to a
linked implementation.
2.
Consider the ADT bag, as described in Chapters 1 through 3.
a.
Would you be able to implement the ADT stack by using a bag to contain its entries? Justify your answer.
b.
Would you be able to implement the ADT bag by using a stack to contain its entries? Justify your answer.
3.
Suppose that the ADT stack included the void method
display
, which displays the entries in a stack. Implement
this method for each of the following classes:
a.
LinkedStack
, as outlined in Listing 6-1.
b.
ArrayStack
, as outlined in Listing 6-2.
c.
VectorStack
, as outlined in Listing 6-3.
d.
Any client of
LinkedStack
,
ArrayStack
, or
VectorStack
.
4.
Repeat the previous exercise, but define the method
toArray
instead of the method
display
.
5.
Suppose that the ADT stack included a void method
remove(n)
that removes the topmost
n
entries from a stack.
Specify this method by writing comments and a header. Consider the possible outcomes for stacks that do not con-
tain
n
entries.
6.
Repeat Exercise 3, but define the method
remove(n)
, as described in the previous exercise, instead of the
method
display
.
7.
Imagine a linked implementation of the ADT stack that places the top entry of the stack at the end of a chain of
linked nodes. Describe how you can define the stack operations
push
,
pop
, and
peek
so that they do not traverse
the chain.
8.
Segment 6.9 noted that an array-based
push
method is normally O(1), but when a stack needs to be doubled in
size,
push
is O(
n
). This observation is not as bad as it seems, however. Suppose that you double the size of a stack
from
n
elements to 2
n
elements.
a.
How many calls to
push
can you make before the stack must double in size again?
b.
Remembering that each of these calls to
push
is O(1), what is the average cost of all the
push
operations?
(The average cost is the total cost of all calls to
push
divided by the number of calls to
push
.)
9.
Suppose that instead of doubling the size of an array-based stack when it becomes full, you just increase the size
of the array by 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?
