자바스크립트에서 큐는 구현되어 있지 않다... 직접 구현해야 한다. 큐를 구현하는 방법은 2가지가 있는데, 배열을 사용하는 방법과 연결 리스트를 사용하는 방법이 있다.
class Queue {
constructor() {
this.queue = [];
this.front = 0;
this.rear = 0;
}
}
배열 Queue를 만들고 인덱스를 가리키는 front와 rear는 모두 0으로 초기화 한다.
Queue.prototype.enqueue = function (newValue) {
this.queue[this.rear++] = newValue;
}
queue에 원소를 추가하는 것을 enqueue라고 한다. 배열 Queue에 원소를 추가할 때마다 rear의 값을 증가시킨다. front의 경우 추가할 때 변하지 않는다.
Queue.prototype.dequeue() = function (newValue) {
const value = this.queue[this.front];
delete this.queue[this.front];
this.front += 1;
return value;
}
queue에서 원소를 추출하는 것을 dequeue라고 한다. 가장 첫 번째 요소가 반환된다. value는 첫 번째 노드를 삭제하기 전 첫 번째 노드의 값을 저장한다. queue의 첫 번째 원소는 삭제한다. 그리고 front의 값을 1 증가시켜 배열의 queue[front]가 아닌 queue[front + 1]이 front가 된다. 그리고 추출한 값을 리턴한다.
javascript에서 배열의 요소를 삭제할 때 delete 연산자를 사용할 수 있다. 단 배열의 길이는 그대로이며.(삭제 후 이동하지 않는다.) 배열의 요소를 빈 값으로 변경한다. 따라서 출력하면 <1 empty item>이 출력된다.
Queue.prototype.peek = function () {
return this.queue[this.front];
};
peek 함수는 배열의 front에 해당하는 인덱스의 값을 반환한다.
Queue.prototype.size = function () {
return this.rear - this.front;
}
size 함수는 queue의 갯수를 리턴하는데 만약 한번도dequeue되지 않고 3개의 값을 추가했을 경우 queue의 인덱스는 [0][1] [2] 으로 되어 있다 이때 배열의 사이즈는 2-0이기 때문에 2가 되어 올바른 사이즈가 아닌 것처럼 보이지만,
enqueue 함수에서 인덱스가 추가되었을 때 this.rear++로 인해 3개가 추가되고 나서 현재 rear의 값은 3이다.
Queue.prototype.display = function () {
this.queue.forEach((item, index) => {
console.log(`[${index}] = ${item}`);
});
};
queue값을 출력하기 위해 사용한다. 디버그용
// Queue는 자바스크립트에서 두 가지 방법으로 구현 가능하다.
// 1. 배열을 사용하기 -> 배열의 인덱스가 매우 커질 위험이 있음. 배열의 빈 공간을 관리하려면 선형 시간이 소요된다.
// 2. 연결 리스트 사용하기
// Array 사용
class Queue {
constructor() {
this.queue = [];
this.front = 0;
this.rear = 0;
}
}
Queue.prototype.enqueue = function (newValue) {
this.queue[this.rear++] = newValue;
};
Queue.prototype.dequeue = function () {
const value = this.queue[this.front];
delete this.queue[this.front];
this.front += 1;
return value;
};
Queue.prototype.peek = function () {
return this.queue[this.front];
};
Queue.prototype.size = function () {
return this.rear - this.front;
};
Queue.prototype.display = function () {
this.queue.forEach((item, index) => {
console.log(`[${index}] = ${item}`);
});
};
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue();
console.log(queue.size());
queue.display();
연결 리스트를 사용하기 위해서는 Node가 필요하다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
연결 리스트를 사용하는 큐는 head, tail 포인터를 갖는다. 모두 null로 초기화 한다.
Queue.prototype.enqueue = function (newValue) {
const newNode = new Node(newValue);
if(this.head === null) {
this.head = this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size += 1;
};
enqueue 를 구현하는 방법은 연결 리스트에서 노드를 추가하는 방법과 동일하다. 첫 번째 노드일 경우 head와 tail 포인터가 모두 새로 생성한 노드를 가리키고 첫 번째 노드가 아닐 경우 현재 tail 노드의 다음 노드로 새로운 노드를 연결시키고 tail을 새로운 노드로 만든다.
Queue.prototype.dequeue = function () {
const value = this.head.value;
this.head = this.head.next;
this.size -= 1;
return value;
};
dequeue 를 구현하는 방법은 head가 가리키는 노드를 반환하는 방법으로 구현한다. 현재 head가 가리키는 노드의 값을 value에 저장하고. 헤드는 현재 head의 다음 노드를 가리킨다. 그리고 나서 저장한 value를 리턴한다.
Queue.prototype.peek = function () {
return this.head.value;
};
Queue.prototype.getSize = function () {
return this.size;
};
prototype을 사용하기 때문에 함수 이름을 size로 만들면 안된다. size로 만들 경우 console.log(queue.size())를 출력했을 때 오류가 발생한다. Queue 내부에서 size 프로퍼티를 먼저 찾는데 Queue 내부에 있는 size 프로퍼티는 함수가 아니다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}
Queue.prototype.enqueue = function (newValue) {
const newNode = new Node(newValue);
if (this.head === null) {
this.head = this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size += 1;
};
Queue.prototype.dequeue = function () {
const value = this.head.value;
this.head = this.head.next;
this.size -= 1;
return value;
};
Queue.prototype.peek = function () {
return this.head.value;
};
Queue.prototype.getSize = function () {
return this.size;
};
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue());
queue.enqueue(4);
console.log(queue.getSize());