패스트캠퍼스 JavaScript 코딩테스트 131개 예제 & CS지식으로 끝내기 강의 2주차

ch.2 JavaScript 핵심 자료구조[큐 (Queue)]

큐(Queue) 자료구조란 ? 

스택(Stack) 자료구조와는 다르게 선입선출 형식의 자료구조이다.

먼저들어간 데이터가 먼저 빠져나온다.

(예를 들면 게임 큐를 돌리고있다 => 먼저 게임 대기열에 들어 온 유저부터 게임에 매칭된다.)

이 큐 자료구조는 탐색 알고리즘에서 특히나 활용빈도가 높다.

그 이유는 먼저 들어간 자료가 먼저나온다는 로직이 상당히 많은 알고리즘에서 유용하게 사용될 수 있는 특성이기 때문이다.

스택같은경우는 배열리스트로 구현을 했지만, 큐 자료구조는 배열을 사용하면 효율적이지 못하다고 볼 수 있다.

 

---

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.큐(Queue) 구현하기

class Queue {
  constructor() { ... }
  
  size() { ... }
  
  add(value) {
    // 큐에 데이터가 아무것도 없는 경우
    if (this.size() === 0) {
      // 0번 위치에 값을 넣고 포인터는 건드리지 않는다
      // 이때 ['0']으로 키를 설정한 이유는
      // 자바스크립트 객체 Object는 키 값으로 오직
      // 문자열과 Symbol만 허용하기 때문
      this.storage['0'] = value;
    } else {
      // 그 외의 경우에는 간단하게
      // rear 위치를 1만큼 늘리고 해당 위치에 값 삽입
      this.rear += 1;
      this.storage[this.rear] = value
    }
  }

 

---

큐(Queue) 데이터 추출하기

큐에서 데이터를 추출하는 메서드의 용어는 다양화 되어 있는데 보통 삽입/추출에 enqueue/dequeue 라는 용어를 사용하기도 하고 단순히 add, insert/popleft 라는 용어를 사용하기도 한다. popleft는 기존 배열 내장 메서드 pop()이 우측에서 부터 데이터를 추출하기 때문에 그에 상반된 개념으로 popleft라고 호칭하는 것이다. 자바스크립트 역시 배열에 pop이라는 메서드 용어를 사용하므로 여기선 popleft 라는 이름으로 메서드를 정의했다. 이 부분은 본인에게 더 편한 용어가 있다면 어떠한 것으로 바꾸더라도 상관없다.

class Queue {
  constructor() { ... }
  
  size() { ... }
  
  add(value) { ... }
  
  popleft() {
    let temp;	// 첫 원소 값을 임시로 담을 변수
    // 두 포인터의 값이 같은 경우 (데이터가 1개 남은 경우)
    // 물론 초기 상태에서 아무런 데이터가 없는 상황일 수도 있으나
    // 이때 front의 값을 가져오고 제거하는 과정에서
    // 자바스크립트 특성 상 에러가 발생하지 않고
    // 두 포인터의 값을 계속 0으로 유지시켜 주기 때문에
    // 별도로 이 부분에 대한 처리를 해줄 필요는 없지만
    // 좀 더 호환성 높은 코드를 위해서는 사실 하는 편을 추천
    if (this.front === this.rear) {
      // 현재 front에 담긴 값을 가져오고
      // 항상 이 값을 delete 해주어야 한다
      temp = this.storage[this.front];
      delete this.storage[this.front];
      // 이 부분이 없었다면 이 시점에서 front는
      // rear의 값 보다 1보다 더 큰 역설에 빠지게 되므로
      // 데이터가 없는 경우를 다시 0으로 초기화
      this.front = 0;
      this.rear = 0;
    } else {
      // 현재 front에 담긴 값을 가져오고
      // 항상 이 값을 delete 해주어야 한다
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
    }
    return temp;
  }
}

---

https://fastcampus.co.kr/dev_online_upjscodingtest

 

UPSKILL : Javascript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.