The
LIFO Nature of Stacks
A
stack is a data structure analogous to stacks encountered in everyday
life. For example, consider a stack of books on a desk. One
may easily put a new book on top of the stack, and one may easily remove
the top book. Adding books to, or removing them from, the middle
of the stack may be perilous. In the stack data structure accessing
items in the middle is prohibited. Items may be added to or removed
from only the top of the stack.
Saving an
item on a stack is referred to as pushing the item, and retrieving an
item is called popping the item. Popping an item removes the item
from the stack. Pushes and pops are done at the top of the stack,
which may be thought of as a distinguished end of the stack. This
means that if two items are pushed and then one popped, the second one
pushed will be popped. This order of data access is called last
in, first out or LIFO access.
Reversing
with a Stack
Suppose
a sequence of items is presented and it is desired to reverse the sequence.
Various methods could be used and the beginning programmer usually will
suggest a solution using an array. A conceptually very simple solution,
however, is based on using a stack. The LIFO property of stack access
guarantees the reversal.
Suppose the
sequence ABCDEF is to be reversed. With a stack, one simply scans
the sequence, pushing each item on the stack as it is encountered, until
the end of the sequence is reached. Then the stack is popped repeatedly,
with each popped item sent to output, until the stack is empty.
The following illustrates this algorithm.
input ==>
ABCDEF
push A:
A <==
top of stack
input ==>
BCDEF
push B:
B <==
top of stack
A
input ==>
CDEF
push C:
C <==
top of stack
B
A
input ==>
DEF
push D:
D <==
top of stack
C
B
A
input ==>
EF
push E:
E <==
top of stack
D
C
B
A
input ==>
F
push F:
F <==
top of stack
E
D
C
B
A
The end of
the input has been reached, and so popping the stack begins.
pop F to
output:
E <==
top of stack
D
C
B
A
pop E to
output:
D <==
top of stack
C
B
A
pop D to
output:
C <==
top of stack
B
A
pop C to
output:
B <==
top of stack
A
pop B to
output:
A <==
top of stack
pop A to
output:
stack empty;
stop.
Stack
Operations
Besides the push and
pop operations on a stack, it is desirable to have at least two more:
an initialize operation, which prepares the stack for use and sets it
to an empty state, and an empty operation, which is simply a test to see
whether the stack is empty. The empty operation is useful to guard
against an attempt to pop an empty stack, which is an error. Ideally
stacks should be unlimited in capacity so that another item can always
be pushed no matter how many are already on the stack. However,
stacks as implemented on an actual computer will always have some finite
maximum capacity. Sometimes these stacks are referred to as stacks
with a roof. When the roof is reached, items can no longer be pushed
on the stack. In view of this fact, it is sometimes desirable to
supply a full operation for a stack.
Other stack operations may
be conceived, such as peek (examine the top item of the stack without
popping it), traverse (go through all the items on the stack, performing
some action for each item) and count (find the number of items on the
stack). Here, however, attention will be restricted to only the
five mentioned in the preceding paragraph.
Stack Operations
- push: add an item
to the top of the stack
- pop: remove an
item from the top of the stack
- empty: test whether the
stack is empty
- full: test whether
the stack is full
- initialize: set up the
stack in an empty condition
In C programs the above operations
are often implemented as functions to provide a degree of data hiding.
A program which uses stacks would access the stacks only through these
functions, and not be concerned with the inner workings of the stack.
It is also convenient to access a stack through a pointer. The pointer
can be considered a handle whereby the program can make use of the stack.
These techniques can provide implementation independent code, so that
a program using stacks would not need to be changed if the stack functions
themselves were changed. This will be illustrated in the following
two sections.
Contiguous
Implementation
A
contiguous implementation means that each stack item is adjacent in memory
to the next stack item, and so arrays are the natural structures for contiguous
implementations. For a contiguous stack implementation the stack
items are kept in an array and the top position in an integer field of
a structure which also contains the array. The stack will be accessed
through a handle which is a pointer to this structure. For flexibility
the type itemtype will be used in the code for stack items. Then
the actual type used in a program can simply be specified with a typedef.
The constant N is the maximum size of the stack and may be redefined to
a suitable value for different applications.
Reversing
an Input Line with a Contiguous Stack
#include
<stdio.h>
#include <stdlib.h>
#define N
80
typedef char
itemtype;
typedef struct{
int top;
itemtype items[N];} stackstruct;
typedef stackstruct
* stack;
stack initialize(stack
s){
s = (stack)malloc(sizeof(stackstruct));
s->top = -1;
return s;}
void push(stack
s, itemtype x){
s->items[++s->top] = x;}
itemtype
pop(stack s){
return s->items[s->top--];}
int empty(stack
s){
return s->top == -1;}
int full(stack
s){
return s->top == N-1;}
void main(){
stack s;
char c;
s = initialize(s);
while((c = getchar()) != '\n' && !full(s))
push(s, c);
while(!empty(s))
putchar(pop(s));
getchar();}
Input
palindromes
Output
semordnilap
Linked
Implementation
A stack can also be
implemented as a linked structure. In such an implementation the
stack consists of a sequence of nodes. Each node is a record (structure
in C) containing a data item and a pointer to the next node if one exists.
This pointer is called a link (to the next node). The first node
is considered to be the top of the stack, and will be pointed to by a pointer
called top. The last node is the bottom of the stack and its pointer
field is set to NULL. An empty stack will have top == NULL.
A linked stack with elements C, B, A in order (C on top) may be represented
as below, where \ denotes a NULL pointer.
__________
__________
_________
top ======> |__C__
|___| =====> |__B__ |___| =====> |__A__ |_\_|
Recall
that it is desirable for a program to access a stack through a handle.
To achieve this, we simply enclose the top field in a structure, and then
a pointer to this structure is the desired handle. It may seem strange
to have a structure with only one field, but this ensures that a program
can use a linked stack in exactly the same way it would use a contiguous
stack.
The memory
for each node is dynamically allocated on the heap using malloc.
So when an item is pushed, a node for it is created, and when an item
is popped, its node is freed (using free).
The following
program illustrates appropriate types and functions for a linked stack.
The main function below is identical to the main function above using
a contiguous stack. Note that the behavior of this program is the
same as the one for a contiguous stack, at least for input lines of 80
characters or less. This is because the same function names are
used for the linked stack operations and they provide the same functionality
for the linked stack as the previous ones do for the contiguous stack.
The only difference is that the capacity of a linked stack is generally
greater than a contiguous stack since a linked stack will not become full
until dynamic memory is exhausted.
Reversing
an Input Line with a Linked Stack
#include
<stdio.h>
#include <stdlib.h>
typedef char
itemtype;
typedef struct
node{
itemtype item;
struct node * next;} Node;
typedef struct
{Node * top;} stackstruct;
typedef stackstruct
* stack;
void push(stack
s, itemtype x){
Node * p = (Node*)malloc(sizeof(Node));
p->item = x;
p->next = s->top;
s->top = p;}
itemtype
pop(stack s){
Node * p = s->top;
itemtype x = p->item;
s->top = p->next;
free(p);
return x;}
int empty(stack
s){
return s->top==NULL;}
int full(stack
s){
Node * p = (Node*)malloc(sizeof(Node));
if(p == NULL) return 1;
else{ free(p);
return 0;}}
stack initialize(stack
s){
s = (stack)malloc(sizeof(stackstruct));
s->top = NULL;
return s;}
void main(){
stack s;
char c;
s = initialize(s);
while((c = getchar()) != '\n' && !full(s))
push(s, c);
while(!empty(s))
putchar(pop(s));
getchar();}
|
