LRU Cache Using Queue

LRU (Least Recently Used) evicts the item that has not been used for the longest time. A queue models recency order from oldest (front) to newest (rear).

On this page

LRU concept and queue role
Operation flow
C demo with fixed capacity

1) Operation mapping

Event	Queue action
Cache hit(key)	Move key to rear (most recent)
Cache miss(key), space exists	Insert key at rear
Cache miss(key), cache full	Evict front (LRU), insert key at rear

2) Example in C

#include <stdio.h>

#define CAP 3

int q[CAP];
int n = 0;

// Find key position in current cache order; -1 means miss
int pos(int x) {
    for (int i = 0; i < n; i++) {
        if (q[i] == x) return i;
    }
    return -1;
}

// Touch key x: move to most-recent position (rear)
void touch(int x) {
    int p = pos(x);

    // Cache hit: shift left and move x to rear
    if (p != -1) {
        for (int i = p; i < n - 1; i++) {
            q[i] = q[i + 1];
        }
        q[n - 1] = x;
        return;
    }

    // Cache miss and free slot available
    if (n < CAP) {
        q[n++] = x;
        return;
    }

    // Cache miss and full: evict LRU (front), append x at rear
    for (int i = 1; i < CAP; i++) {
        q[i - 1] = q[i];
    }
    q[CAP - 1] = x;
}

// Print cache from oldest (front) to newest (rear)
void show(void) {
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d%s", q[i], (i + 1 == n) ? "" : ", ");
    }
    printf("]\n");
}

int main(void) {
    int seq[] = {1, 2, 1, 3, 4, 2};
    int m = 6;

    for (int i = 0; i < m; i++) {
        touch(seq[i]);
        show();
    }

    return 0;
}

Trace (capacity=3)

Access	Result	Queue (oldest → newest)
1	miss	[1]
2	miss	[1,2]
1	hit (move recent)	[2,1]
3	miss	[2,1,3]
4	miss + evict 2	[1,3,4]
2	miss + evict 1	[3,4,2]

3) Complexity note

Queue-only demonstration above uses O(C) search/shift where C is capacity.
Production LRU usually uses HashMap + Doubly Linked List for O(1) average get/put.

Key takeaway

Queue order captures recency intuitively: front is eviction candidate, rear is most recently used.