ADT stack with a dynamic array

Question

I'm starting to learn about data structures and coding in C. The stack is the simplest of all data structures so I'm trying to implement an ADT stack with dynamically allocated array in C. This implementation does have one obvious problem i.e. it hoards memory even after popping the data. How do I solve this problem?

stacklib.h

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

#ifndef STACKLIB_H
#define STACKLIB_H


/* generic type pushed into the stack */    
/* in this case it's just an int */
typedef int item_t;

/* our stack data type */
typedef struct {
    int size;
    int capacity;
    int *elements;
} stack;

/* interface to our new stack data type */
stack* create_stack(int capacity);
int push_stack(stack *mystack, item_t data);
void* pop_stack(stack *mystack);
void delete_stack(stack *mystack);

#endif

stacklib.c

#include "stacklib.h"

/* a helper function to handle exceptions */
void handle_error(const char* message)
{
    if(errno) {
        perror(message);
    } else {
        printf("Error: %s\n", message);
    }

    exit(1);
}


stack* create_stack(int capacity)
{
    stack *stack_ptr = (stack*) malloc(sizeof(stack));

    if(stack_ptr == NULL)
        handle_error("Error while allocating memory.");

    int *elements_ptr = (item_t *) malloc(capacity*sizeof(item_t));

    if(elements_ptr == NULL)
        handle_error("Error while allocating memory.");


    stack_ptr->size = -1;
    stack_ptr->capacity = capacity;
    stack_ptr->elements = elements_ptr;

    return stack_ptr;
}

void delete_stack(stack *mystack)
{
    free(mystack->elements);
    free(mystack);
    mystack = NULL;
}

/* Returns 0 on success, 1 on failure */
int push_stack(stack *mystack, item_t data)
{
    int res = 0;
    /* double the array size when stack is full */
    if(mystack->size == (mystack->capacity - 1)) {
        item_t *tmp = (item_t*) realloc(mystack->elements, sizeof(item_t) * mystack->capacity * 2);
        if(tmp == NULL) {
            res = 1;
        } else {
            mystack->elements = tmp;
            mystack->capacity = mystack->capacity * 2;
        }
    }
    mystack->size++;
    mystack->elements[mystack->size] = data;

    return res;
}

/* Returns a pointer to the popped data or NULL if the stack is empty */
void* pop_stack(stack *mystack)
{
    int *res;
    if(mystack->size == -1) {
        res = NULL;
    } else {
        res = &mystack->elements[mystack->size];
        mystack->size--;
    }
    return res;
}

main.c

#include "stacklib.h"  

int main(void){
    stack *my_stack = create_stack(5);
    item_t i;
    for(i = 0; i < 50; i++)
        push_stack(my_stack, i);

    item_t res, *item ;
    while((item = (item_t*)pop_stack(my_stack)) != NULL) {
        res = *item;
        printf("data: %d\n", res);
    }
    delete_stack(my_stack);
    printf("last item popped was  %d\n", res);
    return 0;
}

Answer 1

Wrong type

You defined a type called item_t but you didn't use it everywhere:

/* our stack data type */
typedef struct {
    int size;
    int capacity;
    int *elements;
} stack;

Here, elements should be of type item_t *. Also, your pop function should return a item_t * instead of a void *.

You could go a different direction and use void * as your generic type instead of item_t. That way, you could store anything in your stack, but you'd have to allocate each item.

Size of -1?

I agree with janos that size should start at 0 instead of -1. That way, size will represent the number of items on the stack.

Error handling in push

You correctly check the return value of realloc() in your push function. However, if it returns NULL, your code currently keeps going and causes a buffer overflow. You should return 1 immediately and not fall through to the rest of the code.

Useless line

In delete_stack(), the line:

mystack = NULL;

doesn't do anything because it won't affect the caller's pointer.

Code simplification

There are a few things that you could do to simplify your code. One is to eliminate your res variable if you can just return a value immediately. Another is to merge the postdecrement/postincrement operation into the array access. For example, your pop function:

void* pop_stack(stack *mystack)
{
    int *res;
    if(mystack->size == -1) {
        res = NULL;
    } else {
        res = &mystack->elements[mystack->size];
        mystack->size--;
    }
    return res;
}

could be simplified to:

