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;
}
malloc
(and family) is not required. See Do I cast the result ofmalloc
? \$\endgroup\$