Java Reference
In-Depth Information
Question 1
Revise the previous implementation of
pop
so that it does not call
peek
.
6.6
The rest of the class.
The remaining public methods
isEmpty
and
clear
involve only
topNode
:
public boolean
isEmpty()
{
return
topNode ==
null
;
}
// end isEmpty
public void
clear()
{
topNode =
null
;
}
// end clear
Question 2
Is an implementation of the ADT stack reasonable if the top of the stack is at
the end of a chain of linked nodes instead of its beginning? Explain.
6.7
If we use an array to implement the stack, where should we place the stack's top entry? If the first
location of the array references the top entry, as shown in Figure 6-4a, we must move all the
entries in the array any time we add or remove a stack entry. We can have more efficient stack
operations if the first array location references the bottom entry of the stack. The top entry of the
stack is then referenced by the last occupied location in the array, as Figure 6-4b shows. This con-
figuration allows us to add or remove stack entries without moving other array elements. Thus, one
disadvantage of a typical array-based implementation does not apply here. The exercises at the end
of this chapter consider other ways to place a stack's entries in an array.
Resizing the array avoids a stack that is too full to accept another entry. However, unlike the
linked chain in the previous section, the array in Figure 6-4 contains locations that are unused. If we
eventually fill the array with additional stack entries, we can expand the size of the array—but then
we will have more unused locations. The chain has its downside as well, in that it uses additional
memory for the link portions of its nodes.
VideoNote
The Class
ArrayStack
Note:
If you use an array to implement a stack, the array's first location is the bottom of the
stack. The last occupied location in the array, then, references the stack's top entry.
FIGURE 6-4
An array that implements a stack; its first location references
(a) the top entry in the stack; (b) the bottom entry in the stack
(a)
0
1
2
3
Array
3
bottomIndex
Top entry of stack
Stack
