[선형] Circular Queue

❒ Description

---

Design Circular Queue 문제를 풀면서 알게된 Circular Queue에 대해 학습한다.

긱포기 Circular Queue 포스팅을 참고했다.

 

 

 

❒ Circular Queue란?

---

Circular-Q는 normal-Q의 확장 버전으로 다음과 같은 특징을 갖고 있다.

• 마지막 요소(rear)와 첫 번째 요소(front)가 연결된 구조를 갖는다.
• 이런 구조로 인해 Buffer-Ring이라고 부르기도 한다.
• FIFO 원칙을 기반으로 한다.

 

 

❒ Operations of Circular-Q

---

1. Front

• Q의 앞쪽 요소를 반환한다.

2. Rear

• Q의 뒤쪽 요소를 반환한다.

3. enQueue(value)

• 새로운 요소를 삽입할 때 사용한다.
• 새로운 요소는 항상 rear 위치에 자리한다.

4. deQueue(value) 

• 요소를 제거할 때 사용한다.
• 항상 front 위치의 요소를 제거한다.

 

 

 

❒ Circular-Q 구현하기

---

Circualr-Q는 두 가지 방식(Array, Linked List)으로 구현할 수 있다. 

 

1. Array 사용

Design Circular Queue 문제를 풀 때 Array 방식을 사용함.

 

---

2. Linked List 사용

Linked Lista 방식으로 구현하기 위해서는 우선 Node 클래스를 만들어줘야 한다.

public class Node {
    private int val;
    private Node next;
    
    public Node(int val) {
    	this.val = val;
        this.next = null;
    }
}

 

 

다음으로는 `enQueue()`가 필요하다.

public void enQueue(int val) {
    Node n = new Node(val);
	if (isEmpty()) {
    	n.next = n;
    } else {
    	n.next = rear.next;
        rear.next = n;
    }
    rear = n;
}

 

 

마지막으로 `deQueue()`가 필요하다.

public void deQueue() {
    if (isEmpty()) {
    	throw new EmptyQueueException();
    }
    int popElement = rear.next.val;
    if (rear.next == rear) {
    	rear = null;
    } else {
    	rear.next = rear.next.next;
    }
    return popElement;
}

 

 

그 외의 메소드들은 다음과 같다.

public int peek() {
    if (isEmpty()) {
    	throw new EmptyQueueException();
    }
    return rear.next.val;
}

public boolean isEmpty() {
    return rear == null;
}

 

 

 

❒ Circular-Q는 어떻게 쓰이고 있을까?

---

 

1. Memory Management

Q의 마지막 부분에 도달하면 처음 부분으로 돌아와 빈자리를 채우기 때문에, 메모리를 효율적으로 사용할 수 있다.

 

2. Traffic System

Circular-Q를 사용하면 traffic-lights의 상태를 순환 시키면, 각 light가 반복적으로 켜질 수 있다.
예를 들어 4개의 신호등이 있다고 가정하면, Circular-Q를 사용하면 첫 번째 신호등이 켜진 후
두 번째, 세 번째, 네 번째 신호등이 차례로 켜지고 다시 첫 번째 신호등으로 돌아오는 식으로 제어할 수 있다.

 

3. CPU Scheduling

프로세스들이 차례재로 CPU에 할당되어 처리되므로 공평하게 CPU 시간을 배분할 수 있다.

 

---

 

이렇게 Circular-Q는 메모리 효율성을 높이고, 일정한 순환이 필요한 시스템에 매우 유용하게 사용된다.