No Comprendo!
Author
I am trying to teach myself C++ using the book Teach Yourself C++ in 21 days. I have had some experience programming in basic, so everything was fairly understandable until the last part of chapter 5. It starts talking about memory and "pushing" or "popping off the stack" and that''s when I got lost. Anyone know where this is explained better or have some knowledge to share? There is also no application of this idea. The chapter just ends after talking about it and while I know it''s important to know about memory and other different things of the program to help it run faster I am not really making the connection of how this really helps. Any knowledge you would like to impart would be greatly appreciated...
Thanks,
Josh
If the world didn''t suck we would all fly off!
If you stick to high level C/C++ you don''t really have to worry about the stack, but it certainly helps in general. Stacks are a common data structure also, so that is another good reason to understand them. Here''s my attempt to explain them:
Stacks are a FILO (First In Last Out) data structure. The "top" element is the last one pushed onto it. If you pop the stack you remove from the top. So, if you pop one element from the stack, the top is gone. Here''s a stack.
If we pop one element, this is the new stack:
If we now push ''10'' onto the stack, it becomes this:
The way the CPU handles it is by pushing and popping a number of bytes on and off the stack. For example, in this C function:
The stack will need to be pushed sizeof(int) bytes at the beginning. So, if the stack looks like this before you call the function:
It may look like this during that function''s lifetime:
Then when the function ends, those sizeof(int) bytes are popped back off the stack, restoring it to the 3-2-1 example. Most (if not all) local variables that you create will be passed via the stack. There''s also lots of hidden variables passed on it (function addresses, function parameters, return values, et cetera). If you use dynamic allocation (new or malloc) you generally take space from the heap, that''s why those variables don''t die on the function''s return.
I hope that helped. If I explained everything you already knew, tell me what I should go over
.
Stacks are a FILO (First In Last Out) data structure. The "top" element is the last one pushed onto it. If you pop the stack you remove from the top. So, if you pop one element from the stack, the top is gone. Here''s a stack.
Top321BottomIf we pop one element, this is the new stack:
21If we now push ''10'' onto the stack, it becomes this:
1021The way the CPU handles it is by pushing and popping a number of bytes on and off the stack. For example, in this C function:
void Fish(void) { int a = 10;}The stack will need to be pushed sizeof(int) bytes at the beginning. So, if the stack looks like this before you call the function:
030201It may look like this during that function''s lifetime:
10 <- int a = 10;00 <- In little endian00 <- 32bit format.00 <-030201Then when the function ends, those sizeof(int) bytes are popped back off the stack, restoring it to the 3-2-1 example. Most (if not all) local variables that you create will be passed via the stack. There''s also lots of hidden variables passed on it (function addresses, function parameters, return values, et cetera). If you use dynamic allocation (new or malloc) you generally take space from the heap, that''s why those variables don''t die on the function''s return.
I hope that helped. If I explained everything you already knew, tell me what I should go over
.
quote:Original post by Null and Void
Stacks are a FILO (First In Last Out) data structure.
The correct way is LIFO - Last In First Out.
---
Make it work.
Make it fast.
"Commmmpuuuuterrrr.." --Scotty Star Trek IV:The Voyage Home
In order to understand stacks you must first understand arrays and how they work. So if you didn''t quite get them the first read through go back & take another look at them.
The above poster is correct in how a stack works. (LIFO) Last in First out. But perhaps a more real world example is needed for you to understand.
What is a stack? At it''s core it''s an array. And I''ve found that imagining an array as a bunch of kids Alphabet blocks stacked one on top of another is the best way to visualize it. What makes a stack different from an array is the way we input and output the values with it.
So lets visualize a stack. So back to my alphabet blocks example. We have a stack that can hold up to 26 values. Our alphabet blocks are lettered A-Z. Now, lets go grab a spring of some sort and put it onto the floor. Take your first alphabet block "A" and place it ontop of the spring then push it down. Hold your hand there as you grab your second alphabet block "B". Place B on top of A with out letting A pop off, and then push down again. Continue this process until you''ve got all the alphabet blocks stacked on top of eachother and your pushing the spring down. There your all done, you''ve "pushed" 26 values onto the stack. Now we''ve got a problem. We need to get all the values out of the stack one at a time. If we try to take "A" off first the spring will most likely come up too fast, and cause the rest of our alphabet blocks to fall to the ground, so thats definately not a solution. If we try to take a block out of the middle of the stack the same thing will happen. So our only course of action is to remove the "Z" block which is directly under your hand (Which is still pushing down on both the spring and the blocks). So slowly remove the Z block and place your hand on the "Y" block applying pressure to it so that the spring doesn''t propell more than 1 block off of the stack. There you''ve successfuly "Poped" off data from the stack.
So now that you''ve visualized what''s happening...you know that Push places a value onto the stack, and Pop removes one.
How many times to you use this in game programming? Well there are multiple reasons to use a stack in different algos and the like, but you''ll see the "Stack" when you start to do stuff in 3d. Both OpenGL and Direct3d, as well as wrappers for these two API''s have something they call a Matrix Stack. Matrix is just the name of the data the stack holds(you''ll learn about matricies later). This stack allows programmers to manipulate one or two objects in the world with out effecting the entire world as a whole. So it''s definately something you shouldn''t ignore or avoid because "I''ll never use it".
Hope this helps you out.
The above poster is correct in how a stack works. (LIFO) Last in First out. But perhaps a more real world example is needed for you to understand.
What is a stack? At it''s core it''s an array. And I''ve found that imagining an array as a bunch of kids Alphabet blocks stacked one on top of another is the best way to visualize it. What makes a stack different from an array is the way we input and output the values with it.
So lets visualize a stack. So back to my alphabet blocks example. We have a stack that can hold up to 26 values. Our alphabet blocks are lettered A-Z. Now, lets go grab a spring of some sort and put it onto the floor. Take your first alphabet block "A" and place it ontop of the spring then push it down. Hold your hand there as you grab your second alphabet block "B". Place B on top of A with out letting A pop off, and then push down again. Continue this process until you''ve got all the alphabet blocks stacked on top of eachother and your pushing the spring down. There your all done, you''ve "pushed" 26 values onto the stack. Now we''ve got a problem. We need to get all the values out of the stack one at a time. If we try to take "A" off first the spring will most likely come up too fast, and cause the rest of our alphabet blocks to fall to the ground, so thats definately not a solution. If we try to take a block out of the middle of the stack the same thing will happen. So our only course of action is to remove the "Z" block which is directly under your hand (Which is still pushing down on both the spring and the blocks). So slowly remove the Z block and place your hand on the "Y" block applying pressure to it so that the spring doesn''t propell more than 1 block off of the stack. There you''ve successfuly "Poped" off data from the stack.
So now that you''ve visualized what''s happening...you know that Push places a value onto the stack, and Pop removes one.
How many times to you use this in game programming? Well there are multiple reasons to use a stack in different algos and the like, but you''ll see the "Stack" when you start to do stuff in 3d. Both OpenGL and Direct3d, as well as wrappers for these two API''s have something they call a Matrix Stack. Matrix is just the name of the data the stack holds(you''ll learn about matricies later). This stack allows programmers to manipulate one or two objects in the world with out effecting the entire world as a whole. So it''s definately something you shouldn''t ignore or avoid because "I''ll never use it".
Hope this helps you out.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
