Wambui Karuga

A Generic Stack in C

The C Programming Language has a reputation of being small but powerful. Unlike C++, which is usually considered its superset, C does not provide built-in types as rich as stacks, vectors, queues, or sets. The built-in array type in C can however be extended to create custom data structures that emulate similar complex structures.

In this example, I’ll try to build a generic stack that can be used to hold different types of data when configured. In this example, I’ll build a generic stack using arrays, structs and unions that can hold an integer or double.
For starters, three structures are defined and declared as below:

  • enum types which is a configuration value that defines the type of element that is being saved in the stack.
  • union stacks - a union in C is a user-defined data type that can hold different types of variables in the same memory location. Unions can hold as many data types, but will only point to one of them at a specific time. In this example, union data can hold ints, doubles and strings (char **).
  • struct stack - this is the actual stack struct data type. Its members include an index named top that keeps track of the number of the top element in the stack, type which is an enum of the type of stack it currently is, and the struct element *stack which is a list of elements which holds the actual data.
typedef struct stack stack;
typedef union stacks stacks;

typedef enum stack_type {
} types;

struct element {
	union stacks {
		int integer;
		char string;
		double double;
	} data;

struct stack {
	int top;
	types type;
	struct element *stack;

To create the stack, we use a call to malloc to create a new stack element and then initialize its members:

stack *new = malloc(sizeof(*new));
new->top = TOP;
new->type = type;
new->stack = malloc(sizeof(*new->stack) * MAX_LEN);

stack->top is initialized to 0 to ensure that our new stack elements starts at index 0. stack->stack is created to be an array of MAX_LEN length to hold our stack’s data.

The push operation (add element to stack) utilizes stdarg.h which provides a number of macros for working with lists of unnamed arguments of unknown types and number. Using these macros, we can then manipulate the data union in our stack to hold the type of data we’re currently working with.
In the push operation, we define a list of arguments va_list args which will hold the list of arguments passed to the function. To initialized the list, the last argument to va_start is the last named argument in the function’s parameter list. This way, a call to va_arg returns the next argument passed to the function. For example in the following call:
push(integer, ints[i])
the last named argument will be the stack integer that holds integers and so the next call to va_args() will yield the value of ints[i]. We then cast this into the appropriate int type and store it in its place on the stack. The top variable is incremented for each element that is pushed on the stack.

case INT:
	stack->stack[stack->top++].data.integers = (int) va_arg(args, int);

For the pop operation (remove from stack and return), we utilized void pointers since they can be cast into any other pointer.
One of the arguments passed to the pop function is a void *element pointer that will hold the value of the popped element.

case INT:
	*((int *) element) = stack->stack[--stack->top].data.integers; 

We cast the void pointer to an int pointer, and then deference the obtained pointer and assigned to it to get the actual value of the element.
The top variable is decremented each time a value is popped from the stack.

Using these functions, we can get a semi-workable generic stack in C that can be created to hold different types specified during creation.