Inside a Stack

Programmers use arrays to store values that are referenced by a stack. As you ll recall from Chapter 3, an array consists of a series of array elements, each of which is similar in concept to a variable. The stack contains the index of the array element that is at the top of the stack.

Figure 4-1 is the way some programmers envision an array used with a stack. This example shows an array called stack with 8 array elements. The entire array contains values that are referenced by the stack. Three array elements are assigned values, while the other array elements are empty and can be used when new items are placed on the stack (see the upcoming section Push ).

Mike is the first value placed on the stack. You know this because Mike is at the bottom of the stack. Bob is the last item placed on the stack because Bob is the top item on the stack.

Push

Programmers use the term push to mean placing an item on a stack. Push is the direction that data is being added to the stack. Think of this as pushing items down on the stack to move the items already on the stack down to make room for the next item.

Here s what actually happens. The new value is assigned to the next available array element and the index of that array element becomes the top of the stack, as shown in Figure 4-2. The program increments the current index of the stack by 1. In this example, the index is incremented by 1, resulting in index 3 being at the top of the stack, which is the index of the new values assigned to the array.

Figure 4-2: The new value is assigned to the next array element and its index becomes the top of the stack.

Pop

Popping is the reverse process of pushing: it removes an item from the stack. It is important to understand that popping an item off the stack doesn t copy the item. Once an item is popped from the stack, the item is no longer available on the stack, although the value remains in the array.

Here s what really happens. Remember that the top of the stack contains an index of the array element whose value is at the top of the stack. In Figure 4-2, index 3 is at the top of the stack, which means New Value in array element 3 is at the top of the stack.

When you pop New Value from the stack, you decrement the index at the top of the stack. That is, you make its index 2 instead of 3. This makes Bob the new value at the top of the stack (see Figure 4-3). Notice that New Value and array element 3 remain untouched in the array because popping a value from the stack only alters the stack, not the underlying array.

Figure 4-3: All values move toward the top of the stack when the top item is popped off the stack.