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?

Do you want to use the same stack type for all element types? Shall a stack be able to conatin different element types? With your current approach, both is possible, but both is different to C++ templates (the types are resolved at run-time). To get compile-time types equivalent to templates, you need to use the preprocessor or code generation. And beside that, I don't see where you get stuck. It's not really different than any other stack. — mafso
– mafso, Commented Nov 2, 2014 at 13:05
That's hard to do when I don't know where your problems are... — mafso
– mafso, Commented Nov 2, 2014 at 13:28
@BasileStarynkevitch: Templates were mentioned in the post, I just asked for clarification if OP wanted something equivalent or wanted to move on with the different approach already shown. (That the accepted answer has been accepted and the comments here seem to contradict each other, though...) — mafso
– mafso, Commented Nov 2, 2014 at 14:57

Crowman · Accepted Answer · 2014-11-02 18:15:11Z

There are a few different approaches, here:

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.
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.
You could use your union per your sample code, and still have individual functions such as stack_float_push() for your different data types.
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$

For a stack containing different types (as the OP asked), how would you check the type to be popped before popping? Inspect the type of stack[top-1]? Your sample code assumes the order of types pushed is known and then rolled back in reverse, which may not be true (I'm thinking of PostScript, for example).
@Jongware: As I mentioned (in an edit, so you might have commented before I did that) if you stored the type in the element itself, it would be easy enough to write a routine to peek at it. Give me a sec, I'll write it up.
@Jongware: Updated. I changed the stack_pop() functions too, since we're using pointers there and only the stack_push() functions actually need to use variable arguments.

5gon12eder · Accepted Answer · 2014-11-02 13:29:48Z

In such simple cases, you can fake templates with some macro magic. For example, you can put this into a file poly_stack.h

/* No include guards here! */

#define CONCAT_NAME_R(A, B, C) A ## B ## C
#define CONCAT_NAME(A, T) CONCAT_NAME_R(A, _, T)

struct CONCAT_NAME(stack, VALUE_TYPE)
{
  VALUE_TYPE top;
  VALUE_TYPE items[STACKSIZE];
};

and then use

#define VALUE_TYPE int
#include poly_stack.h
#undef VALUE_TYPE

To make this work, you'll need to define all your stack operations inline inside the header file.

I don't consider this a very elegant solution. Of course, you can always resort to external code generation using tools like sed or awk for the same purpose.

Finally, you can use run-time polymorphism and declare

struct poly_stack
{
  void * top;
  void * items[STACKSIZE];
};

but compared to the “templated” solution, this is inferior with respect to both, type safety and performance. And it is also much less convenient to use.

Ramin · Accepted Answer · 2018-09-25 05:07:02Z

0

There is another simple way which uses a union of different stack data structures. This method has less restrictions and easy to use.

#include <stdio.h>

#define SZ (20)

union stack_s
{
    struct stack_int
    {
        int top;
        int arr[SZ];
    }istack;

    struct stack_char
    {
        char top;
        char arr[SZ];
    }cstack;

    struct stack_float
    {
        float top;
        float arr[SZ];
    }fstack;
};

void main(void)
{
union stack_s stack_elm;

stack_elm.istack.arr[0] = 0x1234;
printf("stack of integers = %x\n",stack_elm.istack.arr[0]);

stack_elm.cstack.arr[0] = 'A';
printf("stack of chars = %c\n",stack_elm.cstack.arr[0]);

return;
}

and the output is as below:

stack of integers = 1234

stack of chars = A

edited Sep 25, 2018 at 5:07

answered Sep 25, 2018 at 4:48

Ramin

12 bronze badges

Comments

Batuhan Tasdoven · Accepted Answer · 2014-11-02 13:03:43Z

-1

What a compiler does in the template scenario is to create different signatures of that function with the data types that are used in the code.

For example, if you have a method template<class T> void setValue(T value)

and if you are using this method in your code as:

setValue<float>(3.5f);
setValue<int>(7);

Then actually what you will end up with is 2 signatures of the same function:

void setValue(float value)
void setValue(int value)

Therefore, you can write different push and pop methods for each value type. For example:

void push(int val) {
    //some malloc operations
    items[top].ival = val;
}

void push(float val) {
    //some malloc operations
    items[top].fval = val;
}

answered Nov 2, 2014 at 13:03

Batuhan Tasdoven

7987 silver badges19 bronze badges

1 Comment

Crowman Over a year ago

He's asking how to do this in C, so an answer requiring C++ is unhelpful.

Collectives™ on Stack Overflow

stack with objects of different type in c

4 Answers 4

Single type in one stack

Multiple types in one stack

3 Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Single type in one stack

Multiple types in one stack

3 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related