Base CS from zero
Stack and heap
Memory is one long row of byte-addressed cells — that much you know. But a program does not use those cells randomly. If you looked at the addresses a running program actually touches, you would see a clear pattern: some addresses cluster near the top, some near the bottom, and the middle is barely used at all.
This is not an accident. The operating system and the CPU agree to divide the address space into named regions, each with a different purpose and a different lifetime. The two most important regions are the stack and the heap. Understanding them is understanding how every program you will ever write manages its memory.
After this lesson you can describe the address space as divided into regions, explain what the stack region is and why it grows and shrinks as functions run, explain what the heap region is and why it holds long-lived data, and state that both regions are parts of the same physical memory.
The address space: the program’s view of memory. A running program does not see raw hardware memory directly. The operating system gives each program a private view of memory called its address space — a range of addresses (for example, 0 to 2^64 − 1 on a 64-bit OS) that the program can use. The OS manages the mapping from this virtual view to actual physical RAM.
Within the address space, the OS and the language runtime agree on a layout: certain address ranges are reserved for certain purposes. The exact layout varies between operating systems, languages, and architectures, but the stack and the heap appear in every major language and OS, always playing the same roles.
The stack region: memory that grows and shrinks with function calls. The stack is a region of the address space that is managed automatically. Each time a function is called, the system reserves a small block of cells for that function’s exclusive use — this block is called a stack frame (or activation record). The frame holds the function’s local variables, its parameters, and bookkeeping information (like the return address — where execution should continue after the function finishes).
When the function returns, its frame is discarded: those cells become available for reuse immediately. The stack therefore grows as functions call other functions and shrinks as they return. At any moment, the stack contains exactly the frames of all the functions currently running — the call chain from the outermost function down to the current one.
The stack is last-in-first-out (LIFO). The order in which frames are added and removed follows a strict rule: the frame added most recently is always the first to be removed. This is called last-in-first-out (LIFO). Think of a stack of plates: you add new plates to the top and always take the top plate off first. The bottom plate is the last to leave.
On the stack:
- When function A calls function B, B’s frame is added on top of A’s frame.
- When B returns, B’s frame is removed — A’s frame is now on top again.
- A’s frame was there before B’s and outlives B’s, just as the bottom plate predates and outlives the top plate.
This LIFO order is not a design choice made once — it is the consequence of how function calls nest: the most recently called function must finish before the caller can continue.
The heap region: memory that outlives a single function call. The heap is a
region of the address space for data that needs to exist beyond the duration of a single
function call. Unlike the stack, the heap is not managed automatically. A program
explicitly requests a block of cells from the heap (using calls like malloc in C or
new in Java/C++) and later explicitly releases it (using free or delete, or relying
on a garbage collector — a part of the language runtime that automatically reclaims
heap blocks the program no longer uses).
Because heap data can outlive the function that created it — and because multiple functions can hold pointers to the same heap object — the heap has no simple LIFO order. It can contain a patchwork of used and free blocks of different sizes, created and freed at different times.
Why this works
Why have two regions at all? Why not just one?
The stack is extremely fast for the common case: a function’s data lives exactly as long as the function runs, so the system can allocate and free frames with a single pointer movement — it just adjusts one number (the “stack pointer”) up or down. No searching, no bookkeeping about what is free.
The heap handles everything the stack cannot: data that must outlive its creator, large objects whose size is not known until the program runs, objects shared between many functions. Heap allocation and deallocation are more expensive because the allocator must find and track available blocks. Two regions let the program pay the lower cost when stack lifetimes suffice and the higher cost only when necessary.
Both regions are the same physical memory. The stack and the heap are not different hardware components. They are both address ranges within the same flat row of byte- addressed cells you learned about in the first lesson of this unit. The difference is entirely in how they are managed and how long their data lives, not in what the underlying cells are.
On a 64-bit Linux process, for example, the stack occupies a region near the top of the address space and the heap occupies a region near the bottom. Both are backed by the same RAM chips. The operating system and the program cooperate to ensure they do not overlap (if the stack grows so large it collides with the heap, you get a stack overflow error).
Tracing stack frames through a simple call chain.
Consider a program where function main calls function add, which calls no one else.
Initial state — only main is running.
Stack contains: [main frame]
The main frame holds main’s local variables.
main calls add.
Stack contains: [main frame] [add frame]
The add frame is pushed on top. It holds add’s parameters and local variables. Main is
suspended — its frame is still there, waiting.
add returns.
The add frame is popped (discarded). The cells it occupied are free to be reused.
Stack contains: [main frame]
Main resumes from where it left off. The return value of add is passed back to main
(through a register, typically), not through a long-lived cell.
main returns.
The main frame is popped.
Stack contains: [] (empty)
The process ends.
At no point did any frame survive longer than the function it belonged to. That is the defining property of the stack.
Meanwhile, if add had created a large data structure on the heap, that structure would
still exist in the heap after add returned — as long as main (or some other code) held
a pointer to it. The heap data outlives the function; the stack frame does not.
Edge cases
Stack overflow. The stack region has a finite size set by the OS (typically 1–8 MB). If a program calls functions so deeply — especially through unbounded recursion — that the stack grows past its limit, it crashes with a “stack overflow” error. This is not a logical error in the program’s algorithm; it is a physical limit of the reserved address range. Recursive algorithms that go millions of levels deep need iterative rewrites or explicit heap-allocated data structures to avoid this.
Function A calls function B, which calls function C. How many stack frames are on the stack while C is executing?
Function C returns. How many stack frames remain on the stack?
The stack follows LIFO order. Which frame is removed first: the frame of the first function called, or the frame of the most recently called function?
A heap object is created inside function X. After X returns, can the object still exist in memory? Type 1 for yes, 0 for no.
Are the stack and the heap physically different hardware chips? Type 1 for yes, 0 for no.
What is the key difference between stack memory and heap memory?
The program’s address space is divided into regions. The stack region is automatically managed: each function call adds a stack frame containing the function’s local data, and that frame is discarded when the function returns. Frames are added and removed in LIFO order (last in, first out) — the most recently entered function is always the first to leave. The heap region holds data that outlives individual function calls; it is explicitly allocated and freed (or garbage collected), with no fixed order of creation and destruction. Both regions are parts of the same flat byte-addressed memory — they are address ranges in the same RAM, differing only in management strategy and data lifetime.