I tried to edit the previous post but it seems I cant.
Thanks, I think I get what you're saying.
I made some changes and although the stack still holds elements of a Stack_Element type, that type itself is a void * so can point to anything. It also holds the item’s type. This was the main way I could think of to give a hint to the calling code as to the type of a popped off stack item – store the type field along with the data value.
Now client code doesn’t need to define a special stack value structure. They just create a generic Stack_Element item and stash whatever value in the void * slot, set the type field and then push onto the stack. And the macros are more to make the functions themselves easier to read. This is an exercise for me to make a stack as general as possible. I’m studying data structures.
Here's the revised code:
stack.h:
Code:
#ifndef __STACK_H__
#define __STACK_H__
/**
* stack.h: Definitions for a general stack type.
*/
#define STACK_MAX_ELEMENTS(S) (S->size - 1)
#define STACK_CURRENT_SIZE(S) (S->size * sizeof(Stack_Element *))
#define STACK_EXPAND_SIZED(S, N) \
(STACK_CURRENT_SIZE(S) + (N * sizeof(Stack_Element *)))
/**
* How many elements occupy the stack.
*/
#define STACK_N_ELEMENTS(S) ((S->size - (S->size - (S->top + 1))))
typedef enum Enum_Element_Type {
C_TYPE_INT,
C_TYPE_CHAR,
C_TYPE_FLOAT,
C_TYPE_DOUBLE,
C_TYPE_CHAR_ARRAY
} Enum_Element_Type;
typedef struct Stack_Element {
void *value; /* data value */
Enum_Element_Type type; /* data type */
} Stack_Element, *Stack_Element_POINTER;
typedef struct Stack {
int top; /* top of stack */
int size; /* number of possible elements */
int expand; /* size to grow by */
Stack_Element **data; /* stack elements */
} Stack, *Stack_POINTER;
int stack_empty(Stack *stack);
void echo_stack(Stack *stack);
void stack_wipe(Stack *stack);
Stack *stack_new(int size, int expand);
Stack *stack_expand(Stack *, int n_elements);
Stack_Element *stack_pop(Stack *stack);
Stack_Element *stack_peek(Stack *stack);
Stack_Element *stack_push(Stack *stack, Stack_Element *elt);
Stack_Element *stack_elm_new(void *value, Enum_Element_Type data_type);
#endif /* __STACK_H__ */
stack.c:
Code:
/**
* stack.c: Implementation of a general stack.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"
/**
* stack_new: Create a new stack.
*/
Stack *stack_new(int size, int expand) {
int i = 0;
Stack *stack = malloc(sizeof(Stack));
stack->top = -1;
stack->size = size;
stack->expand = (expand > 0 ? expand : 0);
stack->data = calloc(size, sizeof(Stack_Element *));
for (i = 0; i < stack->size; i++)
stack->data[i] = malloc(sizeof(Stack_Element));
return stack;
}
/**
* stack_elm_new: Create new stack element.
*/
Stack_Element *stack_elm_new(void *value, Enum_Element_Type type) {
Stack_Element *elm = malloc(sizeof(Stack_Element));
switch (type) {
case C_TYPE_INT:
elm->type = C_TYPE_INT;
break;
case C_TYPE_CHAR:
elm->type = C_TYPE_CHAR;
break;
case C_TYPE_FLOAT:
elm->type = C_TYPE_FLOAT;
break;
case C_TYPE_DOUBLE:
elm->type = C_TYPE_DOUBLE;
break;
case C_TYPE_CHAR_ARRAY:
elm->type = C_TYPE_CHAR_ARRAY;
break;
}
elm->value = value;
return elm;
}
/**
* echo_stack: Print the stack contents.
*/
void echo_stack(Stack *stack) {
int i = 0;
Stack_Element *elm = NULL;
printf("\nStack contents (%d):\n", STACK_N_ELEMENTS(stack));
while (!stack_empty(stack)) {
elm = stack_pop(stack);
switch (elm->type) {
case C_TYPE_INT:
printf("\t%d.) %d\n", i++, *((int *) elm->value));
break;
case C_TYPE_CHAR:
printf("\t%d.) %c\n", i++, *((char *) elm->value));
break;
case C_TYPE_FLOAT:
printf("\t%d.) %f\n", i++, *((float *) elm->value));
break;
case C_TYPE_DOUBLE:
printf("\t%d.) %g\n", i++, *((double *) elm->value));
break;
case C_TYPE_CHAR_ARRAY:
printf("\t%d.) %s", i++, (char *) elm->value);
break;
}
}
}
/**
* stack_empty: Check whether stack is empty.
*/
int stack_empty(Stack *stack) { return stack->top == -1; }
/**
* stack_pop: Remove top item from stack and return it.
*/
Stack_Element *stack_pop(Stack *stack) {
return (stack_empty(stack)) ? NULL : stack->data[stack->top--];
}
/**
* stack_peek: Preview item at the top of the stack.
*/
Stack_Element *stack_peek(Stack *stack) {
return (stack_empty(stack)) ? NULL : stack->data[stack->top];
}
/**
* stack_push: Push a stack element onto the stack.
*/
Stack_Element *stack_push(Stack *stack, Stack_Element *elm) {
if (stack->top == STACK_MAX_ELEMENTS(stack))
if (stack->expand)
stack = stack_expand(stack, stack->expand);
else
return NULL;
Stack_Element *top_elm = stack->data[++stack->top];
if (top_elm != NULL)
free(top_elm->value);
stack->data[stack->top] = elm;
return elm;
}
/**
* stack_expand: Expand the size of the stack.
*/
Stack *stack_expand(Stack *stack, int n_elms) {
stack->data = realloc(stack->data, STACK_EXPAND_SIZED(stack, n_elms));
stack->size = stack->size + n_elms;
return stack;
}
/**
* stack_wipe: Remove all stack elements and free their memory.
*/
void stack_wipe(Stack *stack) {
int n_elements = STACK_N_ELEMENTS(stack);
while (!stack_empty(stack))
free(stack_pop(stack));
memset(stack->data, 0, n_elements);
}
Test program:
Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"
int main(int argc, char *argv[]) {
int iter = 0;
int value = 76;
char character = 'C';
Stack *stack = stack_new(10, 3);
Stack_Element *elm = NULL;
char buf[256] = { 0 };
do {
printf("(ENTER) >>> ");
fflush(stdout);
fgets(buf, 256, stdin);
if (buf[0] == '\n') break;
elm = stack_elm_new(strdup(buf), C_TYPE_CHAR_ARRAY);
stack_push(stack, elm);
} while (1);
printf("\n");
printf("Pushing 76...\n");
stack_push(stack, stack_elm_new(&value, C_TYPE_INT));
printf("Pushing 'C'...\n");
stack_push(stack, stack_elm_new(&character, C_TYPE_CHAR));
echo_stack(stack);
printf("\nClearing the stack...\n");
stack_wipe(stack);
printf("\nStack has (%d) items.\n", STACK_N_ELEMENTS(stack));
return 0;
}
The output:
Code:
(ENTER) >>> text 1
(ENTER) >>> text 2
(ENTER) >>> text 3
(ENTER) >>> text 4
(ENTER) >>>
Pushing 76...
Pushing 'C'...
Stack contents (6):
0.) C
1.) 76
2.) text 4
3.) text 3
4.) text 2
5.) text 1
Clearing the stack...
Stack has (0) items.
Originally Posted by Bjarne Stroustrup (2000-10-14)
