Having many stacks with different types

Question

I'm making a C program that needs to use two stacks. One needs to hold chars, the other needs to hold doubles. I have two structs, node and stack:

struct node {
    double value;
    struct node *next;
    struct node *prev;
};

struct stack {
    struct node *last;
    struct node *curr;
};

The problem is that I need one of each type. The only thing I can think of is having two separate structs (i.e., char_node, double_node, char_stack, double_stack). If this were C++ I'd use templates, but of course I can't in C.

One thing I remember that could be used for this is a void pointer. Would that work, and would it be practical?

Answer 1

You could use a union.

Here some info on unions.

Answer 2

Why not use a union?

struct node {
    union {
       double d_value;
       char c_value;
    } val;
    struct node *next;
    struct node *prev;
};

Answer 3

OK, but node structure you show seems to belong to double linked list, not a stack. Are you really thinking about stacking? Chains of linked nodes you show being allocated dynamically will eat your memory in a moment.

I'd recommend you to reconsider base design of this. You should use memory more effective (maybe I don't know something about your special conditions but this is general approach. This really could lead to 2 separate stacks for objects of different type to keep data alignment (you won't like 1 byte chars mixed with 4 byte longs for example in plain memory area).

But this is only my opinion based on my experience with this, may it is useful in your situation ;).

Answer 4

1. If you really want to use a linked list as a stack you do not need next and prev, just next. Neither do you need a tail/head pointer ('last' in the example code). On a stack you only ever care about the top element.

2. If you are implementing a stack to hold types like char and double, why not declare an array of each type and hold a pointer to the last valid element in the array? Then when you want to push onto the array you increment the pointer and set the value. To pop you do the reverse: get the value and decrement the pointer. Using an array means allocating all the memory you are likely to need in one fell swoop rather than every time you want to push a new node onto the stack.

Answer 5

If each stack only needs to hold a single data type, unions and void pointers are overkill. Make a DoubleStackNode and a CharStackNode -- this is what a C++ template (i.e. StackNode<T>) would do behind the scenes anyway.

Don't kill yourself trying to make some super-general catch-all solution. You only need two types of stacks.

You could use a union, but doing so will add substantial space overhead to your char stack.