I have one complaint about these specifications and the implementations on pages 83-87. The preconditions for all but the CreateStack function require that "the stack exists and it has been initialized." That's good, but in practice, programmers are prone to ignoring this sort of requirement. I would like the specifications to include error-reporting, and the implementations to protect themselves against dereferencing null pointers. (The implementations in the book do in fact protect against and report errors, but I prefer moving the responsibility of how to respond to errors into the caller rather than leaving that decision up to the stack library.)
Unfortunately, it's hard to design an elegant interface that includes easy-to-use error reporting as well as natural return values. The easiest way to report errors is to have each function return a boolean value that is true if there were no errors, and false otherwise. Unfortunately, this means that functions like StackSize and StackEmpty, which have natural uses for the return value already, can't report errors in the same way as the other functions.
I propose the following solution for this particular set of specifications. For the info-reporting functions StackEmpty, StackFull, and StackSize, we'll return default values if there is an error (false for StackFull and StackEmpty, and 0 for StackSize). For all of the other functions, whose specifications in the textbook are void-valued, we'll return true or false, depending on whether an error occurred.
The errors your implementations need to guard against are (1) the parameter s is NULL for any of the functions, (2) Push is called when the stack is full, (3) Pop is called when the stack is empty, and (4) malloc returns a null pointer (in a linked implementation).
typedef int boolean;
/* Your routines should work for any choice of
definition of StackEntry, but please use char
to simplify the grader's job. */
typedef char StackEntry;
boolean CreateStack( Stack *s );
/* precondition: The Stack pointer s is NULL or points
to a variable of type Stack.
postcondition: Returns true if s is non-NULL and
creation succeeded, false otherwise. If s is
non-NULL, the stack has been initialized to be empty. */
boolean StackEmpty( Stack *s );
/* precondition: The Stack pointer s is NULL or points
to a variable of type Stack for which CreateStack
has been called.
postcondition: Returns true if s is non-NULL and the
stack is empty, false otherwise. */
boolean StackFull( Stack *s );
/* precondition: The Stack pointer s is NULL or points
to a variable of type Stack for which CreateStack
has been called.
postcondition: Returns true if s is non-NULL and the
stack is full, false otherwise. */
boolean Push( StackEntry item, Stack *s );
/* precondition: The Stack pointer s is NULL or points
to a variable of type Stack for which CreateStack
has been called.
postcondition: Returns true if s is non-NULL, the
stack was not full before the Push, and the Push
succeeded, false otherwise. If return value is true
(that is, the Push succeeded), the item has been
stored at the top of the stack. */
boolean Pop( StackEntry *item, Stack *s );
/* precondition: The Stack pointer s is NULL or points
to a variable of type Stack for which CreateStack
has been called.
postcondition: Returns true if s is non-NULL, the
stack was not empty before the Pop, and the Pop
succeeds, false otherwise. If return value is true
(that is, the Pop succeeded), the top element of
the stack has been removed and stored in *item. */
boolean ClearStack( Stack *s );
/* precondition: The Stack pointer s is NULL or points
to a variable of type Stack for which CreateStack
has been called.
postcondition: Returns true if s is non-NULL and
the deletion of previous contents succeeded, false
otherwise. If return value is true (that is, the
ClearStack succeeded), all entries in the stack have
been deleted, and the stack is now empty. */
int StackSize( Stack *s );
/* precondition: The Stack pointer s is NULL or points
to a variable of type Stack for which CreateStack
has been called.
postcondition: Returns the number of elements in the
stack if s is non-NULL, 0 otherwise. */
boolean StackTop( StackEntry *item, Stack *s );
/* precondition: The Stack pointer s is NULL or points
to a variable of type Stack for which CreateStack
has been called.
postcondition: Returns true if s is non-NULL and the
stack was not empty before the call to StackTop,
false otherwise. If return value is true, the
stack is unchanged, but a copy of its top element
is stored in *item. */
boolean TraverseStack( Stack *s, void (*Visit)() );
/* DON'T DO THIS ONE. Instead, you might want to write
yourself a void PrintStack( Stack *s ) for debugging
purposes. */
To help out the grader, please define StackEntry as a char.
Your first implementation, using an array, is almost done already on pages 83-85.
The second implementation is begun on pages 85-87.
Hand in two source files (stackarray.c and stacklinked.c) and their corresponding headers. Do not hand in a main program.
When you test your implementations, a single main program should work for both implementations. All you should need to change in main.c to test the second implementation instead of the first is change #include "stackarray.h" to #include "stacklinked.h".
Questions? Talk to me.
Start early, keep in touch, and
have fun.