지금까지 만든 스택(Stack), 큐(Queue), 덱/데크(Deque) 객체를 보면 아시겠지만 Array 객체로 모두 구현이 가능합니다. JavaScript의 Array 객체는 덱/데크(Deque)라고 생각하시면 됩니다. 그리고 크기 제한을 하지 않으면 사용할 수 있는 메모리만큼 사용할 수 있습니다.
만약 JavaScript의 Array 객체의 메서드를 사용하지 않고 직접 큐(Queue)를 만들어서 사용하면 무슨 문제가 생길까요?
바로 데이터 Push와 Pop에 따른 큐(Queue)의 비효율적인 메모리 사용 문제입니다.
큐(Queue) 데이터를 넣는 위치(rear)와 데이터를 가져오는 위치(front)가 다릅니다. 그래서 데이터를 넣고 가져오기를 반복하다 보면 더 이상 데이터를 넣을 수는 상태가 발생합니다. 큐(Queue)에 있는 전체 데이터를 가져오면 다시 사용할 수 있습니다.
[파란색 화살이 front, 주황색 화살이 rear]
그 이유는 데이터를 넣는 위치에 데이터가 있기 때문에 더 이상 데이터를 넣을 수 없습니다.
(실제 JavaScript의 Array 객체에서는 데이터를 제거하면 데이터가 자동으로 앞으로 이동하기 때문에 빈 공간이 발생하지 않습니다. 그래서 Array 객체에서 데이터 제거할 때는 뒤에서부터 검색하여 제거해야 합니다.)
버퍼의 앞에 빈 공간이 있어도 데이터를 넣는 위치(rear)가 큐의 마지막 위치라면 데이터를 넣을 수 없습니다.
그래서 큐(Queue)의 문제점을 해결한 것이 원형 큐(Circular Queue - 또는 환상 큐)입니다.
원형 큐/환상 큐(Circular Queue)
원형 큐/환상 큐(Circular Queue)란, 데이터를 넣고 가져오는 방향이 없는 구조입니다. 단 큐의 크기가 지정되어 있어야 합니다. 그리고 front와 rear의 위치 계산을 위해 하나의 빈 공간이 있어야 합니다. 그래서 실제 사용할 수 있는 큐의 크기는 전체 큐의 크기에서 1을 뺀 크기입니다.
원형 큐/환상 큐(Circular Queue)의 모양은 큐(Queue)를 원형으로 만든 튜브나 도넛 모양입니다.
[파란색 화살이 front, 주황색 화살이 rear]
위의 원형 큐/환상 큐(Circular Queue)의 크기(queueSize)는 6입니다. 실제 데이터가 저장되는 크기는 5입니다.
그리고 큐(Queue)는 front와 rear의 위치가 -1이지만 원형 큐/환상 큐(Circular Queue)는 front와 rear의 위치가 0입니다.
큐에 데이터 넣기
큐에 데이터를 넣기 위해서 rear의 다음 위치를 계산해야 합니다.
rear에 1을 더하고 큐의 크기(queueSize)로 나눈 나머지 값이 rear의 다음 위치입니다.
큐의 크기로 나눈 나머지 값을 사용하는 이유는 큐가 원형처럼 사용하기 위해서 큐의 마지막 위치에 오면 큐의 시작 위치인 0부터 처리하게 하기 위해서입니다.
rear = (rear + 1) % queueSize;
queue[rear] = data; --> 데이터 넣기그런데 rear의 다음 위치가 front의 위치와 같다면 더 이상 큐에 데이터를 넣을 수 없는 포화 상태입니다.
front == (rear + 1) % queueSize --> 큐 포화 상태
큐에서 데이터 가져오기
큐에서 데이터를 가져오기 위해서 front의 다음 위치를 계산해야 합니다. (rear의 위치 계산 공식과 동일합니다.)
front에 1을 더하고 큐의 크기(queueSize)로 나눈 나머지 값이 front의 다음 위치입니다.
front = (front + 1) % queueSize;
data = queue[front]; --> 데이터 가져오기
queue[front] = null; --> 빈 공간 처리데이터를 가져오기 전에 front와 rear의 위치가 같으면 큐는 데이터가 없는 공백 상태입니다.
front == rear --> 큐 공백 상태
위의 계산 공식으로 원형 큐/환상 큐(Circular Queue) 객체를 만들어 보겠습니다.
원형 큐/환상 큐(Circular Queue) 객체 생성하기
JavaScript에서 객체 생성하는 방법은 "JavaScript Object - 객체 생성"(https://carrotweb.tistory.com/184)를 참고하시기 바랍니다.
function()으로 CircularQueue 객체를 선언하겠습니다.
객체 생성할 때 큐의 크기를 받아서 큐를 초기화합니다.
var CircularQueue = function(queueSize) {
// Array 객체 생성
this.queue = [];
// 데이터 가져오는 위치
this.front = 0;
// 데이터 넣는 위치
this.rear = 0;
// 큐의 크기
this.queueSize = queueSize;
// 큐 초기화
for (var index = 0; index < queueSize; index++) {
this.queue.push(null);
}
// 큐에 데이터 넣기 함수
this.add = function(data) {
var result = true;
if (this.isFull()) {
console.log("Queue Full");
result = false;
} else {
this.rear = (this.rear + 1) % queueSize;
this.queue[this.rear] = data;
}
return result;
}
// 큐에서 데이터 가져오기 함수
this.remove = function() {
var result = null;
if (this.isEmpty()) {
console.log("Queue Empty");
} else {
this.front = (this.front + 1) % queueSize;
result = this.queue[this.front];
this.queue[this.front] = null;
}
return result;
}
// 큐에 데이터가 공백 상태인지 확인하는 함수
this.isEmpty = function() {
return (this.front == this.rear) ? true : false;
}
// 큐에 데이터가 포화 상태인지 확인하는 함수
this.isFull = function() {
return (this.front == (this.rear + 1) % this.queueSize) ? true : false;
}
// 큐 정보 출력 함수
this.consoleLog = function() {
console.log(this.queue);
console.log("front: " + this.front + ", rear: " + this.rear);
}
}큐의 데이터와 front, rear의 위치를 알기 위해서 console로 출력하는 consoleLog 함수를 만들었습니다.
그리고 데이터를 넣는 함수 명을 add가 아닌 enqueue(인큐)로 데이터를 가져오는 함수 명을 remove이 아닌 dequeue(디큐)로 사용하셔도 됩니다.
function()으로 선언된 원형 큐/환상 큐(Circular Queue)를 생성(new) 하겠습니다.
var circularQueue = new CircularQueue(6);
console.log(circularQueue);
--> CircularQueue {queue: Array(6), front: 0, rear: 0, queueSize: 0, add: ƒ, remove: ƒ, isEmpty: ƒ, isFull: ƒ, consoleLog: ƒ}
console.log(typeof circularQueue);
--> object
console.log(circularQueue instanceof Object);
--> true
console.log(circularQueue instanceof CircularQueue);
--> true
circularQueue.consoleLog();
--> (6) [null, null, null, null, null, null]
--> front: 0, rear: 0
생성된 원형 큐/환상 큐(Circular Queue)에 데이터를 넣겠습니다.
// 데이터 넣기
circularQueue.add("Data 1");
circularQueue.consoleLog();
--> (6) [null, 'Data 1', null, null, null, null]
--> front: 0, rear: 1
// 데이터 넣기
circularQueue.add("Data 2");
circularQueue.consoleLog();
--> (6) [null, 'Data 1', 'Data 2', null, null, null]
--> front: 0, rear: 2
// 데이터 넣기
circularQueue.add("Data 3");
circularQueue.add("Data 4");
circularQueue.add("Data 5");
circularQueue.consoleLog();
--> (6) [null, 'Data 1', 'Data 2', 'Data 3', 'Data 4', 'Data 5']
--> front: 0, rear: 5
console.log(circularQueue.isFull());
--> true
// 데이터 넣기
circularQueue.add("Data 6");
--> Queue Full
circularQueue.consoleLog();
--> (6) [null, 'Data 1', 'Data 2', 'Data 3', 'Data 4', 'Data 5']
--> front: 0, rear: 5마지막 데이터는 큐가 포화 상태이기 때문에 추가되지 않고 "Queue Full"를 출력합니다. 그리고 리턴 값으로 false를 리턴합니다.
add() 함수의 리턴 값이 false 이면 큐에 데이터를 더 이상 추가할 수 없는 포화 상태입니다.
생성된 원형 큐/환상 큐(Circular Queue)에 데이터를 가져오겠습니다.
// 데이터 가져오기
var popData = circularQueue.remove();
console.log(popData);
--> Data 1
circularQueue.consoleLog();
--> (6) [null, null, 'Data 2', 'Data 3', 'Data 4', 'Data 5']
--> front: 1, rear: 5
// 데이터 가져오기
popData = circularQueue.remove();
console.log(popData);
--> Data 2
circularQueue.consoleLog();
--> (6) [null, null, null, 'Data 3', 'Data 4', 'Data 5']
--> front: 2, rear: 5
// 데이터 가져오기
popData = circularQueue.remove();
popData = circularQueue.remove();
popData = circularQueue.remove();
console.log(popData);
--> Data 5
circularQueue.consoleLog();
--> (6) [null, null, null, null, null, null]
--> front: 5, rear: 5
console.log(circularQueue.isEmpty());
--> true
// 데이터 가져오기
popData = circularQueue.remove();
--> Queue Empty
console.log(popData);
--> null
circularQueue.consoleLog();
--> (6) [null, null, null, null, null, null]
--> front: 5, rear: 5마지막 데이터가 없기 때문에 가져오지 않고 "Queue Empty"를 출력합니다. 그리고 리턴 값으로 null를 리턴합니다.
remove() 함수의 리턴 값이 null이면 큐에 데이터가 없는 상태입니다.