Menu
What do we call "stack" in Python? Is it the C stack of CPython? I read that Python stackframes are allocated in a heap. But I thought the goal of a stack was... to stack stackframes. What does the stack do then?
608
In Python, we can implement python stacks by: Using the built-in List data structure. Python's built-in List data structure comes with methods to simulate both stack and queue operations. Using the deque library which efficiently provides stack and queue operations in one object.
Why and When do we use Stack? Stacks are simple data structures that allow us to store and retrieve data sequentially. To understand Stack at the ground level, think about a pile of books. You add a book at the top of the stack, so the first one to be picked up will be the last one that was added to the stack.
A stack can be implemented using an array, a list, a pointer, etc. When it comes to a stack, there is a set of functions defined to use the stack efficiently in the programming context. In python, we can use a list data type as a built-in data type to implement the stack data structure.
A stack is an abstract data type that holds an ordered, linear sequence of items. In contrast to a queue, a stack is a last in, first out (LIFO) structure. A real-life example is a stack of plates: you can only take a plate from the top of the stack, and you can only add a plate to the top of the stack.
Python's stack frames are allocated on the heap. But they are linked one to another to form a stack. When function a calls function b, the b stack frame points to the a stack frame as the next frame (technically, a is the f_back attribute of the b frame.)
Having stack frames allocated on the heap is what makes generators possible: when a generator yields a value, rather than discarding its stack frame, it's simply removed from the linked list of current stack frames, and saved off to the side. Then when the generator needs to resume, its stack frame is relinked into the stack, and its execution continues.
75
Oversimplifying slightly:
In CPython, when PyEval_EvalFrameEx is evaluating a Python stack frame's code, and comes to a direct function call, it allocates a new Python stack frame, links it up… and then recursively calls PyEval_EvalFrameEx on that new frame.
So, the C stack is a stack of recursive calls of the interpreter loop.
The Python stack is a stack of Python frame objects, implemented as a simple linked list of heap-allocated objects.
They're not completely unrelated, but they're not the same thing.
When you use generators, this gets slightly more confusing, because those Python stack frames can be unlinked and relinked in different places when they're resumed. Which is why the two stacks are separate. (See Ned's answer, which explains this better than I could.)
5
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
