The third stack implementation is also as a list梠ne that involves dynamic storage allocation of the records. That is, the records are stored in the storage area set aside by C to store records referenced by pointer variables. First, the following declaration must be made.
typedef struct record
{
struct whatever info;
struct record *link;
}stackrecord,*stack;
If we then define s as type stack, code can be written that is independent of its implementation. Setstack must initialize the stack to empty. This means setting s, the head of the list implementing the stack, to null. Push must now use malloc to allocate storage for the entry to be pushed onto the stack before setting its info field and inserting that record as the new first record on the stack. Pop must copy the info field value of the top record into value and then delete that record from the stack.
These stack operations are implemented as follows.
setstack(ps)
/* Initializes the stack s to empty */
stack *ps;
{
*ps = NULL;
}
empty(ps)
/* Returns true only if the stack s is empty */
stack *ps;
{
return(*ps == NULL);
}
push(pnewrecord,ps)
/* Inserts the record newrecord
at the top of the stack s
*/
stackrecord *pnewrecord;
stack *ps;
{
stackrecord *newentry;
newentry = malloc(sizeof(stackrecord));
newentry->info = pnewrecord->info;
newentry->link = *ps;
*ps = newentry;
}
pop(ps,pvalue)
/* Copies the contents of the top record
of stack s into value and removes the
record from the stack
*/
stack *ps;
stackrecord *pvalue;
{
if(!empty(ps))
{
pvalue->info = (*ps)->info;
*ps = (*ps)->link;
}
else
underflow(ps);
}
Notice that this implementation removes the artificial restriction imposed by LIMIT in the first implementation using an array. This is one of the advantages of using dynamic allocation by means of pointer variables.
It is very important to see that no matter what the implementation, as long as the stack is treated as a data abstraction when writing programs, the programs need not be changed, even if the programmer decides to change the implementation of the stack. Only the declarations and definitions related to the stack need be changed, as is evident in the following nonrecursive towers that uses the list implementation. It should be compared to the program of Section 4.5.1, in which the stack was implemented using an array.
#include <stdio.h>
#define NULL 0
typedef struct
{
int n;
int i;
int a;
int f;
}whatever;
typedef struct record
{
whatever info;
struct record *link;
}stackrecord, *stack;
setstack(ps)
/* Initializes the stack s to empty */
stack *ps;
{
*ps = NULL;
}
empty(ps)
stack *ps;
{
return(*ps == NULL);
}
push(pnewrecord,ps)
stackrecord *pnewrecord;
stack *ps;
{
stackrecord *newentry;
newentry = malloc(sizeof(stackrecord));
newentry->info = pnewrecord->info;
newentry->link = *ps;
*ps = newentry;
}
pop(ps,pvalue)
/* Copies the contents of the top record
of stack s into value and removes the
record from the stack
*/
stack *ps;
stackrecord *pvalue;
{
if(!empty(ps))
{
pvalue->info = (*ps)->info;
*ps = (*ps)->link;
}
else
underflow(ps);
}
overflow(ps);
/* Prints a message that the stack has overflowed */
stack *ps;
{
printf(" The stack has overflowed \n");
}
underflow(ps);
/* Prints a message that the stack has underflowed */
stack *ps;
{
printf(" The stack has underflowed \n");
}
main()
/* Driver for towers */
{
int n;
printf("\n enter a value for n \n");
scanf("%d",&n);
towers(n,1,2,3);
}
towers(n,i,a,f)
1 final nonrecursive version
/* Moves the top n disks
from peg i to peg f
*/
int n,i,a,f;
{
stack s;
1 allocates storage for s (an instance of type stack)
int done
setstack(&s);
done = FALSE;
while(!done)
{
while (n > 1)
{
s_tack(n,i,a,f,&s);
setvar 1(&n,&i,&a,&f);
}
printf("\n %d -> %d\n",i,f);
if(!empty(&s))
{
restore(&n,&i,&a,&f,&s);
printf("\n %d -> %d\n",i,f);
setvar2(&n,&i,&a,&f);
}
else
done = TRUE;
}
setvar1(pn,pi,pa,pf)
/* Sets n to n - 1 and
interchanges f and a
*/
int *pn,*pi,*pa,*pf;
{
int t;
*pn = *pn - 1;
t = *pf;
*pf = *pa;
*pa = t;
}
setvar2(pn,pi,pa,pf)
/* Sets n to n - 1 and
interchanges a and i
*/
int *pn,*pi,*pa,*pf;
{
int t;
*pn = *pn - 1;
t = *pa;
*pa = *pi;
*pi = t;
}
s_tack(n,i,a,f,ps)
/* Creates a record containing
n, i, a, and f and inserts it
on stack s
*/
int n,i,a,f;
stack *ps;
{
stackrecord newrecord;
newrecord.info.n = n;
newrecord.info.i = i;
newrecord.info.a = a;
newrecord.info.f = f;
push(&newrecord,ps);
}
restore(pn,pi,pa,pf,ps)
/* Removes the top record from
stack s and copies its contents
into n,i,a,f
*/
int *pn,*pi,*pa,*pf;
stack *ps;
{
stackrecord value;
pop(ps,&value);
*pn = value.info.n;
*pi = value.info.i;
*pa = value.info.a
*pf = value.info.f;
}
The problem of implementing many stacks simultaneously is introduced in the suggested assignment at the end of this chapter. More sophisticated algorithms for the management of the stacks are explored in Garwick [1964], Knuth [1973], and Korsh [1983].