LRU算法，全稱Least Recently Used，即最近最少使用算法，是一種常用的快取淘汰策略。以下是該算法的詳細介紹：
定義和套用。LRU算法通過維護一個動態的訪問順序來決定哪些數據應該被保留在快取中，哪些數據應該被淘汰。當快取達到其最大容量時，最近最久未使用的數據（即最長時間未被訪問的數據）將被淘汰。這種策略假設了局部性原理，即如果數據在最近被訪問過，那麼將來很可能再次被訪問。因此，最近訪問過的數據（即最接近佇列頭部的數據）被認為更有價值，而佇列尾部的數據則被視為較不重要的數據。
實現方式。LRU算法可以通過多種數據結構實現，常見的包括鍊表和哈希表。在鍊表中，節點表示快取中的條目，節點的訪問時間通過其在鍊表中的位置來表示。哈希表用於快速查找節點，無論節點在鍊表中的位置如何。當快取命中（即訪問的鍵已經在快取中）時，對應的節點被移動到鍊表的頭部，表示它最近被訪問過。當快取未命中且快取未滿時，新節點被添加到鍊表的頭部。當快取已滿時，鍊表尾部的節點（即最久未使用的節點）將被淘汰，然後新節點被添加到鍊表的頭部。
優點和局限性。LRU算法的優點包括實現簡單、適應性強以及良好的性能。它能夠有效地減少缺頁中斷次數，從而減少系統開銷。然而，LRU算法也有其局限性，比如對於非周期性訪問模式的快取來說，其性能可能並不理想。此外，LRU算法需要維護一個額外的數據結構（如鍊表）來記錄訪問順序，這可能會增加一定的開銷。
綜上所述，LRU算法是一種有效的快取淘汰策略，適用於多種場景，尤其是在記憶體管理和快取管理中。