1. 큐
- FIFO(First In First Out)이라는 개념을 가진 선형 자료구조
- 먼저 들어간 것이 먼저 나오고, 나중에 들어간 것이 나중에 나온다.
- Linear Queue와 Circular Queue가 존재한다.
- e.g.줄서기를 생각하면 편하다.
1.1 큐의 기본 연산
Enqueue: 큐 맨 뒤에 요소를 추가Dequeue: 큐 맨 앞의 요소를 삭제Peek: front에 위치한 데이터를 확인front: 큐의 맨 앞 위치rear: 큐의 맨 뒤 위치
2. 선형 큐(Linear Queue)
2.1 표현
2.1.1 Array로 표현하기
- Linear Queue를 Array로 표현할 수 있다.
- 배열이기 때문에 빈 공간은 메꿔지지 않습니다.
- 선언한 배열만큼만 사용할 수 있기 때문에 가득 차면 문제가 발생
- JavaScript에서는 배열이 자유롭게 증감되기 때문에 이런 문제는 없겠지만, Font와 Rear가 무한정 커질 수 있다는 문제점이 존재
2.1.2 Linked List로 표현하기
- Linear Queue를 Linked List로 표현할 수 있다.
- Array 구현의 단점을 해결한 방식으로 인덱스의 고민은 할 필요가 없음
2.3 구현
2.3.1 Array로 구현
구현이 간단하기 때문에 코딩테스트에 구현할 떄 추천!
단, 앞서 말한 것처럼 Font와 Rear가 무한정 커질 수 있다는 문제점이 존재합니다.
class Queue {
// 생성자: new 키워드로 객체를 생성할때 호출되는 함수
constructor() {
this.queue = []; // 요소를 넣을 배열 변수
this.front = 0; // front 포인터
this.rear = 0; // rear 포인터
}
// 📝 넣기
enqueue(value) {
// 실행노드[rear변수 증감] = 입력받은 값
this.queue[this.rear++] = value;
}
// 📝 빼기
dequeue() {
const value = this.queue[this.front]; // 실행노드[front값]을 받아오기
delete this.queue[this.front]; // 실행노드의 front 삭제
this.front += 1;
return value;
}
// 📝 큐의 가장 앞에 있는 노드 반환
peek() {
return this.queue[this.front];
}
// 📝 큐의 크기 반환
size() {
return this.rear - this.front;
}
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size()); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 42.3.2 Linked List로 구현
Array 구현의 단점을 해결한 방식입니다.
class Node {
// 생성자: new 키워드로 객체를 생성할때 호출되는 함수
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 📝 넣기
enqueue(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;
}
// 📝 빼기
dequeue() {
const value = this.head.value;
this.head = this.head.next;
this.size -= 1;
return value;
}
// 📝 큐의 가장 앞에 있는 노드 반환
peek() {
return this.head.value;
}
// 📝 큐의 크기 반환
size() {
return this.rear - this.front;
}
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size()); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 42.3.3 shift
간혹 JS에서 큐 구현을 검색하면, shift()로 큐를 구현할 수 있는 경우가 많습니다. 그러나 이는 잘못된 정보입니다.
JS에서 shift는 선형 시간이 걸리기 때문에 큐엑서 기대하는 로직이 수행되지 않습니다. 따라서 큐를 쓸 떄 shift 함수는 쓰지 마세요.
const queue = [1, 2, 3];
queue.push(4);
const value = queue.shift(); // O(n) !!
console.log(value); // 13. 환형 큐(Circular Queue)
- Front와 Rear가 이어져 있는 Queue
- Circular Queue는 한정된 공간을 효율적으로 사용할 떄 사용
- Circular Queue는 Linked List로 구현했을 때 이점이 없다.
3.1 구현
3.1.1 Array로 구현
코딩테스트에서 환형 큐를 사용하는 경우는 많지 않습니다. 따라서 꼭 외울 필요는 없습니다.
class Queue {
// 생성자: new 키워드로 객체를 생성할때 호출되는 함수
constructor(maxSize) {
this.maxSize = maxSize;
this.queue = [];
this.front = 0;
this.rear = 0;
this.size = 0;
}
// 📝 넣기
enqueue(value) {
if (this.isFull()) {
console.log('Queue is full.');
return;
}
this.queue[this.rear] = value;
this.rear = (this.rear + 1) % this.maxSize;
this.size += 1;
}
// 📝 빼기
dequeue() {
const value = this.queue[this.front];
delete this.queue[this.front];
this.front = (this.front + 1) % this.maxSize;
this.size -= 1;
return value;
}
isFull() {
return this.size === this.maxSize;
}
// 📝 큐의 가장 앞에 있는 노드 반환
peek() {
return this.queue[this.front];
}
}
const queue = new Queue(4);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
queue.enqueue(8);
queue.enqueue(16); // Queue is full.
console.log(queue.dequeue()); // 1
console.log(queue.dequeue()); // 2
console.log(queue.size); // 2
console.log(queue.peek()); // 4
queue.enqueue(16);
queue.enqueue(32);
console.log(queue.isFull()); // true4. 큐 실습 : 프린터
4.1 문제
4.2 풀이
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
}
enqueue(newValue) {
const newNode = new Node(newValue);
if (this.head === null) {
this.head = this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
dequeue() {
const value = this.head.value;
this.head = this.head.next;
return value;
}
peek() {
return this.head.value;
}
}
function solution(priorities, location) {
const queue = new Queue(); // 큐 생성
// 대기목록만큼 순회
for (let i = 0; i < priorities.length; i += 1) {
queue.enqueue([priorities[i], i]); // 각각의 우선순위와 인덱스
}
priorities.sort((a, b) => b - a); // 내림차순 정렬
let count = 0; // 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지
// 큐가 비어있을 떄까지 반복
while (true) {
const currentValue = queue.peek(); // 가장 앞에 노드 반환
// 지금까지 수행한 우선순위보다 작은 경우
if (currentValue[0] < priorities[count]) {
queue.enqueue(queue.dequeue()); // 그 값을 맨 뒤에 넣기
} else {
const value = queue.dequeue(); // 우선순위가 더 큰 경우, 바로 dequeue
count += 1;
// 뽑은 문서가 내가 찾은 문서라면
if (location === value[1]) {
return count;
}
}
}
}[참고]
Front-end 공부 중... 책 읽는 걸 좋아합니다.