LIFO Cache: bản chất, thuật toán ngăn xếp và cách hoạt động

LIFO Cache là gì?

LIFO Cache (Last In First Out Cache) là bộ đệm có kích thước cố định được triển khai trên ngăn xếp. Khi một phần tử mới được thêm vào bộ đệm đầy, phần tử gần đây nhất (đỉnh) bị xóa và phần tử mới chiếm vị trí của nó. Tên gọi “Last In First Out” có nghĩa là phần tử vào bộ đệm sau cùng sẽ bị loại bỏ đầu tiên.

Chính sách này khác biệt hoàn toàn so với LRU và FIFO. Trong khi LRU cố gắng giữ dữ liệu liên quan nhất (theo thời gian truy cập cuối) và FIFO bảo toàn “tuổi” dữ liệu, thì LIFO hy sinh dữ liệu mới một cách có chủ ý. Điều này có vẻ phản trực quan đối với lưu trữ đệm, nhưng đối với một số kịch bản, LIFO lại là giải pháp tối ưu.

Triển khai LIFO Cache cổ điển sử dụng ngăn xếp dựa trên mảng hoặc danh sách liên kết. Mảng cung cấp lưu trữ nhỏ gọn và tính cục bộ bộ đệm nhưng yêu cầu cấp phát bộ nhớ trước cho maxSize. Danh sách liên kết linh hoạt hơn, nhưng mỗi phần tử yêu cầu thêm bộ nhớ cho con trỏ (8–16 byte mỗi phần tử).

Các thao tác cơ bản của LIFO Cache

Thao tác push(value) thêm phần tử vào đỉnh ngăn xếp. Nếu kích thước đạt maxSize, đỉnh sẽ bị xóa trước khi chèn. Thao tác pop() xóa và trả về phần tử trên cùng — hữu ích cho các kịch bản “hoàn tác hành động cuối cùng”. Thao tác peek() trả về phần tử trên cùng mà không xóa — để xem trạng thái đã lưu cuối cùng mà không thay đổi ngăn xếp.

Cách hoạt động của LIFO Cache

Nguyên lý hoạt động của LIFO Cache cực kỳ đơn giản: tất cả các thao tác được thực hiện trên một đầu của cấu trúc — đỉnh ngăn xếp. Khi một phần tử mới được thêm vào, nó được đặt lên đỉnh. Nếu ngăn xếp đầy, phần tử trên cùng bị đẩy ra (xóa) và phần tử mới chiếm vị trí của nó. Việc loại bỏ luôn chỉ ảnh hưởng đến một phần tử — đỉnh — vì vậy thuật toán không yêu cầu lặp hay tìm kiếm.

Thuộc tính này làm cho LIFO Cache nhanh nhất trong tất cả các chính sách loại bỏ: tất cả các thao tác chạy trong O(1) mà không cần bất kỳ cấu trúc dữ liệu bổ sung nào. Không cần bảng băm để tra cứu, không cần danh sách liên kết đôi để sắp xếp lại — chỉ cần một con trỏ đơn giản đến đỉnh ngăn xếp. Tiêu thụ bộ nhớ là tối thiểu: chỉ lưu trữ các phần tử.

Tuy nhiên, sự đơn giản có mặt trái: LIFO Cache không xem xét tần suất hoặc thời gian truy cập cuối vào dữ liệu. Nếu một ứng dụng yêu cầu dữ liệu A, B, C trước và sau đó lại yêu cầu A, thì C (được thêm cuối cùng) sẽ bị loại bỏ khi bộ đệm đầy, ngay cả khi A không còn liên quan. Đối với các kịch bản lưu trữ đệm chung, điều này làm cho LIFO trở thành lựa chọn tồi nhất, vì dữ liệu mới thường có giá trị nhất.

Kích thước ngăn xếp và quản lý bộ nhớ

Đối với LIFO Cache dựa trên mảng, kích thước được đặt khi tạo và không thay đổi động. Nếu ngăn xếp đầy và push xảy ra, phần tử trên cùng bị ghi đè. Đối với triển khai danh sách liên kết, bộ nhớ được cấp phát cho mỗi phần tử khi cần, nhưng khi đạt giới hạn, nút cũ bị tách ra và có thể được thu gom bởi trình thu gom rác. Trong các ứng dụng di động, nên sử dụng mảng cho LIFO Cache vì nó không tạo thêm tải cho GC.

LIFO so với LRU và FIFO: So sánh chiến lược

Việc chọn chiến lược loại bỏ ảnh hưởng trực tiếp đến hiệu quả lưu trữ đệm. LIFO, LRU và FIFO đại diện cho các cách tiếp cận khác nhau cho cùng một câu hỏi: xóa phần tử nào khi bộ đệm đầy. Mỗi cách tiếp cận là tối ưu cho loại tác vụ riêng của nó.

