What's wrong with my Stack Implementation?

Question

I created an implementation of a Stack in C. Here are the relevant definitions/methods, I have stripped all the error checking/reallocation so don't comment on that:

typedef struct {
    Element *data;
    int top;
    int size;
} Stack;

typedef void* Element;

void push(Stack *s, Element e) {
    s->data[(s->top)++] = e;
}

Now in another method, I have a loop in which I call push(). Something like

int character;
Stack *s = createStack();
while((character = getchar()) != EOF) {
    int tmp = character;
    push(s, &tmp);  
}

However, this doesn't function how I want it to. The stack receives the same address everytime, thus when each character is read, the "contents" of the entire stack change. How do I modify this to do what I want. e.g when abcde is read, the stack looks like (top-down) e,d,c,b,a.

Seth Carnegie · Accepted Answer · 2012-02-15 04:06:32Z

3

int tmp = character;
push(s, &tmp);

There you are passing the address of the local variable tmp to the function push which is storing the pointer in itself. Every time the loop is iterated, the variable is destroyed and another local variable is made (most likely on top of the old variable), so you are storing pointers to destroyed variables.

If you want your stack to be generic and work with void*, you'll have to make sure the lifetimes of the objects you store is longer than the lifetime of the stack. One way you can do this is allocate the variables on the heap:

char* c = malloc(sizeof(char)); // or malloc(1) but sizeof is there in case you
                                // change the type later
*c = character;
push(s, c);

Then deallocate each one after the stack is no longer in use so you don't get a memory leak.

answered Feb 15, 2012 at 4:06

Seth Carnegie

75.3k22 gold badges185 silver badges252 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Richard J. Ross III Over a year ago

Or just use alloca and forget about freeing the memory, after all that's what alloca is for.

Seth Carnegie Over a year ago

@RichardJ.RossIII no, that's the same as allocating a local variable on the stack and storing a pointer to it, except that the memory is reclaimed when the alloca-calling function returns instead of when the scope ends.

Richard J. Ross III Over a year ago

Correct, but it gives you a different pointer every time, which is what the OP wants.

Seth Carnegie Over a year ago

@Rich I don't think the point was to have it be a different pointer, I think the point was for it to work, and getting the same pointer was just a symptom of not working. Using alloca would only be marginally less not working.

Richard J. Ross III · Accepted Answer · 2012-02-15 04:32:00Z

0

As an addendum to the above answer:

You can simply cast your int value to a pointer:

push(s, (int *) tmp);

answered Feb 15, 2012 at 4:32

Richard J. Ross III

55.7k25 gold badges139 silver badges205 bronze badges

Collectives™ on Stack Overflow

What's wrong with my Stack Implementation?

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related