이전 원형 큐(Circular Queue - 또는 환상 큐)처럼 JavaScript의 Array 객체의 메서드를 사용하지 않고 큐(Queue)를 만들어 보겠습니다.
큐(Queue)는 한쪽으로 데이터를 넣고 다른 쪽으로 데이터를 가져오는 구조입니다.
그래서 데이터를 넣는 쪽을 rear라고 하고 데이터를 가져오는 쪽을 front라고 합니다.
프로그램에서는 버퍼를 사용하기 때문에 방향의 개념이 없습니다. 그래서 데이터를 넣는 위치를 rear로 데이터를 가져오는 위치를 front로 사용합니다. 그리고 데이터를 넣는 것을 인큐(Enqueue), 데이터를 가져오는 것을 디큐(Dequeue)라고 합니다.
[파란색 화살이 front, 주황색 화살이 rear]
큐(Queue)가 생성되면 front와 rear의 위치가 -1입니다. 데이터를 추가하면 rear의 위치에 1이 더해지고 데이터를 가져오면 front의 위치에 1이 더해집니다. rear의 위치가 큐의 마지막 위치와 같으면 더 이상 큐에 데이터를 넣을 수 없는 포화 상태입니다.
[파란색 화살이 front, 주황색 화살이 rear]
큐(Queue) 객체 생성하기
JavaScript에서 객체 생성하는 방법은 "JavaScript Object - 객체 생성"(https://carrotweb.tistory.com/184)를 참고하시기 바랍니다.
function()으로 Queue 객체를 선언하겠습니다.
객체 생성할 때 큐의 크기를 받아서 큐를 초기화합니다.
var Queue = function(queueSize) {
// Array 객체 생성
this.queue = [];
// 데이터 가져오는 위치
this.front = -1;
// 데이터 넣는 위치
this.rear = -1;
// 큐의 크기
this.queueSize = queueSize;
// 큐 초기화
for (var index = 0; index < queueSize; index++) {
this.queue.push(null);
}
// 큐에 데이터 넣기 함수
this.enqueue = function(data) {
var result = true;
if (this.isFull()) {
console.log("Queue Full");
result = false;
} else {
this.rear++;
this.queue[this.rear] = data;
}
return result;
}
// 큐에서 데이터 가져오기 함수
this.dequeue = function() {
var result = null;
if (this.isEmpty()) {
console.log("Queue Empty");
} else {
this.front++;
result = this.queue[this.front];
this.queue[this.front] = null;
if (this.isEmpty()) {
// 위치 초기화
this.front = -1;
this.rear = -1;
}
}
return result;
}
// 큐에 데이터가 공백 상태인지 확인하는 함수
this.isEmpty = function() {
return (this.front == this.rear);
}
// 큐에 데이터가 포화 상태인지 확인하는 함수
this.isFull = function() {
return (this.rear == this.queueSize - 1);
}
// 큐 정보 출력 함수
this.consoleLog = function() {
console.log(this.queue);
console.log("front: " + this.front + ", rear: " + this.rear);
}
}큐의 데이터와 front, rear의 위치를 알기 위해서 console로 출력하는 consoleLog 함수를 만들었습니다.
그리고 데이터 가져오기 함수에서 front와 rear의 위치가 같을 경우 front와 rear의 위치를 초기화해 줌으로써 다시 큐에 데이터를 넣을 수 있게 됩니다.
function()으로 선언된 큐(Queue)를 생성(new) 하겠습니다.
var queue = new Queue(4);
console.log(queue);
--> CircularQueue {queue: Array(4), front: 0, rear: 0, queueSize: 0, enqueue: ƒ, dequeue: ƒ, isEmpty: ƒ, isFull: ƒ, consoleLog: ƒ}
console.log(typeof queue);
--> object
console.log(queue instanceof Object);
--> true
console.log(queue instanceof Queue);
--> true
queue.consoleLog();
--> (4) [null, null, null, null]
--> front: -1, rear: -1
생성된 큐(Queue)에 데이터를 넣고 가져오겠습니다.
// 데이터 넣기
queue.enqueue("Data 1");
queue.consoleLog();
--> (4) ['Data 1', null, null, null]
--> front: -1, rear: 0
// 데이터 넣기
queue.enqueue("Data 2");
queue.consoleLog();
--> (4) ['Data 1', 'Data 2', null, null]
--> front: -1, rear: 1
// 데이터 가져오기
var popData = queue.dequeue();
console.log(popData);
--> Data 1
queue.consoleLog();
--> (4) [null, 'Data 2', null, null]
--> front: 0, rear: 1
// 데이터 넣기
queue.enqueue("Data 3");
queue.enqueue("Data 4");
queue.consoleLog();
--> (4) [null, 'Data 2', 'Data 3', 'Data 4']
--> front: 0, rear: 3
console.log(queue.isFull());
--> true
// 데이터 넣기
var result = queue.enqueue("Data 5");
--> Queue Full
console.log(result);
--> false
queue.consoleLog();
--> (4) [null, 'Data 2', 'Data 3', 'Data 4']
--> front: 0, rear: 3
// 데이터 가져오기
popData = queue.dequeue();
popData = queue.dequeue();
popData = queue.dequeue();
console.log(popData);
--> Data 4
queue.consoleLog();
--> (4) [null, null, null, null]
--> front: -1, rear: -1
console.log(queue.isEmpty());
--> true
popData = queue.dequeue();
--> Queue Empty
console.log(popData);
--> null
queue.consoleLog();
--> (4) [null, null, null, null]
--> front: -1, rear: -1enqueue() 함수의 리턴 값이 false이면 큐에 데이터를 더 이상 추가할 수 없는 포화 상태이고 dequeue() 함수의 리턴 값이 null이면 큐에 데이터가 없는 상태입니다.