큐

선입선출(FIFO) 원리를 구현하는 자료구조입니다. 배열 기반 큐의 핵심은 front와 rear 포인터를 활용한 위치 관리입니다.

• front: 첫 번째 요소의 이전 위치를 가리킴
• rear: 마지막 요소 위치를 가리킴
• 삽입: rear 증가 후 요소 할당
• 삭제: front 증가 후 요소 반환

public class ArrayBasedQueue {
    private int[] elements;
    private int capacity;
    private int frontIdx;
    private int rearIdx;
    
    public ArrayBasedQueue(int size) {
        this.capacity = size;
        elements = new int[capacity];
        frontIdx = -1;
        rearIdx = -1;
    }
    
    public boolean isFull() {
        return rearIdx == capacity - 1;
    }
    
    public boolean isEmpty() {
        return rearIdx == frontIdx;
    }
    
    public void enqueue(int value) {
        if(isFull()) throw new IllegalStateException("Queue full");
        elements[++rearIdx] = value;
    }
    
    public int dequeue() {
        if(isEmpty()) throw new NoSuchElementException("Queue empty");
        return elements[++frontIdx];
    }
}

LRU 알고리즘

최근 사용 빈도가 낮은 데이터를 우선 제거하는 캐시 관리 기법입니다. 다양한 시스템에서 최적화된 형태로 적용됩니다.

• MySQL Buffer Pool: Young/Old 영역 분할로 예상失效 방지
  • innodb_old_blocks_pct: Old 영역 비율 설정
  • innodb_old_blocks_time: Young 영역 진입 임계시간
• Redis: 근사 LRU 구현
  • 임의 샘플링을 통한 효율적 제거
  • LFU(빈도 기반) 전략 추가 도입

연결 리스트

메모리 연속성을 요구하지 않는 선형 자료구조로, 삽입/삭제 연산에서 배열보다 효율적입니다.

단일 연결 리스트

class SinglyLinkedList {
    Node header = new Node(0, 0);
    
    void append(Node node) {
        Node current = header;
        while(current.next != null) {
            current = current.next;
        }
        current.next = node;
    }
    
    void insertOrdered(Node node) {
        Node current = header;
        while(current.next != null && current.next.id < node.id) {
            current = current.next;
        }
        node.next = current.next;
        current.next = node;
    }
}

class Node {
    int id;
    int value;
    Node next;
    
    public Node(int id, int value) {
        this.id = id;
        this.value = value;
    }
}

이중 연결 리스트

class DoublyLinkedList {
    Node head = new Node(0, 0);
    
    void add(Node node) {
        Node current = head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = node;
        node.prev = current;
    }
    
    void remove(Node target) {
        target.prev.next = target.next;
        if(target.next != null) {
            target.next.prev = target.prev;
        }
    }
}

class Node {
    int id;
    int value;
    Node prev;
    Node next;
}

환형 연결 리스트

class CircularList {
    Node first;
    
    void create(int count) {
        if(count < 1) return;
        first = new Node(1);
        first.next = first;
        Node current = first;
        
        for(int i = 2; i <= count; i++) {
            Node newNode = new Node(i);
            current.next = newNode;
            newNode.next = first;
            current = newNode;
        }
    }
}

Josephus 문제 해결

void resolveJosephus(int nodes, int start, int step) {
    Node current = first;
    Node prev = first;
    while(prev.next != first) {
        prev = prev.next;
    }
    
    for(int i = 0; i < start - 1; i++) {
        current = current.next;
        prev = prev.next;
    }
    
    while(current != current.next) {
        for(int j = 0; j < step - 1; j++) {
            current = current.next;
            prev = prev.next;
        }
        prev.next = current.next;
        current = current.next;
    }
}

스택

후입선출(LIFO) 원리를 구현하는 자료구조로, 배열 기반 구현 시 top 포인터로 상태를 관리합니다.

class ArrayStack {
    private int[] storage;
    private int topPointer = -1;
    private int maxSize;
    
    public ArrayStack(int size) {
        maxSize = size;
        storage = new int[maxSize];
    }
    
    boolean isFull() { 
        return topPointer == maxSize - 1; 
    }
    
    boolean isEmpty() { 
        return topPointer == -1; 
    }
    
    void push(int value) {
        if(isFull()) throw new StackOverflowError();
        storage[++topPointer] = value;
    }
    
    int pop() {
        if(isEmpty()) throw new EmptyStackException();
        return storage[topPointer--];
    }
}