[알고리즘]리트코드 622_Design Circular Queue

리트코드 622

• 원형 큐 구현 문제
• 크기가 정해진 리스트에 head, tail을 갱신해가며 FIFO 배열을 만드는 문제
• head, tail 갱신 시 index = (index + 1) % capacity 로 갱신

원형 큐

배열 큐의 문제점

• deQueue() 할 때 O(n) 재배치 문제
  맨 앞 요소를 삭제하면 → 뒤의 모든 요소를 한 칸씩 앞으로 이동시켜야 한다.
  즉, deQueue()가 O(n)
  -> 선형 큐에서는 front, rear 로 해결
  

front/rear를 사용하는 선형 큐의 문제

• 데이터의 삽입과 삭제 반복 -> front, rear 계속 증가
  꺼낸 데이터가 있던 배열의 인덱스 사용 어려움, 인덱스 증가하다 배열의 사이즈 도달 시 사용어려움

원형 큐

• 배열의 양 끝을 연결해 원처럼 사용하는 큐
• head, tail 인덱스 갱신

index = (index + 1) % capacity;

• 배열 끝에 도달하면 0으로 돌아감
• 배열공간 원처럼 반복하여 사용
• 삽입/삭제 모두 O(1) → 인덱스만 이동
• 연결 리스트로 구현 시 head, tail 노드 따로 놓아 tail.next = head 같은 방식으로 구현

class MyCircularQueue {

    private int[] arr;
    private int head; // 가장 앞 요소 인덱스
    private int tail; // 가장 뒷 요소
    private int size; // 현재 들어있는 요소 개수.head== tail 일 때 처리(비어있음, 하나만 있음, 꽉참)
    private int capacity;  // 배열의 전체 크기

    public MyCircularQueue(int k) {
        this.capacity = k;
        this.arr = new int[k];
        this.head = 0;
        this.tail = -1;
        this.size = 0;
    }
    
    // 원소 추가, tail
    public boolean enQueue(int value) {
        if (isFull()) return false;
        
        tail = (tail + 1) % capacity;
        arr[tail] = value;
        size++;
        return true;
    }
    
    // 원소 제거, gead
    public boolean deQueue() {
        if (isEmpty()) return false;
        
        head = (head + 1) % capacity;
        size--;
        return true;
    }
    
    public int Front() {
        if (isEmpty()) return -1;
        return arr[head];
    }
    
    public int Rear() {
        if (isEmpty()) return -1;
        return arr[tail];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
}