Stack

Another common linear data structure is the stack. Just like we did
with the ordered list, we will examine the abstract view of a stack
first and then look at a couple of ways a stack can be implemented.
In one way, a stack is very similar to a list except that a stack is
more restricted. The animation below should give you a good idea of
the abstract view of a stack. Follow the directions to manipulate a
simple stack and learn about the operations that a stack provides.

Press here to see how to use Stack (Flash Movie)

 

Now that you know how a stack works, you can see that this data structure
is really a restricted list. With the stack, we have restricted the
access to one end of the list by using the pop and push operations.
The result of this restriction is that items in the list pile one on
top of the other. To get to the bottom item, we must first remove all
the items above it. This behavior is sometimes described as “last-in,
first-out” or LIFO since the last item to enter the stack is the
first item to leave the stack. With the stack, the top item is always
the last item to enter the stack and it is always the first item to
leave the stack since no other items can be removed until the top item
is removed.

Let’s take another look at the operations that can be performed on
a stack. We will represent these two operations with the following notation:

Item PushStackItem(Stack,
Item)

Item PopStackItem(Stack)

The PushStackItem operation has two parameters which are a stack
and an item. This operation adds the item to the top of the specified
stack. The PopStackItem operation only takes one parameter which
is a stack. However, notice that this operation has the keyword Item
listed to the left. This keyword represents the item that is removed
from the top of the stack when the PopStackItem operation is
done. These two operations are part of the abstract view of a stack.
They are what we expect from any stack regardless of how it is implemented
in the computer.

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