stack with objects of different type in c

Question

I want to design a stack that can contain objects of different type(int, float, double, or char). The type of the stack is decided depending upon the declaration. This can be easily achieved using c++, with the help of templates. I am wondering how it can be done in c, where there is no templates....? This is the basic definitions i have made:

#define STACKSIZE 100
#define INT 1
#define FLOAT 2
#define CHAR 3

struct stackelement{
    int etype;
    union {
      int ival;
      float fval;
      char cval;  
    } element;
};
struct stack{
    int top;
    struct stackelement items[STACKSIZE];
};

Using this definitions how can I declare a stack with a specific type, and how the push and pop operations will be implemented?

Answer 1

There are a few different approaches, here:

1. If you're looking simply to reuse code, and each individual program you write will only use a stack of a particular datatype, then in your "stack.h" file or equivalent, you can just:

   typedef int STACK_DATA;
   

   or similar, define all your functions in terms of STACK_DATA, and just change the typedef at compile time for each app.

2. For the long term, there's really no good reason why you shouldn't define several types, such as stack_int, stack_float, stack_char, or whatever, and just create typed stacks with functions such as stack_float_pop() or such. It's a little more typing, but it's clean.

3. You could use your union per your sample code, and still have individual functions such as stack_float_push() for your different data types.

4. You can make it completely general by using your union and employing variable argument functions. You have to pop elements through a pointer, and you lose some type-safety, but the advantages are that you only have to write one block of code, and you can store different types in the same stack, if you want to.

Single type in one stack

If you wanted to only store elements of one type in each stack, the following code will do it:

stack.h:

#ifndef PG_SAMPLES_AND_DEMOS_STACK_GENERIC_H
#define PG_SAMPLES_AND_DEMOS_STACK_GENERIC_H

#include <stdbool.h>

enum stack_type {
    STACK_CHAR,
    STACK_INT,
    STACK_LONG,
    STACK_FLOAT,
    STACK_DOUBLE,
    STACK_POINTER
};

typedef struct stack * Stack;

Stack stack_create(const size_t capacity, const enum stack_type type);
void stack_destroy(Stack stack);
void stack_push(Stack stack, ...);
void stack_pop(Stack stack, void * p);
bool stack_is_empty(Stack stack);

#endif      /*  PG_SAMPLES_AND_DEMOS_STACK_GENERIC_H  */

stack.c:

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "stack.h"

/*  Struct to contain stack element  */

struct stack_element {
    union {
        char val_c;
        int val_i;
        long val_l;
        float val_f;
        double val_d;
        void * val_p;
    } data;
};

/*  Struct to contain stack  */

struct stack {
    size_t top;
    size_t capacity;
    enum stack_type type;
    struct stack_element * elements;
};

/*  Creates and returns a new stack of specified type and capacity  */

struct stack * stack_create(const size_t capacity, const enum stack_type type)
{
    struct stack * new_stack = malloc(sizeof *new_stack);
    if ( !new_stack ) {
        perror("couldn't allocate memory for stack");
        exit(EXIT_FAILURE);
    }

    new_stack->capacity = capacity;
    new_stack->top = 0;
    new_stack->type = type;

    new_stack->elements = malloc(sizeof *new_stack->elements * capacity);
    if ( !new_stack->elements ) {
        free(new_stack);
        perror("couldn't allocate memory for stack elements");
        exit(EXIT_FAILURE);
    }

    return new_stack;
}

/*  Destroys a previously created stack  */

void stack_destroy(struct stack * stack)
{
    free(stack->elements);
    free(stack);
}

/*  Pushes an element onto the stack  */

