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.
Example 4.4
Suppose we execute
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. Stack overflow occurs when a program attempts to add an element to a full stack. Although, conceptually, the stack as a data structure has no limit, an actual implemented stack does have a limit. In the present implementation it is termed. LIMIT. Push and pop should test, respectively, for stack overflow and underflow and take appropriate action whenever these conditions occur. Such precautionary measures are an example of defensive programming.
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:
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
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.
"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.
The idea of functional modularity is to isolate or localize the code of a program that is invoked in a particular task, such as an operation on a data structure. The implementation of the stack data abstraction discussed so far has achieved this modularity, with respect to the push, pop, setstack, and empty operations on the stack, by embodying them in individual routines. Another kind of modularity may be achieved by placing the type definitions and the declarations of these operations together in one file. This will be discussed further in the next chapter.
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.
In review of the program, notice that it treates the stack as a data abstraction. The type definitions and function definitions for the stack are placed at the top of the program. The functions setvar, s_tack, and restore are not basic stack operations; they are used by towers. Thus they have been placed after towers. Similarly, towers has been placed after main. Also, s_tack and restore are dependent on the stack implementation, since they must know the structure of a stack record, which is, in turn, determined by the needs of towers for its scratchpad.
pop(&s,&y);
pop(&s,&z);
push(&newrecord,&s);
(a) The Stack Data Abstraction
(b) Array Implementation of the Stack
Figure 4.8 Stack before Insertion of a New Element
(a) The Stack Data Abstraction
(b) Array Implementation of the Stack
Figure 4.9 Stack after Insertion of a New Element
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;
}
}
(*ps).stackarray[(*ps).top].info =
(*pnewrecord).info;
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;
}
}
#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;
}