stack and heap
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
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
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
So, one x86 archtitecture,
Also, the
Note that the stack pointer (
This means that you do not need to push elements "one by one", but you can reserver stack space for N elements in one instruction.
Similarily, when no longer needed, the top N elements can be removed from the stack in one instruction.
For example, a typical function "prolog" looks like this:
The corresponding function "epilog" then looks like this:
See also:
https://en.wikibooks.org/wiki/X86_Disassembly/The_Stack
https://www.felixcloutier.com/x86/pop
https://www.felixcloutier.com/x86/push
* 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.This means that you do not need to push elements "one by one", but you can reserver stack space for N elements in one instruction.
Similarily, when no longer needed, the top N elements can be removed from the stack in one instruction.
For example, a typical function "prolog" looks like this:
|
|
The corresponding function "epilog" then looks like this:
|
|
See also:
https://en.wikibooks.org/wiki/X86_Disassembly/The_Stack
https://www.felixcloutier.com/x86/pop
https://www.felixcloutier.com/x86/push
Last edited on
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.
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.
Last edited on
| 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.
Thanks for the elaborated comments!
So if I understands it right, the "program stack" has nothing to do with the data type that called stack?
So if I understands it right, the "program stack" has nothing to do with the data type that called stack?
Last edited on
| So if I understands it right, the "program stack" has nothing to do with the data type that called stack? |
I would not say "has nothing to do with" 😏
A "stack", in general, is an abstract data structure, of which many different concrete implementations exist!
Stack data structures are used in many different applications for many different purposes.
The "program stack" (call stack), which is used by the processor to maintain information about the active function/subroutine (separetly for each thread) – e.g. it is used for allocating the local variables – is just one incarnation of a "stack" data structure.
"Stack" implementations that you find in "high-level" programming languages, such as the
std::stack class in C++, the java.util.Stack class in Java, or the System.Collections.Stack class in C#, serve different purposes than the processor's call stack – they allow the programmer to store a collection of objects with LIFO semantics – but the underlying concept of a "stack" structure is exactly the same!See also:
Stack as an abstract data structure, which is not a concrete implementation but a general concept:
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
The processor's call stack, which is one concrete implementation of a "stack" for one specific purpose:
https://en.wikipedia.org/wiki/Call_stack
Stack (LIFO collection) implementations exist in various programming languages:
https://en.cppreference.com/w/cpp/container/stack
https://learn.microsoft.com/en-us/dotnet/api/system.collections.stack?view=net-9.0
https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html
Last edited on
the program stack is rather different in the "implementation details"* from a C++ built in stack data type or the ones described in a book. They have some similar behaviors, else they would not be "stacks" but a stack has very few requirements... its basically enough to call something a stack if it supports a push and pop operation (regardless of what else it can or cannot do).
** for example if you and I wrote a stack from scratch in c++ (just for the heck of it, as the language has one you should use instead), lets say you built yours with a linked list, stuffing the new items on 'top' as 'push', and lets say I used a vector, which has built in push/pop operations so I just hide the other stuff vector can do and hand you a limited vector that looks and acts like a stack. Yours and mine can both push and pop, though, and are both "stacks" though totally different internally. That is the implementation details! Also, I could provide a function to look at all the elements, you not do that, such that mine does more than yours, yet both are still stacks, but now they have slightly different behaviors. None of that matters. What matters is little more than whether they support push and pop, and if they do, they are conceptually stacks, or can be seen as such in some contexts (like a vector isn't meant to be a stack, but you can use it as one or call it one and that is correct).
Its all just the high level concept, and for a stack, that is a very small and simple requirement, anything above and beyond the requirement is irrelevant.
way down in the weeds, the program stack pushes and pops a "data type" that is often called the "stack frame". But keep in mind that not all languages and code have hard objects (OOP) and types. C++ can even be written this way, sometimes called procedural programming. In assembly language, you have a lump of bytes, store junk in offsets into it, and manhandle the memory blob directly or passing it around to routines, and when you call routines they know what offsets mean what and modify the values there, etc, and all that is hidden in c++ but its what happens down in the compiled code. All the OOP stuff is a programming tool and the CPU/assembly level execution of code doesn't have that kind of organization. A CPU can only hold a few things at once, like 3-4 variable values, maybe 10 for floating point area, but nothing like the 20+ in most objects in c++.
** for example if you and I wrote a stack from scratch in c++ (just for the heck of it, as the language has one you should use instead), lets say you built yours with a linked list, stuffing the new items on 'top' as 'push', and lets say I used a vector, which has built in push/pop operations so I just hide the other stuff vector can do and hand you a limited vector that looks and acts like a stack. Yours and mine can both push and pop, though, and are both "stacks" though totally different internally. That is the implementation details! Also, I could provide a function to look at all the elements, you not do that, such that mine does more than yours, yet both are still stacks, but now they have slightly different behaviors. None of that matters. What matters is little more than whether they support push and pop, and if they do, they are conceptually stacks, or can be seen as such in some contexts (like a vector isn't meant to be a stack, but you can use it as one or call it one and that is correct).
Its all just the high level concept, and for a stack, that is a very small and simple requirement, anything above and beyond the requirement is irrelevant.
way down in the weeds, the program stack pushes and pops a "data type" that is often called the "stack frame". But keep in mind that not all languages and code have hard objects (OOP) and types. C++ can even be written this way, sometimes called procedural programming. In assembly language, you have a lump of bytes, store junk in offsets into it, and manhandle the memory blob directly or passing it around to routines, and when you call routines they know what offsets mean what and modify the values there, etc, and all that is hidden in c++ but its what happens down in the compiled code. All the OOP stuff is a programming tool and the CPU/assembly level execution of code doesn't have that kind of organization. A CPU can only hold a few things at once, like 3-4 variable values, maybe 10 for floating point area, but nothing like the 20+ in most objects in c++.
Last edited on
kigar64551,
I guess that you are talking about "program stack"
If this is the case, why is it actually considered a stack and not array?
[And I guess that in stack data type u cannot access the middle of the stack]
| 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. |
I guess that you are talking about "program stack"
If this is the case, why is it actually considered a stack and not array?
[And I guess that in stack data type u cannot access the middle of the stack]
| I guess that you are talking about "program stack" |
Yes. But not only!
There may be other implementations of a "stack" data structures that, too, allow you to access elements in the "middle" of the stack.
For example, in Java, the
Stack class actually extends the Vector class. And the Vector class has a get() method to get elements by index. Consequently, since Java's Stack class is derived from the Vector class, the Stack class exposes the get() method too! In other words, we can use push() and pop() to add or remove elements, but we can also access all existsing elements by index via the get() method.Example:
https://pastebin.com/nh9YUAAQ
https://pastebin.com/BZK6fyaK
| If this is the case, why is it actually considered a stack and not array? |
Because a "stack" is an abstract data type.
There are many different ways how a "stack" can be implemented, and the details of different implementations differ!
Using an array is actually one common way to implement a "stack" data structure:
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)#Array 😏
In other words, a (bounded-size) "stack" may be thought of as an array that has an additional variable (counter) in order to keep track of the index of the current "top" element, so that the
push() and pop() operations can be implemented with the usual "stack" semantics.BTW: Implementing a "stack" as a linked-list is a possible alternative to using an array. There may be others!
| And I guess that in stack data type u cannot access the middle of the stack |
Totally depends on the concrete implementation !!!
With C++'s
std::stack you can not access elements in the "middle". At least not without deriving your own sub-class 😏But, with Java's
Stack class, for example, you can access arbitrary elements by index. See my example above!Python has no dedicated "stack" type, but a normal Python list supports
pop() to remove and return its last element. Thus, you can use a Python list as a "stack" via the append() and pop() methods, but of course you may also access any element by its index.
Last edited on
Registered users can post here. Sign in or register to post.