Thread: General Stack Implementation

  1. #1
    Registered User
    Join Date
    Apr 2020
    Posts
    7

    General Stack Implementation

    Hey all,

    I’ve implemented a general stack data type and am posting the source code here in the hope that others may find it useful.

    The stack:

    1. Can hold objects of any type.
    2. Can grow dynamically
    3. Will free memory occupied by stack elements, provided a client-defined free function exists.


    stack.h:

    Code:
    #ifndef __STACK_H__
    #define __STACK_H__
    
    /**
     * stack.h: Definitions for a general stack type.
     *
     * Clients need to define the Stack_Elt data type
     * specifying the fields comprising a stack element
     * before including this header:
     * ...
     * typedef struct Stack_Elt {
     *         ...fields...
     * } Stack_Elt, *Stack_Elt_POINTER;
     * ...
     * #include <stack.h>
     */
    
    #define N_STACK_ELEMENTS(S)   (S->size)
    #define STACK_MAX_ELEMENTS(S) (N_STACK_ELEMENTS(S) - 1)
    #define STACK_CURRENT_SIZE(S) (N_STACK_ELEMENTS(S) * sizeof(Stack_Elt *))
    #define STACK_EXPAND_SIZED(S, N) \
                    (STACK_CURRENT_SIZE(S) + (N * sizeof(Stack_Elt *)))
    /**
     * How many elements occupy the stack.
     */
    #define STACK_N_ELEMENTS(S) \
                    ((N_STACK_ELEMENTS(S) - (N_STACK_ELEMENTS(S) - (S->top + 1))))
    
    #define STACK_IS_EMPTY(S) ((S->top == -1))
    #define STACK_EMPTY_CLEAR(S) (stack_wipe(S))
    
    typedef struct Stack_Elt Stack_Elt;
    
    typedef struct Stack {
            int top;                        /* top of stack */
            int size;                       /* number of possible elements */
            int expand;                     /* size to grow by */
            void (*elt_free)(void *);       /* function to free stack elements */
            struct Stack_Elt **data;        /* stack elements */
    } Stack, *Stack_POINTER;
    
    int stack_empty(Stack *);
    
    void stack_wipe(Stack *);
    
    Stack *stack_new(int, int, void (*elt_free)(void *));
    Stack *stack_expand(Stack *, int);
    Stack_Elt *stack_pop(Stack *);
    Stack_Elt *stack_peek(Stack *);
    Stack_Elt *stack_push(Stack *, Stack_Elt *);
    
    
    #endif /* __STACK_H__ */
    stack.c:
    Code:
    /**
     * stack.c: Implementation of a general stack.
     */
    
    #include <stdlib.h>
    #include <string.h>
    
    #include "stack.h"
    
    enum { FALSE, TRUE };
    
    struct Stack_Elt { /* opaque */ };
    
    /**
     * stack_new: Create a new stack.
     */
    Stack *stack_new(int size, int expand, void (*elt_free)(void *)) {
            int i = 0;
            Stack *stack = malloc(sizeof(Stack));
            stack->top = -1;
            stack->size = size;
            stack->expand = (expand > 0 ? expand : FALSE);
            stack->elt_free = (elt_free == NULL ? free : elt_free);
            stack->data = calloc(size, sizeof(Stack_Elt *));
            for (i = 0; i < stack->size; i++)
                    stack->data[i] = malloc(sizeof(Stack_Elt));
            return stack;
    }
    
    /**
     * stack_empty: Check whether stack is empty.
     */
    int stack_empty(Stack *stack) { return stack->top == -1; }
    
    /**
     * stack_pop: Remove top item from stack and return it.
     */
    Stack_Elt *stack_pop(Stack *stack) {
            return (STACK_IS_EMPTY(stack)) ? NULL : stack->data[stack->top--];
    }
    
    /**
     * stack_peek: Preview item at the top of the stack.
     */
    Stack_Elt *stack_peek(Stack *stack) {
            Stack_Elt *elt = malloc(sizeof(Stack_Elt));
            return (STACK_IS_EMPTY(stack)) ?
                    NULL : memcpy(elt, stack->data[stack->top], sizeof(Stack_Elt));
    }
    
    /**
     * stack_push: Push a stack element onto the stack.
     */
    Stack_Elt *stack_push(Stack *stack, Stack_Elt *elt) {
            /**
             * Stack push is invalid if stack is full.
             */
            if (stack->top == STACK_MAX_ELEMENTS(stack))
                    if (stack->expand)
                            stack = stack_expand(stack, stack->expand);
                    else
                            return NULL;
    
            /**
             * Insert element into next available slot.
             * Free memory occupied by a prior element, if necessary.
             */
            stack->top++;
            if (stack->data[stack->top] != NULL)
                    stack->elt_free(stack->data[stack->top]);
            stack->data[stack->top] = elt;
            return elt;
    }
    
    /**
     * stack_expand: Expand the size of the stack.
     */
    Stack *stack_expand(Stack *stack, int n_elements) {
            stack->data = realloc(stack->data, STACK_EXPAND_SIZED(stack, n_elements));
            stack->size = N_STACK_ELEMENTS(stack) + n_elements;
            return stack;
    }
    
    /**
     * stack_wipe: Remove all stack elements and free their memory.
     */
    void stack_wipe(Stack *stack) {
            /**
             * Number of elements is S->top + 1
             */
            int n_elements = STACK_N_ELEMENTS(stack);
            while (!stack_empty(stack))
                    stack->elt_free(stack_pop(stack));
    
            /**
             * Clean the slate.
             */
            memset(stack->data, 0, n_elements);
    }
    To use the stack, define your stack items with:

    Code:
    struct Stack_Elt {
        ...fields…
    };
    This structure must be defined comprising the fields of your stack items. Now include the stack.h header.

    To create a new stack:

    Code:
    Stack *stack_new(int, int, void (*elt_free)(void *));
    The first parameter is the size of the stack. The second parameter is the number of items to expand the stack by when it reaches the top of the stack (pass 0 to indicate a non-growing stack). And the third parameter is the user-defined function to free a complex stack item structure, if necessary. By default stack items will be freed with free().

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,910
    stack_peek looks like a memory leak waiting to happen. Perhaps just return stack->data[stack->top] if the stack is not empty?

    There is no point removing the parameter names from the function prototypes in the header; they would help to document these functions instead.

    I note that there seems to be a limitation with your use of struct Stack_Elt instead of an approach involving void*: the stack is limited to objects of a particular type. Granted, it can be any particular type, but only that type once defined.

    Also, while elt_free is a good idea, you would need the user to provide elt_malloc and even elt_realloc if you truly want it to be useful.

    I wonder if those macros should go in the header: quite a few of them look like implementation detail.
    Last edited by laserlight; 04-11-2020 at 07:24 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2020
    Posts
    7
    Ok, thanks for the feedback.

    I see what you mean with stack_peek() I think at the time the thinking was if you peeked an item and then popped one off the stack you'd lose access to that item but it wouldn't matter because you already returned it.

    So you're saying with Stack_Elt we'd take this approach when wanting to keep the stack a particular type similar to the way an int array is all integers and not wanting to allow arbitrary items pushed to the stack? Also, if the data member were made to instead be a void ** how would we know how to interpret the items coming off the stack?

    And wouldn't macros need to be in some sense implementation details since they're just textual replacements?

    This was a learning exercise and it seemed to work well but thanks for the tips.
    Last edited by TheMuffenMann; 04-11-2020 at 08:35 PM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,910
    Quote Originally Posted by TheMuffenMann
    So you're saying with Stack_Elt we'd take this approach when wanting to keep the stack a particular type similar to the way an int array is all integers and not wanting to allow arbitrary items pushed to the stack?
    Yes. You get type safety because you know that the stack consists of struct Stack_Elt objects, whatever they might be.

    Quote Originally Posted by TheMuffenMann
    Also, if the data member were made to instead be a void ** how would we know how to interpret the items coming off the stack?
    The stack itself won't know: it will merely be handling items that consist of a fixed number of bytes. It is up to the code that uses the stack to pass objects of the expected type in when pushing, and then cast them accordingly when peeking and popping. This is great because then you can have different stacks that handle items with their own different fixed number of bytes; this is not so great because you could accidentally mix up the objects being passed/retrieved and the error may well only be detected at runtime.

    Quote Originally Posted by TheMuffenMann
    And wouldn't macros need to be in some sense implementation details since they're just textual replacements?
    No, they could form part of the interface that you're providing. For example, STACK_IS_EMPTY and STACK_EMPTY_CLEAR looks like they could be part of the interface, but then there is already the stack_empty and stack_wipe functions. Why provide two ways to do the exact same thing?

    N_STACK_ELEMENTS and STACK_MAX_ELEMENTS can be done away with by accessing size directly. STACK_N_ELEMENTS sounds like N_STACK_ELEMENTS, so people are likely to get them mixed up. What I would suggest is this: rename the size member to capacity, because "capacity" means "the maximum amount or number that can be received or contained", which ties in with your comment of it being "number of possible elements". Whereas you can consider "size" to be the "current number of elements", and hence instead of a STACK_N_ELEMENTS macro, you could provide a stack_size function.

    STACK_CURRENT_SIZE and STACK_EXPAND_SIZED don't look like things you want the user of the stack to access, i.e., they are implementation detail, so they shouldn't be in the header.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Apr 2020
    Posts
    7
    I tried to edit the previous post but it seems I cant.

    Thanks, I think I get what you're saying.

    I made some changes and although the stack still holds elements of a Stack_Element type, that type itself is a void * so can point to anything. It also holds the item’s type. This was the main way I could think of to give a hint to the calling code as to the type of a popped off stack item – store the type field along with the data value.

    Now client code doesn’t need to define a special stack value structure. They just create a generic Stack_Element item and stash whatever value in the void * slot, set the type field and then push onto the stack. And the macros are more to make the functions themselves easier to read. This is an exercise for me to make a stack as general as possible. I’m studying data structures.



    Here's the revised code:

    stack.h:
    Code:
    #ifndef __STACK_H__
    #define __STACK_H__
    
    /**
     * stack.h: Definitions for a general stack type.
     */
    
    #define STACK_MAX_ELEMENTS(S) (S->size - 1)
    #define STACK_CURRENT_SIZE(S) (S->size * sizeof(Stack_Element *))
    #define STACK_EXPAND_SIZED(S, N) \
                    (STACK_CURRENT_SIZE(S) + (N * sizeof(Stack_Element *)))
    /**
     * How many elements occupy the stack.
     */
    #define STACK_N_ELEMENTS(S) ((S->size - (S->size - (S->top + 1))))
    
    typedef enum Enum_Element_Type {
            C_TYPE_INT,
            C_TYPE_CHAR,
            C_TYPE_FLOAT,
            C_TYPE_DOUBLE,
            C_TYPE_CHAR_ARRAY
    } Enum_Element_Type;
    
    typedef struct Stack_Element {
            void *value;                    /* data value */
            Enum_Element_Type type;         /* data type */
    } Stack_Element, *Stack_Element_POINTER;
    
    typedef struct Stack {
            int top;                        /* top of stack */
            int size;                       /* number of possible elements */
            int expand;                     /* size to grow by */
            Stack_Element **data;           /* stack elements */
    } Stack, *Stack_POINTER;
    
    int stack_empty(Stack *stack);
    
    void echo_stack(Stack *stack);
    void stack_wipe(Stack *stack);
    
    Stack *stack_new(int size, int expand);
    Stack *stack_expand(Stack *, int n_elements);
    Stack_Element *stack_pop(Stack *stack);
    Stack_Element *stack_peek(Stack *stack);
    Stack_Element *stack_push(Stack *stack, Stack_Element *elt);
    Stack_Element *stack_elm_new(void *value, Enum_Element_Type data_type);
    
    
    #endif /* __STACK_H__ */
    stack.c:
    Code:
    /**
     * stack.c: Implementation of a general stack.
     */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #include "stack.h"
    
    /**
     * stack_new: Create a new stack.
     */
    Stack *stack_new(int size, int expand) {
            int i = 0;
            Stack *stack = malloc(sizeof(Stack));
            stack->top = -1;
            stack->size = size;
            stack->expand = (expand > 0 ? expand : 0);
            stack->data = calloc(size, sizeof(Stack_Element *));
            for (i = 0; i < stack->size; i++)
                    stack->data[i] = malloc(sizeof(Stack_Element));
            return stack;
    }
    
    /**
     * stack_elm_new: Create new stack element.
     */
    Stack_Element *stack_elm_new(void *value, Enum_Element_Type type) {
            Stack_Element *elm = malloc(sizeof(Stack_Element));
            switch (type) {
                    case C_TYPE_INT:
                            elm->type = C_TYPE_INT;
                            break;
                    case C_TYPE_CHAR:
                            elm->type = C_TYPE_CHAR;
                            break;
                    case C_TYPE_FLOAT:
                            elm->type = C_TYPE_FLOAT;
                            break;
                    case C_TYPE_DOUBLE:
                            elm->type = C_TYPE_DOUBLE;
                            break;
                    case C_TYPE_CHAR_ARRAY:
                            elm->type = C_TYPE_CHAR_ARRAY;
                            break;
            }
            elm->value = value;
            return elm;
    }
    
    /**
     * echo_stack: Print the stack contents.
     */
    void echo_stack(Stack *stack) {
            int i = 0;
            Stack_Element *elm = NULL;
            printf("\nStack contents (%d):\n", STACK_N_ELEMENTS(stack));
            while (!stack_empty(stack)) {
                    elm = stack_pop(stack);
                    switch (elm->type) {
                            case C_TYPE_INT:
                                    printf("\t%d.) %d\n", i++, *((int *) elm->value));
                                    break;
                            case C_TYPE_CHAR:
                                    printf("\t%d.) %c\n", i++, *((char *) elm->value));
                                    break;
                            case C_TYPE_FLOAT:
                                    printf("\t%d.) %f\n", i++, *((float *) elm->value));
                                    break;
                            case C_TYPE_DOUBLE:
                                    printf("\t%d.) %g\n", i++, *((double *) elm->value));
                                    break;
                            case C_TYPE_CHAR_ARRAY:
                                    printf("\t%d.) %s", i++, (char *) elm->value);
                                    break;
                    }
            }
    }
    
    /**
     * stack_empty: Check whether stack is empty.
     */
    int stack_empty(Stack *stack) { return stack->top == -1; }
    
    /**
     * stack_pop: Remove top item from stack and return it.
     */
    Stack_Element *stack_pop(Stack *stack) {
            return (stack_empty(stack)) ? NULL : stack->data[stack->top--];
    }
    
    /**
     * stack_peek: Preview item at the top of the stack.
     */
    Stack_Element *stack_peek(Stack *stack) {
            return (stack_empty(stack)) ? NULL : stack->data[stack->top];
    }
    
    /**
     * stack_push: Push a stack element onto the stack.
     */
    Stack_Element *stack_push(Stack *stack, Stack_Element *elm) {
            if (stack->top == STACK_MAX_ELEMENTS(stack))
                    if (stack->expand)
                            stack = stack_expand(stack, stack->expand);
                    else
                            return NULL;
    
            Stack_Element *top_elm = stack->data[++stack->top];
            if (top_elm != NULL)
                    free(top_elm->value);
    
            stack->data[stack->top] = elm;
            return elm;
    }
    
    /**
     * stack_expand: Expand the size of the stack.
     */
    Stack *stack_expand(Stack *stack, int n_elms) {
            stack->data = realloc(stack->data, STACK_EXPAND_SIZED(stack, n_elms));
            stack->size = stack->size + n_elms;
            return stack;
    }
    
    /**
     * stack_wipe: Remove all stack elements and free their memory.
     */
    void stack_wipe(Stack *stack) {
            int n_elements = STACK_N_ELEMENTS(stack);
            while (!stack_empty(stack))
                    free(stack_pop(stack));
            memset(stack->data, 0, n_elements);
    }
    Test program:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #include "stack.h"
    
    int main(int argc, char *argv[]) {
            int iter = 0;
            int value = 76;
            char character = 'C';
            Stack *stack = stack_new(10, 3);
    
            Stack_Element *elm = NULL;
    
            char buf[256] = { 0 };
            do {
                    printf("(ENTER) >>> ");
                    fflush(stdout);
                    fgets(buf, 256, stdin);
                    if (buf[0] == '\n') break;
                    elm = stack_elm_new(strdup(buf), C_TYPE_CHAR_ARRAY);
                    stack_push(stack, elm);
            } while (1);
            printf("\n");
    
            printf("Pushing 76...\n");
            stack_push(stack, stack_elm_new(&value, C_TYPE_INT));
    
            printf("Pushing 'C'...\n");
            stack_push(stack, stack_elm_new(&character, C_TYPE_CHAR));
    
            echo_stack(stack);
    
            printf("\nClearing the stack...\n");
            stack_wipe(stack);
    
            printf("\nStack has (%d) items.\n", STACK_N_ELEMENTS(stack));
    
            return 0;
    }
    The output:

    Code:
    (ENTER) >>> text 1
    (ENTER) >>> text 2
    (ENTER) >>> text 3
    (ENTER) >>> text 4
    (ENTER) >>> 
    
    Pushing 76...
    Pushing 'C'...
    
    Stack contents (6):
        0.) C
        1.) 76
        2.) text 4
        3.) text 3
        4.) text 2
        5.) text 1
    
    Clearing the stack...
    
    Stack has (0) items.
    Last edited by TheMuffenMann; 04-12-2020 at 01:14 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack Implementation No Errors
    By fredlo2010 in forum C Programming
    Replies: 2
    Last Post: 04-08-2016, 07:59 PM
  2. stack implementation using arrays
    By Mishu Singh in forum C Programming
    Replies: 1
    Last Post: 05-31-2014, 12:36 AM
  3. Replies: 5
    Last Post: 07-01-2011, 11:35 AM
  4. Stack Implementation and Exceptions
    By audinue in forum C Programming
    Replies: 4
    Last Post: 06-22-2008, 09:32 AM
  5. stack implementation problem-help needed
    By sanju in forum C Programming
    Replies: 1
    Last Post: 12-10-2002, 07:29 AM

Tags for this Thread