a stack algorithm
Suppose you run the same program twice: once allowing it three frames of memory, once allowing four. You might hope that the four-frame run always keeps in memory everything the three-frame run did, plus one more page — that the bigger memory is a superset of the smaller. An algorithm for which this is always true, for every reference string and every point in time, is called a stack algorithm. The set of pages it holds with more frames always contains the set it would hold with fewer.
More precisely, a stack algorithm has the inclusion property: at every step of any reference string, the n pages it would keep with n frames are a subset of the n+1 pages it would keep with n+1 frames. Both LRU and optimal have this property — LRU because its choice depends only on recency of use (the n most-recently-used pages are always inside the n+1 most-recently-used), and optimal because its choice depends only on future use order. FIFO does not have it, because adding a frame can shuffle which pages are oldest in a way that breaks the nesting.
Why it matters: the stack property is the precise reason some algorithms cannot suffer Belady's anomaly. If the larger memory always contains everything the smaller one held, then every page that was a hit with n frames is still resident with n+1 frames, so adding frames can never turn a hit into a miss — faults can only stay the same or drop. So when you hear 'LRU is immune to Belady's anomaly,' the underlying reason is simply 'LRU is a stack algorithm.' The property also makes it possible to compute the fault count for all memory sizes in a single pass over the reference string.
With LRU at any moment, the 3 most-recently-used pages it keeps in 3 frames are always among the 4 most-recently-used it would keep in 4 frames. So nothing resident with 3 frames is ever missing with 4 — that nesting is the stack property, and it forbids Belady's anomaly.
Bigger memory contains smaller memory's pages — so more frames never add faults.
Being a stack algorithm is a sufficient guarantee against Belady's anomaly, not a description of how the algorithm picks victims. LRU and optimal qualify; FIFO does not, which is exactly why FIFO alone exhibits the anomaly in textbooks.