Abstraction
Now, let's think about a stack in an abstract way. I.e., it doesn't
hold any particular kind of thing (like books) and we aren't
restricting ourselves to any particular programming language or any
particular implementation of a stack.
Stacks hold objects, usually all of the same type. Most stacks support
just the simple set of operations we introduced above; and thus, the
main property of a stack is that objects go on and come off of the
top of the stack.
Here are the minimal operations we'd need for an abstract stack
(and their typical names):
Push:
Places an object on the top of the stack.
Pop:
Removes an object from the top of the stack and
produces that object.
IsEmpty:
Reports whether the stack is empty or not.
Because we think of stacks in terms of the physical analogy, we usually
draw them vertically (so the top is really on top).
-
Order produced by a stack:
Stacks are linear data structures. This means that their contexts are
stored in what looks like a line (although vertically). This linear
property, however, is not sufficient to discriminate a stack from other
linear data structures. For example, an array is a sort of linear data
structure in which you can access any element directly. In contrast,
in a stack, you can only access the element at its top.
One of the distinguishing characteristics of a stack, and the thing
that makes it useful, is the order in which elements come out
of a stack. Let's see what order that is by looking at a stack of
letters...
Suppose we have a stack that can hold letters, call it stack.
What would a particular sequence of Push and
Pops do to this stack?
We begin with stack empty:
-----
stack
Now, let's perform Push(stack, A), giving:
-----
| A | <-- top
-----
stack
Again, another push operation, Push(stack, B),
giving:
-----
| B | <-- top
-----
| A |
-----
stack
Now let's remove an item, letter = Pop(stack), giving:
----- -----
| A | <-- top | B |
----- -----
stack letter
And finally, one more addition, Push(stack, C), giving:
-----
| C | <-- top
-----
| A |
-----
stack
You'll notice that the stack enforces a certain order to
the use of its contents, i.e., the Last thing In
is the First thing Out. Thus, we say that a stack
enforces LIFO order.
Now we can see one of the uses of a stack...To reverse the order of
a set of objects.
-
Implementing a stack with an array:
Since a stack usually holds a bunch of items with the same type, we
could implement a stack as an array.
Consider how we could have an array of characters, contents,
to hold the contents of the stack, and an integer top that
holds the index of the element at the top of the stack.
We choose the array to be of size 4 for now.
Starting with an empty stack, we have:
----------------- -----
| | | | | | -1|
----------------- -----
0 1 2 3 top
contents
Now, the same sequence of operations we used before, namely:
1. Push(stack, 'A')
2. Push(stack, 'B')
3. ch = Pop(stack)
4. Push(stack, 'C')
produce the following effects:
1.
----------------- -----
| A | | | | | 0 |
----------------- -----
0 1 2 3 top
contents
2.
----------------- -----
| A | B | | | | 1 |
----------------- -----
0 1 2 3 top
contents
3.
----------------- -----
| A | | | | | 0 |
----------------- -----
0 1 2 3 top
contents
4.
----------------- -----
| A | C | | | | 1 |
----------------- -----
0 1 2 3 top
contents
If we were actually coding this, we would have to decide what data
types are needed for this stack data structure.
Since for the array implementation, we need to keep track of the
array contents and a top index, how could we combine the
2 into a single C construct called a stack?
What is the disadvantage of using an array to implement
a stack?
-
Implementing a stack with a linked list:
Using a linked list is one way to implement a stack so that it can handle
essentially any number of elements.
Here is what a linked list implementing a stack with 3 elements might
look like:
list
|
v
-------- -------- ---------
| C | -+-->| B | -+-->| A | 0 |
-------- -------- ---------
Where should we consider the top of the stack to be, the
beginning or end of the list, and why?
How will we represent an empty stack?
-
C implementation:
Now, think about how to actually implement this stack of
characters in C.
It is usually convenient to put a data structure in its own module, thus,
we'll want to create files stack.h and a stack.c.
The operations needed for our stack are mainly determined by the
operations provided by an abstract stack, namely:
StackPush()
StackPop()
StackIsEmpty()
We may need to add a few other operations to help implement a stack.
These will become apparent as we start to implement the stack.
Before we ponder the details of the stack operations, what must
we decide on?
-
Data types for a stack:
In order to determine what data types we'll need, let's think about
how someone will use our stack:
1. type-of-a-stack stack1, stack2;
2. StackPush(ref-to-stack1, 'A');
3. StackPush(ref-to-stack2, 'B');
4. ch = StackPop(ref-to-stack1);
First, stack variables must be defined (e.g., stack1 and
stack2). Then, stack operations may be called. Those
operations will need to know which stack to operate on.
Thus, our goal is to get some kind of type that we can use to keep
track of a stack.
Let's start bottom-up from the simplest type and work our way up
through types that use the simpler types...
First, we want to write a stack that is very generic. The fact that
this stack holds a character is only particular to this program. It
should be easy to change the type of things held in the stack.
Let's introduce a type name for the type of thing held in the stack:
typedef char stackElementT;
Now, elements of the stack are being stored in a linked list.
Recall that linked lists are made up of nodes that
contain both an element and a pointer to the next
node.
How do we define the type for a node?
typedef struct stackTag {
stackElementT element;
struct stackTag *next;
} stackNodeT;
Finally, we need something that holds all the information needed to
keep track of the stack. Since elements will be held in nodes, we only
need a pointer to keep track of the beginning of the list (which will
be our top of the stack).
We suggest that this single pointer be put in a structure, so that we
can give it a descriptive field name and so that we can add more fields
easily in the future (if needed):
typedef struct {
stackNodeT *top;
} stackT;
-
Filling in stack operations:
Now that we've decided on the data types for a stack, we think we'd
like to add 2 extra operations:
StackInit()
StackDestroy()
They are not part of the abstract concept of a stack, but
they are necessary for setup and cleanup when writing the stack in C.
Now, let's think about the StackInit() function. It will
need to set up a stack stackT structure, so that we have
an empty stack.
What does the prototype for StackInit() look like?
What do we do in its body?
Now, what about putting an element in the stack. What should the
prototype for StackPush() look like?
The steps needed to push an element onto the stack are:
- Allocate a new node.
- Put the element in the node.
- Link the element into the proper place in the list.
Let's fill in the body of StackPush().
Last, fill in the prototypes for the rest of the stack operations:
void StackInit(stackT *stackPtr);
return-type StackDestroy(parameters);
void StackPush(stackT *stackPtr,
stackElementT element);
return-type StackPop(parameters);
return-type StackIsEmpty(parameters);
Under some circumstances, you may be able to pass a stackT
and not need a pointer. We prefer to always pass a pointer so that
users call all stack functions in the same way.
-
Testing your implementation:
Here's a sample program stacktest.c and a Makefile for you to test your
stack module once you've filled it in.
The program demonstrates one use of the ordering produced by
a stack...What is it?