void stack_push(struct stack * stack, ...)
{
    if ( stack->top == stack->capacity ) {
        fprintf(stderr, "Stack full!\n");
        exit(EXIT_FAILURE);
    }

    va_list ap;
    va_start(ap, stack);

    switch ( stack->type ) {
        case STACK_CHAR:
            stack->elements[stack->top++].data.val_c = (char) va_arg(ap, int);
            break;

        case STACK_INT:
            stack->elements[stack->top++].data.val_i = va_arg(ap, int);
            break;

        case STACK_LONG:
            stack->elements[stack->top++].data.val_l = va_arg(ap, long);
            break;

        case STACK_FLOAT:
            stack->elements[stack->top++].data.val_f = (float) va_arg(ap, double);
            break;

        case STACK_DOUBLE:
            stack->elements[stack->top++].data.val_d = va_arg(ap, double);
            break;

        case STACK_POINTER:
            stack->elements[stack->top++].data.val_p = va_arg(ap, void *);
            break;

        default:
            fprintf(stderr, "Unknown type in stack_push()\n");
            exit(EXIT_FAILURE);
    }

    va_end(ap);
}

/*  Pops an element from the stack  */

void stack_pop(struct stack * stack, void * p)
{
    if ( stack->top == 0 ) {
        fprintf(stderr, "Stack empty!\n");
        exit(EXIT_FAILURE);
    }

    switch ( stack->type ) {
        case STACK_CHAR:
            *((char *) p) = stack->elements[--stack->top].data.val_c;
            break;

        case STACK_INT:
            *((int *) p) = stack->elements[--stack->top].data.val_i;
            break;

        case STACK_LONG:
            *((long *) p) = stack->elements[--stack->top].data.val_l;
            break;

        case STACK_FLOAT:
            *((float *) p) = stack->elements[--stack->top].data.val_f;
            break;

        case STACK_DOUBLE:
            *((double *) p) = stack->elements[--stack->top].data.val_d;
            break;

        case STACK_POINTER:
            *((void **) p) = stack->elements[--stack->top].data.val_p;
            break;

        default:
            fprintf(stderr, "Unknown type in stack_pop()\n");
            exit(EXIT_FAILURE);
    }
}

/*  Returns true if the stack is empty  */

bool stack_is_empty(struct stack * stack) {
    return stack->top == 0;
}

and main.c:

#include <stdio.h>
#include "stack.h"

int main(void)
{
    /*  Create, push and pop with stack of type int  */

    Stack istk = stack_create(3, STACK_INT);

    stack_push(istk, 123);
    stack_push(istk, 456);
    stack_push(istk, 789);

    while ( !stack_is_empty(istk) ) {
        int i;
        stack_pop(istk, &i);
        printf("Popped int %d from stack.\n", i);
    }

    /*  Create, push and pop with stack of type long  */

    if ( sizeof(long) >= 8U ) {
        Stack lstk = stack_create(3, STACK_LONG);

        stack_push(lstk, 123000000000L);
        stack_push(lstk, 456000000000L);
        stack_push(lstk, 789000000000L);

        while ( !stack_is_empty(lstk) ) {
            long l;
            stack_pop(lstk, &l);
            printf("Popped long %ld from stack.\n", l);
        }

        stack_destroy(lstk);
    }

    /*  Create, push and pop with stack of type float  */

    Stack fstk = stack_create(3, STACK_FLOAT);

    stack_push(fstk, 1.23);
    stack_push(fstk, 4.56);
    stack_push(fstk, 7.89);

    while ( !stack_is_empty(fstk) ) {
        float f;
        stack_pop(fstk, &f);
        printf("Popped float %f from stack.\n", f);
    }

    /*  Create, push and pop with stack of type double  */

    Stack dstk = stack_create(3, STACK_DOUBLE);

    stack_push(dstk, 1.23);
    stack_push(dstk, 4.56);
    stack_push(dstk, 7.89);

    while ( !stack_is_empty(dstk) ) {
        double d;
        stack_pop(dstk, &d);
        printf("Popped double %f from stack.\n", d);
    }

    /*  Create, push and pop with stack of type void *  */

    Stack pstk = stack_create(3, STACK_POINTER);

    stack_push(pstk, (void *) &istk);
    stack_push(pstk, (void *) &fstk);
    stack_push(pstk, (void *) &dstk);

    while ( !stack_is_empty(pstk) ) {
        void * p;
        stack_pop(pstk, &p);
        printf("Popped pointer %p from stack.\n", p);
    }

    /*  Destroy stacks and exit  */

    stack_destroy(pstk);
    stack_destroy(dstk);
    stack_destroy(fstk);
    stack_destroy(istk);

    return 0;
}

