數(shù)組實(shí)現(xiàn)

 var cache: [Int] = []
let maxCount = 5 // 緩存最大值

extension Array where Element: Equatable {
    mutating func remove(_ object: Element) {
        if let index = index(of: object) {
            remove(at: index)
        }
    }
}

func LRU (data : Int){
    // 如果沒(méi)有緩存
    if !cache.contains(data) {
        // 數(shù)組滿(mǎn)了, 移除最后一個(gè)數(shù)據(jù)
        if cache.count == maxCount { cache.removeLast() }
    } else {
        cache.remove(data)
    }
    cache.insert(data, at: 0)
}

LRU(data: 1)
LRU(data: 2)
LRU(data: 3)
LRU(data: 4)
LRU(data: 5)

print(cache)

// 數(shù)組滿(mǎn)了
LRU(data: 6)
print(cache)

// 相同元素
LRU(data: 4)
print(cache)

輸出
[5, 4, 3, 2, 1]
[6, 5, 4, 3, 2]
[4, 6, 5, 3, 2]

鏈表實(shí)現(xiàn)

  class ListNode<T> {
    var value: T
    var previous: ListNode?
    var next : ListNode?
    init(_ value: T) {
        self.value = value
    }
}

class List<T> {
    typealias Node = ListNode<T>
    
    private var head: Node?
    private var tail: Node?
    
    // 判斷是否為空
    var isEmpty: Bool { return head == nil }
    
    // 獲取頭節(jié)點(diǎn)
    var first: Node? { return head }
    
    // 獲取尾節(jié)點(diǎn)
    var last : Node? { return tail }
    
    // 鏈表數(shù)量
    var count: Int = 0;
    
    // 下標(biāo)
    subscript(index: Int) -> T? {
        var i = index
        var next = head
        while i > 0 {
            i -= 1
            next = next?.next
        }
        return next?.value
    }
    
    // 插入尾部
    func insert(value : T) {
        
        let newNode = Node(value)
        
        if let first = head {
            newNode.next = first
            first.previous = newNode
            head = newNode;
        } else {
            head = newNode
            tail = newNode
        }
        count += 1
    }
    
    // 移除某個(gè)節(jié)點(diǎn)
    func remove(node: Node) {
        
        let pre = node.previous
        let next = node.next
        
        pre?.next = next
        next?.previous = pre
        
        if pre == nil { head = node.next }
        if tail == nil { tail = node.previous }
        
        count -= 1
    }
    
    // 移除最后一個(gè)節(jié)點(diǎn)
    func removeLast() {
        remove(node: last!)
    }
    
    // 移動(dòng)某個(gè)節(jié)點(diǎn)到頭部
    func moveToHead(node: Node) {
        
        let pre = node.previous
        let next = node.next
        
        pre?.next = next
        next?.previous = pre
        
        node.next = head
        head?.previous = node
        
        head = node
        
        if pre == nil { return }
        if next == nil  { tail = pre}
    }
}

class CacheLRU<T> {
    var limit : Int
    var cache : List<T>
    init(cacheCount: Int) {
        self.limit = cacheCount
        self.cache = List<T>()
    }
    
    // 添加數(shù)據(jù)
    func add(value: T) {
        if cache.count == limit { cache.removeLast()}
        cache.insert(value:value)
    }
    
    // 移動(dòng)數(shù)據(jù)
    func move(value: ListNode<T>) {
        cache.moveToHead(node: value)
    }
}

extension List where T == Dictionary<String, String> {
    // 判斷鏈表是否含有緩存
    func contains(name: String) -> Node? {
        var next = head
        var index = 0
        while index < count {
            if next?.value[name] != nil { return next }
            index += 1
            next = next?.next
        }
        return nil;
    }
    
    // 打印 log 信息
    func log() {
        var next = head
        while next != nil {
            print(next?.value as Any)
            next = next?.next
        }
    }
}

extension CacheLRU where T == Dictionary<String, String> {
    
    // 訪(fǎng)問(wèn)已有的數(shù)據(jù)
    func fetch(key : String) {
        let node = cache.contains(name: key)
        if let dic = node?.value {
            // 存在的話(huà), 直接取數(shù)據(jù)
            print(dic)
            
            // 移動(dòng)到頭節(jié)點(diǎn)
            move(value: node!)
        } else {
            
        }
    }
}

let cacheManager = CacheLRU<Dictionary<String, String>>(cacheCount: 2)
let value1 = ["1" : "測(cè)試1"]
let value2 = ["2" : "測(cè)試2"]
let value3 = ["3" : "測(cè)試3"]

// 模擬添加數(shù)據(jù)
cacheManager.add(value: value1)
cacheManager.add(value: value2)
cacheManager.add(value: value3)
cacheManager.cache.log()

// 模擬訪(fǎng)問(wèn)數(shù)據(jù)
cacheManager.fetch(key: "2")
cacheManager.cache.log()


輸出
添加數(shù)據(jù)
Optional(["3": "測(cè)試3"])
Optional(["2": "測(cè)試2"])
訪(fǎng)問(wèn)數(shù)據(jù)
["2": "測(cè)試2"]
Optional(["2": "測(cè)試2"])
Optional(["3": "測(cè)試3"])