Thread: HELP: Stack of Different Variable Types

I need the stack below to take in arguments for both char arrays and ints. I am trully lost as to how to make this work though! I have seen a suggestion to try using a union but I am absolutely lost as to how to make this work with my code. Can anyone assist me?

Code:

typedef struct Stack
{
    int capacity;            // max # of elements the stack can hold      
    int size;           // current size of the stack
    int *elements;      // the array of elements
}Stack;

Stack * createStack(int maxElements)
{        
    Stack *S;        
    S = (Stack *)malloc(sizeof(Stack));     
    S->elements = (int *)malloc(sizeof(int)*maxElements);        
    S->size = 0;        
    S->capacity = maxElements;      
    return S;
}


// STACK COMMANDS
void pop(Stack *S)
{               
     if(S->size==0)        
     {                    
          printf("Stack is Empty\n");                
          return;        
     }        
     else        
     {                    
         S->size--;        
     }        
     return;
}

int top(Stack *S)
{        
     if(S->size==0)        
     {                    
          printf("Stack is Empty\n");                   
          exit(0);        
     }               
     return S->elements[S->size-1];
}

void push(Stack *S,int element)
{                
    if(S->size == S->capacity)        
    {                    
         printf("Stack is Full\n");        
    }        
    else        
    {                                   
         S->elements[S->size++] = element;        
    }        
    return;
}

Define your question "I need the stack below to take in arguments for both char arrays and ints" a little more.

Basically right now, the stack only allows me to push (and pop) on integer variables. I need to push both integer variables and char arrays (strings). Is there a way for me to format my stack to allow this sort of implementation?

make each entry of your stack a void * and a variable identifying the type. Create push_char_array and push_int functions - each mallocs space for the appropriate var, copies it into this space, points the void * to it and sets the type ID correctly. Create corresponding pop_char_array and pop_int functions which do the reverse. Figure out what happens if you call pop_char_array and the top of the stack is an int and vice versa.

You could instead use a union of a char pointer and int as your stack element which would save some malloc/freeing for the int case.

Or better yet, ask yourself why not use two different stacks, one for ints and one for char arrays.

Here's one way to do it:

Code:

#include <stdlib.h>
#include <errno.h>

enum element_type {
    UNUSED = 0,
    DOUBLE,
    FLOAT,
    LONG,
    INT,
    CHAR_PTR
};

struct stack_element {
    enum element_type     type;
    union element_value {
        double            double_value;
        float             float_value;
        long              long_value;
        int               int_value;
        char             *char_ptr;
    }                     value;
};

struct stack {
    size_t                size;
    size_t                used;
    struct stack_element *element;
};

typedef struct stack      stack_t;


/* Initialize a new stack. Returns 0 if success, errno otherwise.
*/
int stack_init(stack_t *const stack, const size_t size)
{
    /* NULL pointer? Invalid size? */
    if (!stack || size < 1)
        return errno = EINVAL;

    stack->size    = 0;
    stack->used    = 0;
    stack->element = malloc(size * sizeof (*stack->element));
    if (!stack->element)
        return errno = ENOMEM;

    stack->size = size;
    return 0;
}

/* Discard a stack.
*/
int stack_free(stack_t *const stack)
{
    free(stack->element);
    stack->size = 0;
    stack->used = 0;
    stack->element = NULL;
    return 0;
}

/* Helper: Return the type of the item at 'i' from the top of the stack.
*/
enum element_type stack_typeof(const stack_t *const stack, const size_t i)
{
    if (!stack || i >= stack->used)
        return UNUSED;
    else
        return stack->element[stack->used - 1 - i].type;
}

/* Stack push helper. Automatically grows the stack if needed.
*/
static inline int stack_push_any(stack_t *const stack, const struct stack_element element)
{
    if (!stack)
        return errno = EINVAL;
    else
    if (stack->used >= stack->size) {
        const size_t  temp_size = (stack->used + 13) * 5 / 4;
        struct stack_element *temp;

        temp = realloc(stack->element, temp_size * sizeof (*stack->element));
        if (!temp)
            return errno = ENOMEM;

        stack->size = temp_size;
        stack->element = temp;
    }

    stack->element[stack->used].type = element.type;
    stack->element[stack->used].value = element.value;
    stack->used++;

    return 0;
}

/* Stack pop helper.
 * To pop any type, set element->type = UNUSED first,
 * otherwise only that type element will be popped.
*/
static inline int stack_pop_any(stack_t *const stack, struct stack_element *const element)
{
    if (!stack)
        return errno = EINVAL;
    else
    if (stack->used < 1)
        return errno = ENOENT; /* Stack is empty, nothing to pop. */

    if (element) {

        /* Wrong type? */
        if (element->type != UNUSED &&
            stack->element[stack->used - 1].type != element->type)
            return errno = EMEDIUMTYPE;

        element->value = stack->element[stack->used - 1].value;
    }

    stack->used--;

    return 0;
}

/*
 * Pushers. Return 0 if success, errno otherwise.
*/

int stack_push_double(stack_t *const stack, const double value) {
    struct stack_element  element;
    element.type = DOUBLE;
    element.value.double_value = value;
    return stack_push_any(stack, element);
}

int stack_push_float(stack_t *const stack, const float value) {
    struct stack_element  element;
    element.type = FLOAT;
    element.value.float_value = value;
    return stack_push_any(stack, element);
}

