As we did with the ordered list, we are going to look at two implementations of a stack. The first implementation uses an array to create the stack data structure, and the second implementation uses pointers.

Array Implementation

In order to implement a stack using an array, we need to reserve a block of memory cells large enough to hold all the items we want to put on the stack. The picture below shows an array of six memory cells that represent our stack. Notice that we have one other memory cell called a stack pointer that holds the location of the top of our stack. As the stack grows and shrinks, this pointer is updated so that it always points to the top item of the stack.

Notice that our array implementation retains one of the problems we saw with the array implementation of an ordered list. Since our array is a fixed size, our stack can only grow to a certain size. Once our stack is full, we will have to use the PopStackItem operation before we can push any more items onto the stack. To make the size of our stack more flexible, we can use pointers to implement the stack.

Pointer Implementation

In order to implement a stack using pointers, we need to link nodes (groups of memory cells) together just like we did for the pointer implementation of a list. Each node contains a stack item and a pointer to the next node. We also need a special pointer to keep track of the top of our stack.

Notice that the stack operations can get a little tricky when we use pointers. To push an item onto the stack, we need to find a free memory location, set the pointer of the new location to the top of the stack, and finally set the stack pointer to the new location. The order of these operations is very important. If we set the stack pointer to the location of the new memory first, we will lose the location of the top of our stack. This example shows the same tradeoff that we saw earlier with the ordered list implementations. While the array implementation is simpler, the added complexity of the pointer implementation gives us a more flexible stack.