with output:

paul@thoth:~/src/sandbox/stack_generic$ ./stack_generic
Popped int 789 from stack.
Popped int 456 from stack.
Popped int 123 from stack.
Popped long 789000000000 from stack.
Popped long 456000000000 from stack.
Popped long 123000000000 from stack.
Popped float 7.890000 from stack.
Popped float 4.560000 from stack.
Popped float 1.230000 from stack.
Popped double 7.890000 from stack.
Popped double 4.560000 from stack.
Popped double 1.230000 from stack.
Popped pointer 0x7fff4a1dc1d8 from stack.
Popped pointer 0x7fff4a1dc1e0 from stack.
Popped pointer 0x7fff4a1dc1e8 from stack.
paul@thoth:~/src/sandbox/stack_generic$ 

Multiple types in one stack

If you want to store multiple types in one stack, you have to pass the type of the element with each pop() and push() call.

stack.h:

#ifndef PG_SAMPLES_AND_DEMOS_STACK_MULTITYPE_H
#define PG_SAMPLES_AND_DEMOS_STACK_MULTITYPE_H

#include <stdbool.h>

enum stack_type {
    STACK_CHAR,
    STACK_INT,
    STACK_LONG,
    STACK_FLOAT,
    STACK_DOUBLE,
    STACK_POINTER
};

typedef struct stack * Stack;

Stack stack_create(const size_t capacity);
void stack_destroy(Stack stack);
void stack_push(Stack stack, const enum stack_type type, ...);
void stack_pop(Stack stack, void * p);
enum stack_type stack_type_peek(Stack stack);
bool stack_is_empty(Stack stack);

#endif      /*  PG_SAMPLES_AND_DEMOS_STACK_MULTITYPE_H  */

stack.c:

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "stack.h"

/*  Struct to contain stack element  */

struct stack_element {
    enum stack_type type;
    union {
        char val_c;
        int val_i;
        long val_l;
        float val_f;
        double val_d;
        void * val_p;
    } data;
};

/*  Struct to contain stack  */

struct stack {
    size_t top;
    size_t capacity;
    enum stack_type type;
    struct stack_element * elements;
};

/*  Creates and returns a new stack of specified type and capacity  */

struct stack * stack_create(const size_t capacity)
{
    struct stack * new_stack = malloc(sizeof *new_stack);
    if ( !new_stack ) {
        perror("couldn't allocate memory for stack");
        exit(EXIT_FAILURE);
    }

    new_stack->capacity = capacity;
    new_stack->top = 0;

    new_stack->elements = malloc(sizeof *new_stack->elements * capacity);
    if ( !new_stack->elements ) {
        free(new_stack);
        perror("couldn't allocate memory for stack elements");
        exit(EXIT_FAILURE);
    }

    return new_stack;
}

/*  Destroys a previously created stack  */

void stack_destroy(struct stack * stack)
{
    free(stack->elements);
    free(stack);
}

/*  Pushes an element onto the stack  */

