Implementing Stack using Dynamic Array

Question

I have implemented a Stack using dynamic array(implementing array doubling) but when the doubling happens for the second time, I am getting runtime error! What's going wrong with the implementation? Please help.

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

struct Stack {
    int *arr;
    int top,size,capacity;
};

struct Stack *createStack(int capacity) {
    struct Stack *s = (struct Stack*)malloc(sizeof(struct Stack));
    s->arr = (int*)malloc(sizeof(int)*capacity);
    s->top = -1;
    s->capacity = capacity;
    s->size = 0;
    return s;
}

void doubleStack(struct Stack *s) {
    s->capacity = s->capacity*2;
    s->arr = realloc(s->arr,s->capacity);
    printf("Array doubling happened successfully!\n");
}

int isFull(struct Stack *s) {
    return s->size == s->capacity;
}

void push(struct Stack *s, int item) {
    if(isFull(s))
        doubleStack(s);

    printf("%d pushed!\n",item);
    s->arr[++(s->top)] = item;
    s->size++;
}

int isEmpty(struct Stack *s) {
    return s->size == 0;
}

void pop(struct Stack *s) {
    if(isEmpty(s)) {
        printf("Empty stack!\n");
        return;
    }

    int item = s->arr[(s->top)--];
    s->size--;
    printf("%d popped!\n",item);
}

int main(void) {
    struct Stack *s = createStack(2);
    push(s,1);
    push(s,2);
    push(s,3);
    push(s,4);
    push(s,5);
    pop(s);
    pop(s);
    return 0;
}

Note: they say [you shouldn't case the result of `malloc()` in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — MikeCAT, Dec 09 '15 at 16:23
`printf("Array doubling happened successfully!\n");` without checking if the `realloc()` was successful? Nonsense. — MikeCAT, Dec 09 '15 at 16:24
That was not meant to check the successful allocation of memory but to tell the no of times the array doubling was happening! I appreciate the help but watch the lingo! — Rajan Kalra, Dec 09 '15 at 16:45

score 2 · Answer 1 · answered Dec 09 '15 at 16:27

You failed to multiply the size to allocate via realloc() by sizeof(int).

Try this with some other improvement:

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

struct Stack {
    int *arr;
    int top,size,capacity;
};

struct Stack *createStack(int capacity) {
    struct Stack *s = malloc(sizeof(struct Stack));
    s->arr = malloc(sizeof(int)*capacity);
    s->top = -1;
    s->capacity = capacity;
    s->size = 0;
    return s;
}

void destroyStack(struct Stack *s) {
    if(s != NULL) free(s->arr);
    free(s);
}

void doubleStack(struct Stack *s) {
    s->capacity = s->capacity*2;
    s->arr = realloc(s->arr,sizeof(int)*s->capacity);
    if(s->arr != NULL) {
        printf("Array doubling happened successfully!\n");
    } else {
        perror("realloc");
    }
}

int isFull(struct Stack *s) {
    return s->size == s->capacity;
}

void push(struct Stack *s, int item) {
    if(isFull(s))
        doubleStack(s);

    printf("%d pushed!\n",item);
    s->arr[++(s->top)] = item;
    s->size++;
}

int isEmpty(struct Stack *s) {
    return s->size == 0;
}

void pop(struct Stack *s) {
    if(isEmpty(s)) {
        printf("Empty stack!\n");
        return;
    }

    int item = s->arr[(s->top)--];
    s->size--;
    printf("%d popped!\n",item);
}

int main(void) {
    struct Stack *s = createStack(2);
    push(s,1);
    push(s,2);
    push(s,3);
    push(s,4);
    push(s,5);
    pop(s);
    pop(s);
    destroyStack(s);
    return 0;
}

Thanks for the swift reply, its working. I have a question why was it producing error for the second error doubling and not in the first time itself? — Rajan Kalra, Dec 09 '15 at 16:39

Implementing Stack using Dynamic Array

1 Answers1