CODEWITHSUNDEEP
cstruct
jfa
jfa

Reputation: 1101

Using a function call to implement a stack

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?

Upvotes: 1

Views: 97

Answers (2)

zmo
zmo

Reputation: 24812

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.

Upvotes: 0

mah
mah

Reputation: 39807

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).

Upvotes: 1

Related Questions