Stack Implementations - Data Structures and Abstractions with Java - page 143

To indicate an empty stack, we have assigned - 1 to topIndex as its initial value. This choice
allows push to simply increment topIndex before using it when placing a new entry in the array.

6.9

Adding to the top. The push method checks whether the array has room for a new entry by calling
the private method ensureCapacity . It then places the new entry immediately after the last occu-
pied location in the array:

public void push(T newEntry)
{

ensureCapacity();
topIndex++;
stack[topIndex] = newEntry;
} // end push
private void ensureCapacity()
{

if (topIndex == stack.length - 1) // if array is full,
// double size of array
stack = Arrays.copyOf(stack, 2 * stack.length);
} // end ensureCapacity

Note that ensureCapacity is similar to the ensureCapacity method in the class Resizable-
ArrayBag , which we encountered in Chapter 2. Both private methods double the size of an array
after it becomes full.
When ensureCapacity does not resize the array stack , push is an O(1) operation, since its
performance is independent of the size of the stack. However, resizing the array is an O( n ) opera-
tion, so when the array is full, the performance of push degrades to O( n ). If this happens, however,
the very next push is O(1) again. To be fair, all push operations should share the cost of the occa-
sional resize of the array. That is, we amortize the cost of doubling the array size over all additions
to the stack. Unless we must resize the array many times, each push is almost O(1).

6.10

Retrieving the top. The operation peek returns either the array entry at topIndex or null if the
stack is empty:

public T peek()
{

T top = null ;
if (!isEmpty())
top = stack[topIndex];
return top;
} // end peek

This operation is O(1).

6.11

Removing the top. The pop operation, like peek , retrieves the top entry in the stack, but then
removes it. To remove the stack's top entry in Figure 6-4b, we could simply decrement topIndex ,
as Figure 6-5a illustrates. This simple step would be sufficient, since the other methods would
behave correctly. For example, given the stack pictured in Figure 6-5a, peek would return the item
that stack[2] references. However, the object that previously was the top entry and has now been
returned to the client would still be referenced by the array. No harm will come from this situation
if our implementation is correct. To be safe, pop can set stack[topIndex] to null before decre-
menting topIndex . Figure 6-5b illustrates the stack in this case.