Weird stack problem

[barramundi9]

My stack.h file :

/* stack using array implementation */

#include <stdio.h>
#include <stdlib.h>
#define max 5

struct stack {
        int array[max];
        int top;
};

typedef struct stack stack;

int isFull (stack *s);
int isEmpty (stack *s);
void push (stack *s, int value);
void pop (stack *s);
void printStack (stack *s);

My stack.c file :

/* stack operations */

#include "stack.h"

int isFull (stack *s) {
        if (s->top >= max) {
                printf("s->top is greater than or equal to max.\n");
                return 0;
        } else {
                return 1;
        }
}

int isEmpty (stack *s) {
        if (s->top == -1) {
                return 0;
        } else {
                return 1;
        }
}

void push (stack *s, int value) {
        if (!(isFull(s))) {
                printf("Stack overflow.\n");
        } else {
                s->top++;
                s->array[s->top] = value;
        }
}

void pop (stack *s) {
        if (!(isEmpty(s))) {
                printf("The stack is empty.\n");
        } else {
                printf("The value being popped: %d\n", s->array[s->top--]);
        }
}

void printStack (stack *s) {
        int i;
        if (s->top == -1) {
                printf("There is nothing to print.\n");
        } else {
                printf("s->top : %d\n", s->top);
                printf("Stack:\n");
                printf("======\n");
                for (i=s->top; i>=0; i--) {
                        printf("%d\n", s->array[i]);
                }
        }
}

my stackMain.c file :

/* main file for stack */

#include "stack.h"

int main () {
        stack *ptr;

        ptr = (stack *) malloc (sizeof(stack));
        ptr->top = -1;

        push(ptr, 1);
        push(ptr, 5);
        push(ptr, 8);
        push(ptr, 11);
        push(ptr, 224);
        push(ptr, 9);
        pop(ptr);

        printStack(ptr);
        return 0;
}

After compilation, the result is:


The value being popped: 0
s->top : 8
Stack:
======
0
0
135137
8
224
11
8
5
1


which is really weird, because I have limited the stack to five elements(or I thought I have) (in stack.h, #define max 5). However, the number of stack elements will change according to the last value I pushed onto the stack, in this case, it's 9, i.e. if I change the value of max to 100, the stack will grow to 100 elements.

What did I do wrong?

Thanks.

Regards,
barramundi9

[laserlight]

May I suggest that if you name a function isX, then if X is the case, you return 1, otherwise you return 0? Because when I read !(isFull(s)), I think "not is full", but actually it means "is full", which is terribly confusing. If you really do want to return 0 to mean success, then use error codes instead of a boolean return value.

[barramundi9]

Thanks for the suggestion, laserlight. Actually, that was what I did at first, but the output was weird, so I changed it.

Now I've changed to return 1 when it's full or empty and 0 when it's not, the output is still the same, any idea?

Thanks.

barramundi9

[claudiu]

You are not counting correctly when the stack is full. It should be fairly obvious that in the push function you always take the else branch, otherwise you wouldn't be seeing this behaviour. Try stepping through your code on paper with a pencil. I suspect the problem is that you have max=5 elements in the stack but the last one is array[4] not array[5], since counting starts at 0. When you add the first element top becomes 0, ... when you add the 5th element top becomes 4. Since 4 is not >= max (which is 5) you keep adding.

[barramundi9]

OMG, you're right. It is fairly obvious ... my mistake. Once I change the if statement to if ((s->top) >= (max-1)), it works, thanks, claudiu.

Any idea as to why the stack always grew to the last value pushed onto the stack before I corrected the if statement? if I pushed 9 to the stack, the stack grew to 9 elements, if I pushed 11, the stack grew to 11 elements. Any ideas?

[oogabooga]

Your implementation is writing to stack[max], which is out of bounds. This explains why the stack "grows" to the last value you pushed, because it was actually (apparently) written over top.

Other points:

max should be all uppercase, and a better name would be STACK_MAX.

Don't include stdio.h and stdlib.h in stack.h. Include them in stack.c instead.

You aren't freeing the memory you malloc. Actually, you should have a newStack and deleteStack function in your stack implementation.

[barramundi9]

After drawing on paper, I see what you mean now. Thank you, oogabooga and everyone.

Regards,
barramundi9