Conceptually, a stack contains elements that are inserted by the push operation, and deleted by the pop operation in the opposite order that they were inserted. In other words, the first element to be deleted is the last one inserted. The top operation returns the last element inserted without affecting the contents of the stack. Finally, the empty operation is a predicate to test whether the stack has zero elements.
l = cons(element, l);The implementation of empty is particularly simple:
return l == NULL;or simply:
return !l;For the implementation of pop we need to check that the stack is not empty before attempting to remove the top element. Here is the code:
assert(!empty(l));
{
list temp = l;
l = l -> next;
free(temp);
}
If we have a garbage
collector, we can do even better, like this:
assert(!empty(l)); l = l -> next;Finally, for the top operation, we also need to check whether the stack is empty before attempting the operation:
assert(!empty(l)); return l -> element;
Here is the header file:
#ifndef STACK_H
#define STACK_H
struct stack;
typedef struct stack *stack;
/* create a new, empty stack */
extern stack stack_create(void);
/* push a new element on top of the stack */
extern void stack_push(stack s, void *element);
/* pop the top element from the stack. The stack must not be
empty. */
extern void stack_pop(stack s);
/* return the top element of the stack */
extern void *stack_top(stack s);
/* return a true value if and only if the stack is empty */
extern int stack_empty(stack s);
#endif
We have added comments describing briefly what the module does, and
describing what each interface function does. The phrases must
be and must not be mean that a program that does not
respect what these phrases say, is a program with errors in it. This
module is therefore free to do whatever it thinks reasonable
(including nothing at all) when such a condition is violated. In our
implementation, we will call assert and abort the
execution of the program. For the implementation, we use a header object:
#include "stack.h"
#include "list.h"
#include < assert.h>
#include < stdlib.h>
typedef struct stack *stack;
struct stack
{
list elements;
};
stack
stack_create(void)
{
stack temp = malloc(sizeof(struct stack));
temp -> elements = NULL;
return temp;
}
void
stack_push(stack s, void *element)
{
s -> elements = cons(element, s -> elements);
}
int
stack_empty(stack s)
{
return s -> elements == NULL;
}
void
stack_pop(stack s)
{
assert(!empty(s));
s -> elements = cdr_and_free(s -> elements);
}
void *
stack_top(stack s)
{
assert(!empty(s));
return s -> elements -> element;
}