큐 (Queue)
Queue 🙂
큐(Queue)는 스택과 함께 대표적인 자료구조입니다. 스택이 Last In, First Out(LIFO)의 구조를 띄고 있었다면, 큐는 First In, Fist Out(FIFO)라는 선입선출 구조를 띄고 있습니다. 그리고 큐 역시 각 동작마다 명칭이 정해져 있는데, 큐의 마지막에 새로운 데이터를 추가하는 작업을 인큐(Enqueue), 그리고 맨 앞의 데이터를 빼는 작업을 디큐(Dequeue)라 합니다.
큐를 구현할 때는 디큐(Dequeue)가 일어날 때마다, 맨 앞을 가리키는 front의 값이 하나씩 뒤로 이동하는 것을 유의해야 합니다. 자바스크립트에서는 배열 프로토타입의 메소드 중 push와 shift로 큐를 간단하게 구현할 수 있지만, 본문의 코드에서는 사용하지 않았습니다.
큐 프로토타입
function Queue(capacity) {
this.front = 0;
this.rear = capacity - 1;
this.capacity = capacity;
}
Queue.prototype = Object.create(Array.prototype);
Queue.prototype.constructor = Queue;
const queue = new Queue(3);
생성자 함수 Queue는 3개의 멤버 변수를 갖습니다. front와 rear는 각각 큐의 앞과 뒷부분을 가리키는 포인터 역할을 하며, 이 변수들을 통해 큐에 데이터를 삽입하거나 제거할 수 있습니다. 그리고 capacity는 큐에 담을 수 있는 데이터의 최대 수용량을 의미하는 변수입니다.
생성자 함수 아래를 보면 두 줄의 추가 구문을 확인할 수 있는데, 이는 큐를 배열처럼 사용하기 위해 프로토타입 체이닝을 통한 상속을 구현한 것입니다. 이렇게 함으로써 Queue 생성자로 만든 객체는 배열의 메소드를 사용할 수 있게 됩니다.
데이터 추가
Queue.prototype.enqueue = function (data) {
if (this.isFull()) {
throw new Error('Queue is full!');
}
this.rear = (this.rear + 1) % this.capacity;
this[this.rear] = data;
this.length += 1;
};
Queue.prototype.isFull = function () {
return this.length === this.capacity;
};
큐에 새로운 데이터를 추가할 때는 rear의 값을 하나씩 증가시키며 삽입하면 됩니다. 본문의 예제에서는 큐가 꽉 차게 되면 에러를 발생시키는데, 만약 무한 큐를 구현하고 싶다면 isFull 함수를 사용하지 않아도 됩니다. 바로 아래에서 모듈러 연산(%)을 통해 데이터를 삽입할 수 있도록 구현했기 때문입니다.
데이터 제거
Queue.prototype.dequeue = function () {
if (this.isEmpty()) {
throw new Error('Queue is empty!');
}
let val = this[this.front];
this.front = (this.front + 1) % this.capacity;
this.length -= 1;
return val;
};
Queue.prototype.isEmpty = function () {
return this.length === 0;
};
데이터를 제거하는 것도 추가할 때와 동일한 방식으로 구현 가능합니다.
References 📝
본문의 내용은 GeeksforGeeks의 자료구조 튜토리얼을 참고해 작성했습니다 ❤️
'💻 컴퓨터공학 > 자료구조' 카테고리의 다른 글
이진 트리 (Binary Tree) (0) | 2021.10.26 |
---|---|
LCRS 트리 (LCRS Tree) (0) | 2021.10.25 |
스택 (Stack) (0) | 2021.10.14 |
원형 링크드 리스트 (Circular Linked List) (0) | 2021.10.13 |
더블 링크드 리스트 (Doubly Linked List) (0) | 2021.10.13 |
댓글
이 글 공유하기
다른 글
-
이진 트리 (Binary Tree)
이진 트리 (Binary Tree)
2021.10.26 -
LCRS 트리 (LCRS Tree)
LCRS 트리 (LCRS Tree)
2021.10.25 -
스택 (Stack)
스택 (Stack)
2021.10.14 -
원형 링크드 리스트 (Circular Linked List)
원형 링크드 리스트 (Circular Linked List)
2021.10.13