안녕하세요. 이전 포스팅에이어서 오늘은 원형 큐에 대해서 공부한 내용을 공유해보고자 합니다.
원형 큐는 일반적인 선형큐의 단점을 보완한 확장 개념입니다. 우선, 선형큐에 대해 간단히 복습해보겠습니다. 선형큐는 배열이나 링크드 리스트로 구현할 수 있지만, 배열로 구현할때 다음과 같은 문제가 발생할 수 있습니다.
- 비효율적인 요소이동 : 요소를 삽입하거나 삭제 할때마다 모든 요소를 앞으로 혹은 뒤로 밀어야 합니다.
- 공간 낭비 : 삭제된 요소의 자리를 재활용하지 않으면, 앞 공간이 계속 비어있게 되어 큐가 비어있지 않더라도, 새요소를 삽입할 수 없게 됩니다.
이러한 문제를 해결하기 위해서 원형큐가 도입되었습니다. 원형 큐는 큐의 마지막 포인터(rear)를 첫 번째 포인터(front)와 연결하여 끝과 끝이 이어진 원형 구조를 만들어 공간을 효율적으로 활용합니다.
원형 큐의 특징은 다음과 같습니다.
- 원형 구조 : rear기 배열의 끝에 도달하여도 front가 가리키는 요소로 되돌하가서 비어있는 공간을 더 사용할 수 있습니다.
- 공간 낭비 : 삭제된 요소의 공간을 재활용하기 때문에 메모리를 최적화 할 수 있습니다.
enQueue 연산
- Queue가 이미 가득 차 있는지 확인 합니다.
- 큐가 비어있다면 front와 rear을 0으로 초기화 합니다.
- 그렇지 않다면, 한칸 이동 시키되, 원형으로 처리하기 위해 다음 수식을 rear에 대입합니다. rear = (rear +1) % MaxSize
- rear의 위치에 queue에 값을 넣습니다.
deQueue 연산
- Queue가 비어있는지 확인합니다.
- 큐가 비어있지 않다면, 요소를 제거할 수 있다는 의미이므로, front가 가르키는 index 값을 null로 변경 합니다.
- 만약, front와 rear의 값이 같다면, 요소가 하나만 존재한다는 의미이므로 두 값 모두 -1로 초기화 합니다.
- 그렇지 않다면, 다음 연산을 이용해 front의 위치를 이동 시킵니다. front = (front +1) % MaxSize
Array를 이용한 원형 큐 구현
class CircularQueue {
constructor(MAX_SIZE) {
this.queue = [];
this.MAX_SIZE = MAX_SIZE;
this.front = -1;
this.rear = -1;
}
isFull() {
return (this.rear + 1) % this.MAX_SIZE === this.front;
}
isEmpty() {
return this.front === -1 && this.rear === -1;
}
enQueue(item) {
if (this.isFull()) {
throw Error("Queue is full");
}
if (this.isEmpty()) {
this.front = this.rear = 0;
} else {
// rear 포인터를 한 칸 이동시키되, 원형으로 처리
this.rear = (this.rear + 1) % this.MAX_SIZE;
}
this.queue[this.rear] = item;
}
deQueue() {
if (this.isEmpty()) {
throw Error("Queue is empty");
}
this.queue[this.front] = null;
if (this.front === this.rear) {
this.front = this.rear = -1;
} else {
this.front = (this.front + 1) % this.MAX_SIZE;
}
}
}원형 큐는 대부분의 로직이 기존 선형 큐와 유사하지만, 주요 차이점은 삽입과 삭제 시 rear와 front를 연결하여 순환 구조를 유지하는 방식입니다. 이때, (rear + 1) % maxSize를 통해 rear 포인터가 front로 돌아가도록 설정합니다. 이 방식으로 배열의 끝에 도달해도 다시 처음으로 이동할 수 있게 되어 효율적인 메모리 활용이 가능합니다.
배열을 사용해 구현된 원형 큐의 연산별 시간 복잡도는 다음과 같습니다:
삽입 (enQueue): Queue가 가득 찼는지 확인한 후, 올바른 위치에 요소를 삽입합니다. 요소를 삽입하는 작업은 상수 시간이므로, 시간 복잡도는 𝑂(1) 입니다.
삭제 (deQueue): Queue가 비었는지 확인하고, 요소를 삭제한 후 front 포인터를 이동시키거나, 큐가 비었을 경우 front와 rear를 초기화합니다. 이 역시 상수 시간에 수행되므로, 시간 복잡도는 O(1)입니다.
특정 요소 찾기: 특정 요소를 찾기 위해서는 모든 요소를 순회해야 하므로, 최악의 경우 O(n)의 시간 복잡도가 발생합니다. 이 부분은 일반적인 선형 큐와 동일합니다.
따라서, 원형 큐는 효율적인 메모리 활용과 간단한 삽입/삭제 연산을 제공하며, 삽입과 삭제는 O(1), 특정 요소를 찾는 연산은 O(n)의 시간 복잡도를 가집니다.
LinkedList를 이용한 원형 큐
다음은 자바스크립트와 LinkedList로 구현한 원형 큐입니다.
class NewNode {
constructor(value, priority) {
this.value = value;
this.priority = priority;
this.next = null;
}
}
class PriorityLinkedListQueue {
constructor() {
this.head = null;
this.tail = null;
}
printQueue() {
let current = this.head;
while (current) {
current = current.next;
}
}
enQueue(value, priority) {
const newNode = new NewNode(value, priority);
// 리스트가 비어있을 경우
if (!this.head && !this.tail) {
this.head = newNode;
this.tail = newNode;
return;
}
// 새 노드가 head보다 우선순위가 높을 경우
if (this.head.priority < newNode.priority) {
newNode.next = this.head;
this.head = newNode;
return;
}
let current = this.head;
let previous = null;
while (current) {
if (current.priority <= newNode.priority) {
previous = current;
current = current.next;
}
}
if (!current) {
this.tail.next = newNode;
this.tail = newNode;
} else {
previous.next = newNode;
newNode.next = current;
}
}
deQueue() {
this.head = this.head.next;
if (!this.head.next) {
this.tail = null;
}
}
}원형 큐는 요소를 삽입할 때 마지막 요소의 next를 front와 연결해 순환 구조를 유지하는 것 외에는 일반적인 선형 큐와 거의 동일한 로직을 사용합니다.
삽입 (enQueue): 마지막 위치에 요소를 추가하고, rear.next를 front와 연결해 원형 구조를 만듭니다. 삽입은 큐의 끝에서 이루어지므로 상수 시간에 수행되며, 시간 복잡도는 O(1)입니다.
삭제 (deQueue): 큐의 맨 앞 요소를 제거하고, 새로운 front와 rear.next를 연결해 순환 구조를 유지합니다. 이 역시 큐의 앞부분에서 한 번의 연산으로 처리되므로, 시간 복잡도는 O(1)입니다.
따라서 원형 큐는 삽입과 삭제 모두 O(1)의 시간 복잡도를 가지며, 효율적인 메모리 사용과 간단한 연산을 제공하는 구조입니다.
결론
배열로 선형 큐를 구현할 때 발생하는 한계를 해결하기 위해 원형 큐에 대해 공부해 보았습니다.
선형 큐를 배열로 구현하면 삽입과 삭제 시 앞쪽 공간이 비더라도 재사용할 수 없거나, 모든 요소를 이동시켜야 하는 문제가 있습니다. 이때, 배열을 사용해야 한다면 원형 큐 구조를 활용해 끝과 끝을 연결하여 이러한 문제를 효과적으로 해결할 수 있습니다.
반면, 연결 리스트(Linked List)로 큐를 구현할 경우, 선형 큐와 원형 큐 사이에 큰 차이가 없습니다. 연결 리스트는 삭제된 요소의 자리를 자연스럽게 활용할 수 있으므로, 굳이 원형 큐 구조를 사용할 필요가 없다는 생각이 들었습니다.
따라서, 배열로 큐를 구현해야 하는 상황이라면 원형 큐를 이용하는게 더 좋은 선택이 될 것 같습니다.