int stack_push_long(stack_t *const stack, const long value) {
    struct stack_element  element;
    element.type = LONG;
    element.value.long_value = value;
    return stack_push_any(stack, element);
}

int stack_push_int(stack_t *const stack, const int value) {
    struct stack_element  element;
    element.type = INT;
    element.value.int_value = value;
    return stack_push_any(stack, element);
}

int stack_push_char_ptr(stack_t *const stack, char *const value) {
    struct stack_element  element;
    element.type = CHAR_PTR;
    element.value.char_ptr = value;
    return stack_push_any(stack, element);
}

/*
 * Poppers. Return 0 if success, errno otherwise.
 * Value pointer may be NULL, but the type is still enforced.
 * (To discard the top of stack, use stack_pop_any(stack, NULL).)
*/

int stack_pop_double(stack_t *const stack, double *const valueptr)
{
    struct stack_element  element;
    element.type = DOUBLE;
    if (stack_pop_any(stack, &element))
        return errno;
    if (valueptr)
        *valueptr = element.value.double_value;
    return 0;
}

int stack_pop_float(stack_t *const stack, float *const valueptr)
{
    struct stack_element  element;
    element.type = FLOAT;
    if (stack_pop_any(stack, &element))
        return errno;
    if (valueptr)
        *valueptr = element.value.float_value;
    return 0;
}

int stack_pop_long(stack_t *const stack, long *const valueptr)
{
    struct stack_element  element;
    element.type = LONG;
    if (stack_pop_any(stack, &element))
        return errno;
    if (valueptr)
        *valueptr = element.value.long_value;
    return 0;
}

int stack_pop_int(stack_t *const stack, int *const valueptr)
{
    struct stack_element  element;
    element.type = INT;
    if (stack_pop_any(stack, &element))
        return errno;
    if (valueptr)
        *valueptr = element.value.int_value;
    return 0;
}

int stack_pop_char_ptr(stack_t *const stack, char **const valueptr)
{
    struct stack_element  element;
    element.type = CHAR_PTR;
    if (stack_pop_any(stack, &element))
        return errno;
    if (valueptr)
        *valueptr = element.value.char_ptr;
    return 0;
}

The struct element structure is a structure that holds a typed value. The structure is always the same size, large enough to contain its largest union member, but the types I listed there are all just four to eight bytes, so the memory use would be no issue. (C library internal structures are definitely larger, if you were to allocate each value separately.)

The union holds the value. Each of the union members are stored in the same memory locations, so you can only use one member at a time. The C standards also state that you must use the same member to read the value as you used to store it. (If you don't, compilers may do funny decisions about optimization, giving you bogus results.)

The stack_init() and stack_free() are quite straightforward, nothing strange there.

The actual work when pushing anything onto the stack is done in stack_push_any(). The other stack_push_type() are just wrappers that call it with a suitably prepared structure; they're usually easier to use. Note that the stack will be dynamically grown when necessary, and that I'm being very careful about checking the function parameters. (They're easier to remove if they prove to be a slowdown in profiling, but they're certainly useful when writing and testing.)

Before popping anything off the stack, you can use the stack_typeat() to check the type, relative to the top of stack (0 being top, 1 being below that, and so on).

The real work for popping off the stack is done in stack_pop_any(). Note that you can supply a NULL element pointer to it, in which case the top of the stack is just discarded. If you do supply a pointer to a stack element, the type matters: if the type field in the pointed-to element is UNUSED, then the top of the stack is popped; otherwise, it is popped only if the types match. The stack_pop_type() helper functions use that feature to pop the top of the stack only if the type matches.

I didn't want to make it too easy to just take the code and use it as-is; I hope you have to first look at and understand what the code does before you can use it. Consider it an example only.

That said, if you have any specific questions on why the code does what it does, I'd be happy to elaborate.

This is a common form of polymorphism in C. Another example of polymorphism is with the sockaddr structures in POSIX (see <netinet/in.h> and <sys/socket.h>):

Code:

struct sockaddr {
    sa_family_t  sa_family  // Address family. 
    char         sa_data[]  // Socket address (variable-length data). 
};

// IPv4 (AF_INET) socket address
struct sockaddr_in {
    sa_family_t     sin_family   // AF_INET. 
    in_port_t       sin_port     // Port number. 
    struct in_addr  sin_addr     // IP address.
};

// IPv6 (AF_INET6) socket address
struct sockaddr_in6 {
    sa_family_t      sin6_family    // AF_INET6. 
    in_port_t        sin6_port      // Port number. 
    uint32_t         sin6_flowinfo  // IPv6 traffic class and flow information. 
    struct in6_addr  sin6_addr      // IPv6 address. 
    uint32_t         sin6_scope_id  // Set of interfaces for a scope. 
};

sockaddr_in and sockaddr_in6 are child classes of the sockaddr parent class. The first member is always one of type sa_family_t (the actual name doesn't matter), so any code that takes a pointer to struct sockaddr knows what address family it belongs to and therefore what type it is (sockaddr_in if sa_family == AF_INET or sockaddr_in6 if sa_family == AF_INET6).

(Some object-oriented languages automatically store a hidden member in each object that contains information about the type of the object. This code (sockaddr) and the code that Nominal Animal posted is basically the same thing but it puts an explicit type field in the structures because C doesn't natively support OOP).