item_t *pop_stack(stack *mystack)
{
    if (mystack->size == -1)
        return NULL;
    return &mystack->elements[mystack->size--];
}

Reducing memory

In regards to your question about reducing capacity when popping, you could shrink your array when you pop but you need to be careful:

1. You should probably remember the initial capacity and not shrink the array below that level.
2. You don't want to do something where you resize too often. For example, if you did the natural thing of shrinking when you pop below half capacity: if (size == capacity/2) { resize smaller }, then what could happen is that you could bounce between sizes if the user pushes and pops right at the threshold. In other words, if the last push caused an expansion, the next pop would cause a contraction, and that would be bad because they could keep pushing and popping at that level and cause a resize every time. Therefore, you need to either use a smaller ratio than 1/2 for contraction or use a different criterion.

Answer 2

This implementation does have one obvious problem i.e. it hoards memory even after popping the data. How do I solve this problem?

Just like you double the size when capacity is reached, the common practice to save memory is to reduce the size when the usage drops below some arbitrary threshold. Yes, this will incur copying (the same as when doubling the size). Therefore, the thresholds and multipliers used for all resize operations (increasing or decreasing) may need careful tuning according to usage patterns to avoid them happening too often.

---

It's unnatural that the value of size is actually the real size - 1. So that size == -1 indicates an empty stack. It would be better to refactor to make size == 0 indicate an empty stack. It will be more natural and intuitive that way.

---

A minor thing, but instead of this:

mystack->capacity = mystack->capacity * 2;

This is simpler:

mystack->capacity *= 2;

Answer 3

Just a little note to give you an alternative method on handling the ADT stack which is easier to maintain: Instead of using a dynamic array, use a linked list.

Using a linked list would eliminate the need for dynamically changing the array size, and would do allocations (and freeing) of memory much easier. At any point in the time the list will only have allocated just enough memory.

In addition if you make the list correctly it will almost be an immutable object requiring little or no work when pushing or popping besides handling the new stack element, and updating a pointer to whatever is the top of the stack.

Here are some code to get you started, if you want to pursue this alternate method:

/* our stack data type */
typedef struct {
    stack_element *top_of_stack;
} stack;

typedef struct {
   item_t value;
   stack_element *next;
} stack_element;

/* Returns 0 on success, 1 on failure */
int push_stack(stack *mystack, item_t data)
{
    int res = 0;

    stack_element *tmp = (stack_element*) malloc(sizeof(stack_element));

    if(tmp == NULL) {
        res = 1;
    } else {
        tmp->next = mystack->top_of_stack;
        tmp->value = data;
    }

    return res;
}

item_t pop(stack *mystack) 
{
   item_t tmp;
   stack_element *element;

   if (mystack->top_of_stack != null) {
       element mystack->top_of_stack->value;

       tmp = element->value;
       mystack->top_of_stack = element->next;
       free(element)
       return tmp
   }
}

Disclaimer: Please note that code is untested, it is more for giving a gist of the idea of using a linked list.

Answer 4

/* generic type pushed into the stack */    
/* in this case it's just an int */
typedef int item_t;

/* our stack data type */
typedef struct {
    int size;
    int capacity;
    int *elements; // problem here
} stack;

void* pop_stack(stack *mystack); // same here

If your stack is supposed to hold item_ts, then it should hold item_ts, not ints, and the pop function should return item_t*.

stack* create_stack(int capacity)
{
    stack *stack_ptr = (stack*) malloc(sizeof(stack));

    if(stack_ptr == NULL)
        handle_error("Error while allocating memory.");

    int *elements_ptr = (item_t *) malloc(capacity*sizeof(item_t));

    if(elements_ptr == NULL)
        handle_error("Error while allocating memory.");

If the second malloc failed, you leaked stack_ptr. Not a real big problem since you exit right after it, but worth correcting anyway.

Also please read Do I cast the result of malloc? (Spoiler: no you should not.) Plus you've got stack* and item_t *. Your spacing should be consistent - pick one or the other.

void delete_stack(stack *mystack)
{
    free(mystack->elements);
    free(mystack);
    mystack = NULL; // <- no-op
}

That last assignment is useless - it only modifies the local variable that is not used further. Remove it to avoid confusion. If you meant to zero-out the callers pointer, you need to take that parameter with a pointer-to-pointer.