큐

► 코딩테스트 합격자되기 자바스크립트편 07장 큐를 요약정리한 포스팅입니다.

선입선출 :FIFO( first in first out )

• 삽입하는 연산 push
• 꺼내는 연산 pop

👯👯 큐의 특성을 활용하는 분야

• 작업 대기열
• 이벤트 처리

큐의 ADT (abstract data type)

큐는 front 다음부터 rear까지를 큐가 관리하는 데이터로 생각해야 한다.

연산

• isFull() :boolean
• isEmpty() : boolean
• push(item) : void
• pop(item) : itemType

상태

• front :int -> front는 이전을 기준으로 큐의 사용할 수 있는 부분과 사용할 수 없는 부분으로 나뉘었다.
• rear : int
• data[maxsize] : itemType

큐 구현하기

자바스크립트에서는 배열의 push()와 shift()메서드를 이용해 큐를 흉내내는 방식이나 배열을 이용하여 큐를 구현하는 방식, 연결 리스트를 이용하여 큐를 구현하는 방식을 사용해야 한다.

1️⃣ shift() 메서드 사용하기

push()와 shift() 메서드를 사용하면 큐의 FIFO를 흉내낼 수는 있지만 shift()메서드의 시간 복잡도가 O(1)이 아니기 때문에 진짜 큐는 아니다.

2️⃣ 배열을 이용하는 방식

많은 요소를 다뤄야하는 문제라면 shift()메서드를 사용하는 경우 문제가 될 수 있기 때문에 직접 큐를 구현하는 방식도 알아야한다.

class Queue {
  items = [];
  front = 0;
  rear = 0;

  push(item) {
    this.items.push(item);
    this.rear++;
  }

  pop() {
    return this.item[this.front++];
  }

  isEmpty() {
    return this.front === this.rear;
  }
}

3️⃣ 연결 리스트를 이용하는 방식

자바스크립트에서 연결 리스트는 제공되지 않는 자료구조이다. 직접 구현하여 사용할 수 있어야한다. 하지만 실전 상활에서 기억이 안난다면 우선 shift()함수로 큐를 대체하거나 배열을 이용한 방법을 사용하는 것이 좋다.

class Node {
  constructor(data) {
    this.data = data; // 요소의 값
    this.next = null; // 다음 요소를 참조
  }
}

class Queue {
  constructor() {
    this.head = null; // 첫 번째 요소 참조
    this.tail = null; // 마지막 요소 참조
    this.size = 0; // 큐의 길이
  }

  push(data) {
    // 새로운 요소 생성
    const newNode = new Node(data);

    if (!this.head) { // 큐가 비어 있다면 head와 tail을 모두 새로 생성한 요소로 설정
      this.head = newNode;
      this.tail = newNode;
      // 아니면 현재 tail의 next 속성을 새로운 요소로 설정 후 tail이 새로운 요소를 참조하도록 변경
    } else {
      this.tail.nexe = newNode;
      this.tail = newNode;
    }

    this.size++; // 큐 길이 증가
  }

  pop() {
    /* ... */
  }

  isEmpty() {
    return this.size === 0;
  }
}