LRU thường cung cấp tỷ lệ truy cập tốt nhất nhưng yêu cầu nhiều bộ nhớ hơn và phức tạp hơn để triển khai. FIFO là sự dung hòa giữa hiệu suất và tỷ lệ truy cập, hữu ích cho dữ liệu phát trực tuyến. LIFO là đơn giản nhất nhưng có tỷ lệ truy cập thấp: chỉ nên sử dụng khi ngữ nghĩa “vào sau ra trước” phù hợp với logic nghiệp vụ (điều hướng, thao tác hoàn tác).

Nơi sử dụng LIFO Cache

Mặc dù phù hợp hạn chế cho lưu trữ đệm chung, LIFO Cache được sử dụng trong các kịch bản cụ thể nơi thứ tự xử lý dữ liệu ngược với thứ tự đến. Hãy xem xét các trường hợp chính.

Ngăn xếp điều hướng

Trong các ứng dụng di động, ngăn xếp điều hướng được sử dụng: khi một màn hình mới được mở, nó được đặt lên đỉnh ngăn xếp; khi nút “Quay lại” được nhấn, nó bị xóa. Nếu độ sâu ngăn xếp bị giới hạn (ví dụ: tối đa 10 màn hình), LIFO Cache sẽ tự động loại bỏ màn hình gần đây nhất khi vượt quá giới hạn. Điều này cho phép kiểm soát mức tiêu thụ bộ nhớ của ngăn xếp điều hướng mà không mất các màn hình đã mở trước đó.

Ngăn xếp Hoàn tác/Làm lại

Cơ chế hoàn tác (Undo) là một ví dụ kinh điển về LIFO. Mỗi hành động của người dùng được lưu trong ngăn xếp. Khi Undo được gọi, hành động cuối cùng bị hoàn tác và chuyển sang ngăn xếp Làm lại. Giới hạn kích thước ngăn xếp qua LIFO Cache đảm bảo rằng khi vượt quá giới hạn, các hành động cũ nhất (ở đáy ngăn xếp) vẫn còn trong khi các hành động gần đây nhất bị loại bỏ — điều này hợp lý vì người dùng thường hoàn tác các hành động gần đây trong khi các hành động cũ không còn liên quan.

Bộ đệm tính toán tạm thời

Trong các tính toán đệ quy có quay lui (backtracking), kết quả của các bước trung gian được lưu theo thứ tự LIFO. Khi bộ đệm tràn, kết quả cuối cùng bị loại bỏ — điều này có thể chấp nhận được vì thuật toán có thể tính toán lại nếu cần. Cách tiếp cận này được sử dụng trong trình phân tích cú pháp, trình biên dịch và thuật toán duyệt đồ thị có giới hạn độ sâu.

Ví dụ mã LIFO Cache

Hãy xem xét triển khai LIFO Cache trong Kotlin sử dụng mảng kích thước cố định. Mảng cung cấp hiệu suất tốt nhất và mức tiêu thụ bộ nhớ tối thiểu cho thiết bị di động.

class LifoCache<V>(
    private val maxSize: Int
) {
    private val array = arrayOfNulls<V>(maxSize)
    private var top = -1

    fun push(value: V) {
        if (top == maxSize - 1) {
            top--  // discard oldest when full
        }
        array[++top] = value
    }

    fun pop(): V? {
        if (top == -1) return null
        val result = array[top]
        array[top--] = null
        return result
    }

    fun peek(): V? {
        return array[top]
    }
}

Chỉ mục top trỏ đến đỉnh ngăn xếp. push tăng top và ghi giá trị; nếu mảng đầy (top == maxSize - 1), top bị giảm trước khi ghi — đỉnh ngăn xếp bị ghi đè, triển khai việc loại bỏ LIFO. Phương thức pop trả về phần tử và giảm top, trong khi peek chỉ đọc phần tử trên cùng mà không thay đổi ngăn xếp.

Ví dụ: Ngăn xếp điều hướng với LIFO Cache

Xem xét việc sử dụng LIFO Cache để giới hạn độ sâu điều hướng trong Jetpack Compose. Khi một màn hình mới được mở, nó được thêm vào ngăn xếp và khi vượt quá giới hạn, màn hình gần đây nhất bị loại bỏ.

class NavigationStack(maxDepth: Int = 10) {
    private val cache = LifoCache<Screen>(maxDepth)

    fun navigateTo(screen: Screen) {
        cache.push(screen)
    }

    fun goBack(): Screen? {
        return cache.pop()
    }

    fun currentScreen(): Screen? {
        return cache.peek()
    }
}

Trong ví dụ này, NavigationStack sử dụng LIFO Cache để lưu trữ lịch sử màn hình. Khi navigateTo được gọi, màn hình được thêm vào ngăn xếp; khi goBack được gọi, màn hình cuối cùng bị xóa. Nếu người dùng đã mở 11 màn hình với giới hạn 10, màn hình gần đây nhất (thứ 11) sẽ loại bỏ màn hình trước đó (thứ 10) — màn hình đầu tiên vẫn ở trong ngăn xếp, phù hợp với mong đợi của người dùng khi điều hướng quay lại. Chiến lược này hiệu quả hơn LRU cho điều hướng: xóa các màn hình đã mở từ lâu (“trang chủ”, “hồ sơ”) sẽ dẫn đến hành vi không mong muốn.