4.5.3 List Implementation of the Stack with Records in Dynamic Memory

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.

>Comment

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;

{

>Comment

*ps = NULL;

}

empty(ps)

/* Returns true only if the stack s is empty */

stack *ps;

{

>Comment

return(*ps == NULL);

}

push(pnewrecord,ps)

/* Inserts the record newrecord

at the top of the stack s

*/

stackrecord *pnewrecord;

stack *ps;

{

stackrecord *newentry;

>Comment

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;

{

>Comment

if(!empty(ps))

{

>Comment

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.

>Comment

#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");

}

>Comment

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;

}

>Comment

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;

{

>Comment

stackrecord newrecord;

newrecord.info.n = n;

newrecord.info.i = i;

newrecord.info.a = a;

newrecord.info.f = f;

push(&newrecord,ps);

}

>Comment

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].