Stacks Implementation

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.

stack_array.gif

 

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.

stack_linked_list.gif

 

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s