stack and heap

[Jonathan100]

Hi,

I have some programming concepts question:

Why is stack (in context of stack and heap) considered LIFO (last in first out)?

The last time i checked, the program can access random memory inside the stack and manipulate it, without need to pull the predecessors memory cells

[kigar64551]

Because you generally manipulate the stack via the "push" and "pop" operations:

* The "push" operation adds one more element to the top of the stack and increments the stack-pointer accordingly.

* The "pop" operation removes and returns the top element from stack and decrements the stack-pointer accordingly.


Consequently, the last element that you added (pushed) to the stack, will be the first one that you take (pop) off the stack → LIFO.

However, this does not mean that you can not access (e.g. read) elements in the "middle" of the stack.

If you are able to figure out the address of an element in the "middle" of the stack, then you can read (or even overwrite) it directly.

But adding (or removing) elements to (or from) the stack is only possible at the current top of the stack!


Also note that, on the x86 architecture, the esp register always points to the "top" of the stack, and the stack "grows" downwards!

So, one x86 archtitecture, pop actually increments the stack-pointer, and push actually decrements the stack-pointer.

Also, the ebp register always points to the "stack frame", i.e. the address where the data for the current function begins in the stack.


Note that the stack pointer (esp) can also be incremented or decremented using the add and sub instructions.

For example, a typical function "prolog" looks like this:

push ebp        # backup "old" stack frame
mov  ebp, esp   # store current stack pointer as the new stack frame
sub  esp, N     # decrement stack pointer to reserve N bytes of additional stack space for the local variables 

The corresponding function "epilog" then looks like this:

mov esp, ebp    # restore "old" stack pointer value, which was stored as current stack frame value before
pop ebp         # restore "old" stack frame value that was backed up before
ret             # return from function 

See also:
https://en.wikibooks.org/wiki/X86_Disassembly/The_Stack
https://www.felixcloutier.com/x86/pop
https://www.felixcloutier.com/x86/push

[jonnin]

The "program stack" (the stack referred to when talking about the stack and the heap) is outside of c++ and is part of the model of how programs do things and how computers work.
some simplified words about what goes on with the computer's stack:
you call a function/method/subroutine (whatever your favorite word or flavor of the year is here) in c++. The (Lets call it the system, operating system and hardware and compiler generated code and assembly language commands all lumped together) "system" will "push" the current cpu set of registers, flags, and other values onto the stack, including its instruction pointer (where it is in the program at this moment) and so on. Then it pushes the local variables for the subroutine onto the stack too. Then it moves the instruction pointer to the subroutine and starts running the code there, modifying the local variables and doing whatever it does. Now that section of code may call another subroutine, and all that happens again... and after a bit the current subroutine finishes and the "system" pops the previous one off the stack. That replaces the instruction pointer and the code starts running from where it left off, ... gets to the end of that one and pops again, ... eventually its back in the main branch where it started and so on.

From that example, you can see that another use of stacks is to keep track of a state while you do something else and then come back to where you were. Stacks can be used for various pathing algorithms, like finding a way thorough a maze... you take a branch and if you get stuck, you can pop back to where you took the branch and try the next different path. The same can be said of traversing graphs(another data structure), trees, and similar things. Another example of keeping track, recursive functions use the system stack to do their work, which is like having a 'free' data storage area instead of having to create and manage it in your code.

in c++ you can also have a stack data structure (not the "system stack"). A *vector* in c++ lets you do as you said, mess with internal elements, or any element, yet it has push and pop features like a stack too. You can use the vector class as a stack, but its more than that, in other words. There is also a c++ stack object, that does not allow messing with the internal values (you may be able to look/read without modification, I forget).

Stacks as a data structure are not used a lot. The data structure is useful for a handful of algorithms, including parsing equations in reverse polish, for one common example that is different from the above.

Some of these things you may not have seen yet, or done much with. Its ok -- the high level concept is all you need, the description of how subroutines push and pop off the system stack is the key idea. Its not important that you can get inside the system stack somewhat (eg, change a variable's value that is stored on the stack even if its not the topmost) -- what is important is that it pushes and pops to control the flow of the program instructions.

[seeplus]

There is also a c++ stack object, that does not allow messing with the internal values (you may be able to look/read without modification, I forget).

If you want access to the internal values you have to derive a new class from stack (and queue). The internal data structure used is a protected member object of stack/queue so you can get access from the new derived class.