void stack_push(struct stack * stack, const enum stack_type type, ...)
{
    if ( stack->top == stack->capacity ) {
        fprintf(stderr, "Stack full!\n");
        exit(EXIT_FAILURE);
    }

    va_list ap;
    va_start(ap, type);

    switch ( type ) {
        case STACK_CHAR:
            stack->elements[stack->top].data.val_c = (char) va_arg(ap, int);
            break;

        case STACK_INT:
            stack->elements[stack->top].data.val_i = va_arg(ap, int);
            break;

        case STACK_LONG:
            stack->elements[stack->top].data.val_l = va_arg(ap, long);
            break;

        case STACK_FLOAT:
            stack->elements[stack->top].data.val_f = (float) va_arg(ap, double);
            break;

        case STACK_DOUBLE:
            stack->elements[stack->top].data.val_d = va_arg(ap, double);
            break;

        case STACK_POINTER:
            stack->elements[stack->top].data.val_p = va_arg(ap, void *);
            break;

        default:
            fprintf(stderr, "Unknown type in stack_push()\n");
            exit(EXIT_FAILURE);
    }

    stack->elements[stack->top++].type = type;

    va_end(ap);
}

/*  Pops an element from the stack  */

void stack_pop(struct stack * stack, void * p)
{
    if ( stack->top == 0 ) {
        fprintf(stderr, "Stack empty!\n");
        exit(EXIT_FAILURE);
    }

    switch ( stack->elements[--stack->top].type ) {
        case STACK_CHAR:
            *((char *) p) = stack->elements[stack->top].data.val_c;
            break;

        case STACK_INT:
            *((int *) p) = stack->elements[stack->top].data.val_i;
            break;

        case STACK_LONG:
            *((long *) p) = stack->elements[stack->top].data.val_l;
            break;

        case STACK_FLOAT:
            *((float *) p) = stack->elements[stack->top].data.val_f;
            break;

        case STACK_DOUBLE:
            *((double *) p) = stack->elements[stack->top].data.val_d;
            break;

        case STACK_POINTER:
            *((void **) p) = stack->elements[stack->top].data.val_p;
            break;

        default:
            fprintf(stderr, "Unknown type in stack_pop()\n");
            exit(EXIT_FAILURE);
    }
}

/*  Returns the type of the top element on the stack  */

enum stack_type stack_type_peek(struct stack * stack)
{
    if ( stack->top == 0 ) {
        fprintf(stderr, "Stack empty!\n");
        exit(EXIT_FAILURE);
    }

    return stack->elements[stack->top - 1].type;
}

/*  Returns true if the stack is empty  */

bool stack_is_empty(struct stack * stack) {
    return stack->top == 0;
}

and a sample main.c:

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

int main(void)
{
    Stack stk = stack_create(5);

    stack_push(stk, STACK_CHAR, 'x');
    stack_push(stk, STACK_INT, 123);
    stack_push(stk, STACK_FLOAT, 4.56);
    stack_push(stk, STACK_DOUBLE, 7.89);
    stack_push(stk, STACK_POINTER, (void *) &stk);

    while ( !stack_is_empty(stk) ) {
        char c;
        int i;
        float f;
        double d;
        void * p;

        switch ( stack_type_peek(stk) ) {
            case STACK_CHAR:
                stack_pop(stk, &c);
                printf("Popped char '%c' from stack.\n", c);
                break;

            case STACK_INT:
                stack_pop(stk, &i);
                printf("Popped int %d from stack.\n", i);
                break;

            case STACK_FLOAT:
                stack_pop(stk, &f);
                printf("Popped float %f from stack.\n", f);
                break;

            case STACK_DOUBLE:
                stack_pop(stk, &d);
                printf("Popped double %f from stack.\n", d);
                break;

            case STACK_POINTER:
                stack_pop(stk, &p);
                printf("Popped pointer %p from stack.\n", p);
                break;

            default:
                fprintf(stderr, "Unknown type.\n");
                return EXIT_FAILURE;
        }
    }

    stack_destroy(stk);

    return 0;
}

with output:

paul@thoth:~/src/sandbox/stack_multitype$ ./stack_multitype
Popped pointer 0x7fff401ab528 from stack.
Popped double 7.890000 from stack.
Popped float 4.560000 from stack.
Popped int 123 from stack.
Popped char 'x' from stack.
paul@thoth:~/src/sandbox/stack_multitype$