ADT stack with a dynamic array

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 
#include 
#include 

#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 {

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:

• You should probably remember the initial capacity and not shrink the array below that level.

• 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.

StackExchange Code Review Q#106510, answer score: 4