A. Stacks
This chapter introduces stacks and call stacks, which will help you understand block updates.
1 Understanding Stacks
A stack is a first-in-last-out (FILO) data structure, where elements can only be added or removed at one end.
1.1 First In Last Out
Imagine a Pringles can:
- Chips can only be placed in from the top, and can only be taken out from the top.
- Therefore, the chip placed at the bottom first will be the last one that can be taken out.
This is the "first in last out" principle.
1.2 Stack
A stack is like a Pringles can.
In data structure terminology:
- "Putting chips into the can" corresponds to push;
- "Taking chips from the top" corresponds to pop.
Additionally:
- The top of the can is equivalent to the top of the stack
- The bottom of the can is equivalent to the bottom of the stack
That's a stack.
2 Call Stacks
A call stack is a mechanism that programs use at runtime to manage function calls. It relies on the first-in-last-out rule to ensure functions return correctly.
3 How It Works
Imagine you're making phone calls to ask a question:
- You call your friend A to ask a question.
- A doesn't know the answer, so they call their friend B to ask.
- B isn't sure either, so they call their friend C to ask.
This time, C finds the answer and tells B first.
B then tells A.
Finally, A tells you the answer.
This follows the call stack pattern:
- Each phone call pushes a new "call task" onto the "call stack".
- When C is searching for the answer, the task at the top of the stack is "C searching for the answer".
- After C finds the answer, the most recent call completes first, then returns layer by layer to the callers (B → A → you).
- Your initial phone call was the first task pushed onto the call stack, so it sits at the bottom of the stack.
In a program:
- "Making a phone call" is equivalent to calling a function;
- "Getting an answer and passing it back" is equivalent to a function returning a result.
This way, when functions are nested, the program can ensure each function completes and returns to its caller correctly.