the stack?

Recommended Posts

Okay, heres the deal: I'm a beginner... and I read -alot- of tutorials. Mostly about stuff I don't even understand, so I thought I'd try to "start over" from the ground up, and try to not only learn coding techniques, but to implement them into something useful this time around. But I've come across several terms which are the source of some confusion. More specifically, I've seen the word "stack" thrown around multiple times. I'm not exactly sure what it is used for, and how it would be applied to C/C++ and game programming. All I really know, is that it has something to do with memory, and push and pop and what-not. I've searched google, and I've read a wide range of articles on this site, yet nothing really nips the topic in the bud. I'm looking for a decent article that fully explains the topic, yet I haven't really found any. If anyone could direct me to one, I'd appreciate it. Or perhaps you'd like to enlighten me yourself? If so, then by all means, feel free to do such. If it makes any difference, I've been meddling around with C/C++ for a couple years now, so I'd say I have a pretty solid understanding of most of the basics. But not quite solid enough. Thanks, -Darin

Share on other sites
nilkn    960
The stack is a portion of memory which static (non-pointer) variables are allocated on.

It's called the stack because that is essentially what it is. When something is added to the stack, it must go on the top. This is called "pushing" the item onto the stack. The only thing that can be removed from the stack is the topmost item. This is called "popping" off the topmost item.

Dynamically allocated variables (pointers) are placed into a portion of memory called the "heap". The heap is quite a bit different from the stack. Most important is that the position at which a new item will be added it totally random. Therefore, the heap permits random-access. You can add something anywhere, and remove something from anywhere.

Though this has it's advantages, it leads to several problems including slower run-time performance and heap fragmentation.

Share on other sites
Drakkcon    612
Whenever you declare a variable like this:

int foo;

or this:

auto int bar;

You're creating it on the stack (auto isn't ever necessary, it just means to put it on the stack)

The stack is a place in memory about two megabytes large (I think), where scoped variables go. It's very fast. It's fast because it's staticalready known what variables are needed--there can be no dynamic programming because you have to initialize all variables at compile time. With the stack, there is no random access. Things are stored in order.

