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); #endifWe 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; }