Using a function call to implement a stack

Question

I'm a little unclear on this part of C, since it's a bit unlike other languages I've used, but this may just be a dumb question. I'm trying to implement a stack. I have the node struct, it has the information I want to pass:

struct position{
   int square[2];
   int counter;
   struct position *prev;
};

so in main, I declare and initialize the bottom node of the stack, set *prev to NULL, then declare the rest. My question is, what happens when I try to pass it to function pop? I can create a position object that points to this one and return that, but will it be pushed off the stack when the function closes? Or should I return the position and set that equal to a new position object in main? What if I decide to create several of these nodes in a function? Will they remain once the function closes?

Edit: mah reminded me of my followup question which is, if they don't exist outside of the function, should I use malloc to create the space in the memory for them?

first of all, you do not set *prev (which reads as value at address of prev), but you do set prev to NULL, which of type struct position*. That's syntactic detail, but it's a really common beginner mistake to mix the * operator and the foo* type. — zmo
– zmo, Commented Feb 21, 2014 at 18:46
@JFA re: your follow-up... braces ({}) don't only define blocks of code, as you see in your structure definition. Your elements (square, counter, prev) do not need to be malloc'd, just a struct position needs to be malloced. It will contain all of the elements. — mah
– mah, Commented Feb 21, 2014 at 18:55
@mah I may have mis-typed something that made the question misleading. I edited the edit. — jfa
– jfa, Commented Feb 21, 2014 at 18:57
@JFA where you're headed is really a fine line between "can it be made to work" and "is it a good idea". Under the right circumstances (meaning it depends on the exact code you write) you can make it work with and without malloc, but you will make it far too easy to break something if you take the no-malloc approach. That's the sort of shortcut that might work initially, and later a subtle code change can have surprising undesirable effects. Using pointers to malloc'd objects minimizes that risk. — mah
– mah, Commented Feb 21, 2014 at 19:01
it's not really a question of scope, but more a question of how you want to use your stack. To have it dynamic, you need to use malloc()s. — zmo
– zmo, Commented Feb 21, 2014 at 19:31

mah · Accepted Answer · 2014-02-21 18:48:19Z

1

The lifetime of your objects depend on where they're created; if you declare for example a structure within a block of code (where a block is everything inside { and its matching }), that structure is no longer valid once execution leaves the block. Pointers to that structure are only valid as long as the structure is valid.

For what you're describing, you want to dynamically allocate your structures, using either malloc() or a similar function. Dynamically allocated data will remain valid (assuming you do not overwrite it) until you free() the memory, or until your program terminates. Pointers to these areas of memory will remain valid for that same period of time.

Consider:

static struct position *topOfStack = NULL;

void push(struct position *node)
{
    node->prev = topOfStack;
    topOfStack = node;
}

struct position *pop()
{
    struct position *popped = topOfStack;
    if (topOfStack) topOfStack = topOfStack->pref;
    return popped;
}

To use this, you can:

f() {
    struct position *node = malloc(sizeof(*node));
    /* ... fill in node details ... */
    push(node);
}

Notice that I allocated the node dynamically. Had I just declared a struct position node;, I could legally call push(&node); but once my function left scope, the stack would have an invalid item in it (which would likely cause havoc).

answered Feb 21, 2014 at 18:48

mah

40.1k9 gold badges79 silver badges94 bronze badges

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

3 Comments

jfa Over a year ago

If I were planning on just using the stack in one function (ie main or my function generatestack) but still used a function push, could I return the top position struct since it passes by value?

mah Over a year ago

If you're passing by value instead of reference, you will still have to malloc space to copy it into in order to link it into your stack... if you don't do that, you're very likely to run into problems. Using pointers is not necessarily an easy thing to learn in C, but for building any kind of dynamic list such as a stack, it should be considered absolutely required.

jfa Over a year ago

Thanks. I learned how to use pointers, I'm just not always clear on when I should.

zmo · Accepted Answer · 2014-02-21 19:30:45Z

what happens when I try to pass it to function pop?

it depends on your pop() function prototype. If the pop's function prototype should be:

struct position* pop(struct position* stack);

I can create a position object that points to this one and return that, but will it be pushed off the stack when the function closes?

your question is quite unclear, and it looks like a big misunderstanding of instance scoping in C. Basically, you have two ways to allocate variables, either on the stack or on the heap. The scoping you're talking about is stack instances scope.

What if I decide to create several of these nodes in a function? Will they remain once the function closes?

basically, if you use the stack, they will live as long as the scope they're declared in. In C, scope is defined by { and }. for example:

int main() {
    struct position pos1;
    struct position pos2;
    struct position pos3;
    pos3.prev = pos2;
    pos2.prev = pos1;
    pos1.prev = NULL;
    pop(&pos3);
}

there you declare 3 variables, and associate them, and the pop function just resets the .prev link. But for a stack that kind of architecture is not really useful, because it is quite limited.

There you definitely need to push your instances in the heap, thus using malloc() and free():

// push() pseudocode:
// take stack, iterate over each prev until prev is NULL
// allocate prev with malloc() the same way as for "stack" in main()
// insert values in prev
void push(struct position* stack, int* value);

// pop() pseudocode:
// take stack, iterate over each prev until prev->prev is NULL, 
// then keep prev->prev in a temporary variable
// set prev to NULL
// return temporary variable (former prev->prev)
struct position* pop(struct position* stack);

int main() {
    int value[2];
    struct position* stack = malloc(sizeof(struct position));
    // value is what you want to push to the stack
    value[0] = 42;
    value[1] = 42;
    push(stack, value);
    value[0] = 2;
    value[1] = 20;
    push(stack, value);
    struct position* pos;
    pos = pop(stack);
    // do something with pos->value
    free(pos);
}

there you create a pointer to a node for which you allocate some memory in the heap. the push() function is allocating some new memory, assigning .prev for that new space to stack's address and populating that memory with the value. pop() should get to the value before the last one, reset its pointer to that value, and return that value.

Of course, I'm just giving concepts and ideas here, I'm leaving you get to the real implementation. One advice though, instead of using square that contains an array, use two separate values in your struct, that will make it simpler for a first implementation.

Collectives™ on Stack Overflow

Using a function call to implement a stack

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related