The heap and the free-space are two other areas or putting memory. Using the new keyword and the malloc() functions allow you to access them (I don't think they're the same thing, but I'm not sure).

I hope this helps.

Edit: oops, nilkn beat me.

Share on other sites
MichaelWeber    138
And just to make matters worse...Stack is also an Abstract Datatype (ADT).

hmm...Abstract datatype ?

A description of what a datatype does, without describing how (implementation).

Share on other sites
ernow    732
On the Windows platform:

The OS distributes execution time on the CPU('s) by scheduling threads. Each process has at least one thread. A thread can start an other thread in the same process. Threads in the same process share data that is allocated on the Heap (using malloc, new, calloc) and data that is in the Data segment (globals, literals and constants) Each thread has it's own memory to store local variables and parameters: this is called the Stack. Also: each thread keeps it's own CPU register values.

Cheers

Share on other sites
Spoonbender    1258
As MichaelWeber said, it also refers to a data structure.
Works pretty much like a real-world stack of, well, something, dishes, maybe? Or books or CD's, or anything else. You have two possible operations, push and pop. Push puts a new item on top of the stack. Pop takes the top one off. You can't just grab something from the middle of the stack, you have to deal with the top of it only. I bet you have a stack of CD's next to the computer. You can't just grab the bottom one, without taking the top ones off first. That's a stack. [wink]

The memory area the others explained about works in the same way (hence the name). Every new function pushes data onto the stack, and when the function ends, they're popped off, leaving the stack as it looked before the function was called.

Share on other sites
Guest Anonymous Poster
So if I make a function that takes a pointer as an argument. will that pointer be deleted after the function ends? or do I have to delete it myself at the end of the function.

-Mark

Share on other sites
Okay, I think I have a better idea of things. However I'm not quite sure here:

Quote:
 Original post by SpoonbenderEvery new function pushes data onto the stack, and when the function ends, they're popped off, leaving the stack as it looked before the function was called.

Do all variables within the function utilize the stack by default? If so, how could one access a variable that is defined before another variable, without "popping off" the previous variable, and losing that data?

Or perhaps the stack only applies to constants? Nilkn mentioned something about the heap, and static/dynamic data... is this what he/she is referring to?

Share on other sites
nobodynews    3126
I think that learning a lower level language(ie, assembly) would greatly facillitate understanding of the stack.

Share on other sites
wasted_druid    692
For beginning programming all you really need to know is that the stack is where your non-dynamic variables are stored, and the heap is where your dynamic allocation takes place.

That's when your stack is referring to memory. It's not really necessary to know how it's implemented yet (in my opinion). Just know that it works.

The stack can also be referring to a type of container. You push data onto the top, and to get stuff out you pop it off the top. It's Last In First Out.

*** Excerpt from "The Doctrine of Programming, According To wasted_druid"

Share on other sites
Spoonbender    1258
Quote:
Original post by redirectionkid
Okay, I think I have a better idea of things. However I'm not quite sure here:

Quote:
 Original post by SpoonbenderEvery new function pushes data onto the stack, and when the function ends, they're popped off, leaving the stack as it looked before the function was called.

Do all variables within the function utilize the stack by default? If so, how could one access a variable that is defined before another variable, without "popping off" the previous variable, and losing that data?

Well, that's where the similarity to a real-world stack ends. On a computer, it's just a bunch of memory addresses. If you have the address of something halfway down the stack, then you can manipulate it. The stack is just a method to be able to keep adding and removing data, always in a "first in-last out" order.

If a function is called with the address of another variable on the stack, then it won't be on top of the stack, but you have the address, so you can still read it or change its value.

On the other hand, when a function ends, all its data is popped off the stack, meaning that if you still have the address of a function variable (maybe you returned the address of a local variable?), then suddenly that points to nothing, to a semi-random value that's going to be overwritten as soon as someone push data onto the stack.

That's why you use 'new' to allocate memory. When you use new, you create a variable on the heap. It stays there until it's deleted.

When you just do something like this:

int x = 42;
it's created on the stack, and once the function ends, poof, the variable is gone.

Make sense? :P

Or to put it in code, imagine you call a function like this one:
int* foo(int* a){  // Now a points to something further down the stack (or maybe on the heap).  // If it's on the stack, it won't be popped off until the function it exists  // in ends, so it's safe enough to use here.  // Create a local variable and return the address of it.  // Of course, this goes out of scope when the function ends, so returning  // the address of it is *very* stupid. What happens is that when the function   // ends, it pops all the local variables (the ones created in this function   // without using 'new') off the stack, and suddenly, &b points to nothing in  // particular. It'll get overwritten any moment.  int b = 1;  return &b;}

Share on other sites
ernow    732
Quote:
 Do all variables within the function utilize the stack by default? If so, how could one access a variable that is defined before another variable, without "popping off" the previous variable, and losing that data?Or perhaps the stack only applies to constants? Nilkn mentioned something about the heap, and static/dynamic data... is this what he/she is referring to?

As said before 'ONLY' when you use malloc, calloc and new you are allocating memory on the HEAP. Local variables are stored on the Stack.

elements on the Stack can be addressed by index from the start of the frame; a frame contains variables bound to a scope or by using real addresses (not recommended as you can and might access data that does not exist or does not belong to you)

Cheers

Share on other sites
Okay so basicly you're saying that if you have an external pointer pointing to a variable that is local to a function, and that function terminates, the address of the actual variable is deleted, and thus your pointer would be pointing to some random location... all because that variable was stored on the stack.

But-

By using "new" you allocate space for a variable on the heap, where the variable will remain in the same location until "delete" is used, despite the life of the function with which the variable resides in.

Is that correct?

[EDIT: Well I guess it would be better to say that the value is deleted, not the address... so you're still pointing to the same address, just a random value that could change at any moment. Right?]

Share on other sites
Ra    1062
Quote:
 Original post by redirectionkidDo all variables within the function utilize the stack by default? If so, how could one access a variable that is defined before another variable, without "popping off" the previous variable, and losing that data?

If you're talking about two variables in the same function, one defined before the other, then a pointer to the base of the stack is stored.

Positive offsets from this base pointer are parameters or arguments passed to the function, already on the stack. Then the function's variables are pushed on the stack. These variables are accessed at negative offsets from the base pointer, so they don't actually have to be popped off the stack to be accessed.

Quote:
 Original post by redirectionkidBy using "new" you allocate space for a variable on the heap, where the variable will remain in the same location until "delete" is used, despite the life of the function with which the variable resides in.Is that correct?

Yes.

Share on other sites
Spoonbender    1258
Quote:
 Original post by redirectionkidOkay so basicly you're saying that if you have an external pointer pointing to a variable that is local to a function, and that function terminates, the address of the actual variable is deleted, and thus your pointer would be pointing to some random location... all because that variable was stored on the stack.

Pretty much. Of course, the address isn't deleted, but the place it points to is no longer reserved for that variable, so it might get overwritten any moment (or it might have been already)

Quote:
 By using "new" you allocate space for a variable on the heap, where the variable will remain in the same location until "delete" is used, despite the life of the function with which the variable resides in.

Yup.

You can try it for yourself.
Have a main function that calls first a function which returns the address of a local variable, and afterwards, call another function which is passed that address. Then try to read it. If the latter function takes up enough space on the stack, it'll overwrite the value, and if you try to print out the old variable then, you'll get some new garbage value.

Share on other sites
Guest Anonymous Poster
Quote:
Original post by Spoonbender
Quote:
Original post by redirectionkid
Okay, I think I have a better idea of things. However I'm not quite sure here:

Quote:
 Original post by SpoonbenderEvery new function pushes data onto the stack, and when the function ends, they're popped off, leaving the stack as it looked before the function was called.

Do all variables within the function utilize the stack by default? If so, how could one access a variable that is defined before another variable, without "popping off" the previous variable, and losing that data?

Ah, sounds like you've got it. :)

That's why you use 'new' to allocate memory. When you use new, you create a variable on the heap. It stays there until it's deleted.

I don't think you're following his question.

To the OP, be aware that there are two contexts here when we're speaking about a stacks: one is an abstract data type (ADT) while the other is related to how functions are executed in memory at the machine level.

In the ADT case, conceptually you can't access an item within the stack without popping items on top. You can do tricks like pushing the popped items onto another stack until you get to the item you wanted, process it (or whatever), and then pop the items from the second stack back onto the first.

The stack referred to when you're talking about function calls is not quite the same beast. When you enter a function, space for local variables are set aside in this stack region - i.e. you push a variable onto the stack. For the scope of the function call, you can access any of these variables (computer memory is randomly accessible after all). When the function goes out of scope, then the space you're used is no longer needed so these variables are popped. In this context, the stack refers to how we reserve memory for variables.

Hopefully I've explained this without confusing you further :)

Share on other sites
Saweet. I think I have grasped the general concept.

Now, it's time to put it to use.

Thanks everyone.

Share on other sites
Spoonbender    1258
Quote:
 Original post by Anonymous PosterI don't think you're following his question.

Agreed. I realized that and edited the post just after I first wrote it (You must have been pretty quick in quoting me. The unedited post wasn't up for more than a few minutes... :)