3、堆栈法
　　用栈顶至栈底的先后次序来记录Cache同一组内的各个块被访问的先后次序。栈顶是最近被访问过的块，栈底是最久没有被访问过的块。当要替换时，从栈顶压入新的块，很自然，最久没有被访问过的块就从栈的底部被挤出堆栈。如图5.32所示。
图 5.32 堆栈法的工作原理
　　堆栈法实际上是一种LRU替换算法，其管理规则为：把本次访问的块号与堆栈中保存的所有块号进行相联比较。如果发现有相等的，则Cache命中，这时，把本次访问的块号从栈顶压入，堆栈内各单元中的块号依次往下移，直至与本次访问的块号相等的那个单元为止，再往下的单元直止栈底都不变。如果没有发现相等的，则Cache块失效，这时，本次访问的块号从栈顶压入，堆栈内各单元的块号依次往下移，直至栈底。栈底单元中的块号被移出堆栈，它就是要被替换的块号。
　　因此，在堆栈法中，栈底永远保存着最久没有被访问过的块号，也就是下次要被替换出Cache的块号。
　　堆栈法的主要优点有两个。一是它的块失效率比较低，因为它采用了LRU算法。二是它的硬件实现相对比较简单，除了必须的寄存器之外，其它控制逻辑很简单。它的主要缺点是速度比较低，这是因为需要进行相联比较。因此，当每一组的块数比较大时，不宜采用堆栈法。

　　综上所述，对于Cache的替换算法，主要解决好以下三个问题：
　　(1) 记录每次访问Cache的块号。可以用寄存器，也可以用计数器，或者用其它方法。总之，在实现Cache替换算法时，必须要有时序逻辑。
　　(2) 管理好所记录的Cache块号。例如，排序、计数、清除、置位等。其目的是为找出被替换的块号提供方便。
　　(3) 根据记录和管理的结果，采用时序逻辑判断那个块号是将要被替换出去的块号。轮换法是要找出最早访问的块号，而另外三种方法都要找出最久没有被访问过的块号。