A stack may be implemented using arrays with the following declarations:

typedef struct

{

whatever info;

}stackrecord;

typedef struct

{

stackrecord stackarray [LIMIT];

int top;

}stack;

stack s;

The definitions must be preceded by a typedef for "whatever." Let us assume LIMIT has been set in a define statement fixing the maximum number of items the stack can hold. Suppose 6, 45, 15, 32, and 18 were pushed onto the stack. Figure 4.8 illustrates the meaning attached to the declaration. Figure 4.8(a) is a conceptualization of the stack. Since 6 was the first entry on the stack, it is on the bottom. Likewise, 18 was the last entry, so it is on top. Figure 4.8(b) is the way the data is stored in the actual stack s. The stackarray holds the data and top contains an index to the current entry on the top of the stack. Although 6 is at the top of the array, it is the bottom stack entry; while 18 is at the bottom of the array, it is the top stack entry. Thus top has the value 4.

Addition or insertion of a new element to the stack will be accomplished by a function push. Removal or deletion of the current top stack element will be accomplished by a function pop. Executing push (&newrecord,&s) results in the contents of newrecord being placed on the stack as a new first element. A call to the function pop(&s,&value) causes the removal of the current top stack element, with value containing a copy of that value. A routine setstack sets the stack to empty so that it initially contains no entries.

pop(&s,&y);

pop(&s,&z);

push(&newrecord,&s);

If Figure 4.8 indicates the current stack, then Figure 4.9 shows the new situation after this execution. n

* Stack underflow* occurs when a program attempts to remove an element from an empty stack. It normally indicates either an error or the termination of a task.

It is also necessary to test the stack to determine whether or not it is empty. This may be accomplished by invoking a function empty, which will return the value *true* when the stack is empty and *false* otherwise.

These routines may be implemented as follows:

setstack (ps)

/* Initializes the stack s to empty */

stack *ps;

{

(*ps).top = -1;

}

empty (ps)

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

stack *ps;

{

return ((*ps).top == -1);

}

push (pnewrecord,ps)

/* Inserts the record newrecord

at the top of the stack s

*/

stackrecord *pnewrecord,

stack *ps;

{

if ((*ps).top == (LIMIT - 1))

overflow(ps);

else

{

(*ps).top = (*ps).top + 1;

(*ps).stackarray[(*ps).top].info =

(*pnewrecord).info;

}

}

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))

underflow(ps);

else

{

(*pvalue).info = (*ps).stackarray

[(*ps).top].info;

(*ps).top = (*ps).top - 1;

}

}

The procedures overflow and underflow are assumed to take appropriate action when they are invoked. Notice that the elements of the stack will be of "whatever" type. We have taken the liberty here of assuming that the C compiler being used allows the contents of one structure to be assigned to another. Otherwise, for example, the assignment

(*ps).stackarray[(*ps).top].info =

(*pnewrecord).info;

that occurs in push could not be used. Instead, each field of info would have to be individually assigned.

The implementation discussed so far applies when *records* are to be stored on the stack. Instead, if only the contents of *simple variables* of type such as int, float, char, or listpointer are to be stored, then the declarations and definitions of push and pop may be simplified, as follows.

typedef struct

{

whatever stackarray [LIMIT];

int top;

}stack;

push(value,ps)

/* Inserts the new value

at the top of the stack s

*/

whatever value;

stack *ps;

{

if((*ps).top == (LIMIT-1))

overflow(ps);

else

{

(*ps).top = (*ps).top + 1;

(*ps).stackarray[(*ps).top] = value;

}

}

pop(ps,pvalue)

/* Copies the contents of the top entry

of stack s into value and removes it

from the stack

*/

stack *ps;

whatever *pvalue;

{

if(empty(ps))

underflow(ps);

else

{

*pvalue = (*ps).stackarray[(*ps).top];

(*ps).top = (*ps).top - 1;

}

}

"Whatever" will, of course, be declared of type int, or float, etc. The same simplification can be made, when appropriate, to the implementations of Sections 4.5.2, 4.5.3, 4.7.1, 4.7.2, and 4.7.3.

An application of the stack to the nonrecursive towers of Section 4.4.1 follows. It illustrates the use of the stack and its treatment as a data abstraction.

#include <stdio.h>

#define LIMIT 50

typedef struct

{

int n;

int i;

int a;

int f;

}whatever;

typedef struct

{

whatever info;

}stackrecord;

typedef struct

{

stackrecord stackarray [LIMIT];

int top;

}stack;

setstack(ps)

/* Initializes the stack s to empty */

stack *ps;

{

(*ps).top = -1;

}

empty(ps)

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

stack *ps;

{

return((*ps).top == -1);

}

push(pnewrecord,ps)

/* Inserts the record newrecord

at the top of the stack s

*/

stackrecord *pnewrecord;

stack *ps;

{

if ((*ps).top == (LIMIT-1))

overflow(ps);

else

{

(*ps).top = (*ps).top + 1;

(*ps).stackarray[(*ps).top].info =

(*pnewrecord).info;

}

}

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))

underflow(ps);

else

{

(*pvalue).info =

(*ps).stackarray[(*ps).top].info;

(*ps).top = (*ps).top - 1;

}

}

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)

/*Moves the top n disks

from peg i to peg f

*/

int n,i,a,f;

{

stack s;

int done;

setstack(&s);

done = FALSE;

while(!done)

{

while (n > 1)

{

s_tack(n,i,a,f,&s);

setvar1(&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;

}