[자바스크립트] 큐(Queue)

큐(Queue)란 무엇인가?

**큐(Queue)**는 선입선출(FIFO, First-In-First-Out) 방식으로 데이터를 처리하는 자료 구조입니다. 쉽게 말해, 먼저 들어온 데이터가 먼저 나가는 방식으로, 마치 줄을 서서 기다리는 것과 같습니다.

• 선입(Enqueue): 큐의 뒷부분에 새로운 데이터를 추가하는 작업
• 선출(Dequeue): 큐의 앞부분에서 데이터를 제거하는 작업

자바스크립트에서 큐 구현하기

자바스크립트에서는 배열을 이용하여 간단하게 큐를 구현할 수 있습니다. 배열의 push() 메서드를 사용하여 데이터를 큐의 뒷부분에 추가하고, shift() 메서드를 사용하여 데이터를 큐의 앞부분에서 제거합니다.

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }

  peek() {
    return this.items[0];
  }
}

 

큐의 활용 예시

• 이벤트 루프: 자바스크립트 엔진은 이벤트 루프를 통해 비동기 작업을 처리하는데, 이때 큐를 사용하여 이벤트들을 관리합니다.
• 브라우저 역사 관리: 브라우저는 사용자가 방문한 페이지를 큐 형태로 저장하여 뒤로 가기 기능을 구현합니다.
• 데이터 처리: 생산자-소비자 문제처럼 여러 스레드에서 데이터를 생산하고 소비하는 경우, 큐를 사용하여 데이터를 효율적으로 주고받을 수 있습니다.
• BFS(너비 우선 탐색): 그래프 탐색 알고리즘 중 하나인 BFS에서 큐를 사용하여 노드를 탐색합니다.

큐의 장단점

• 장점:
  • 구현이 간단하고 직관적이다.
  • 데이터를 순서대로 처리하기 때문에 예측 가능한 결과를 얻을 수 있다.
• 단점:
  • 임의의 위치에 데이터를 삽입하거나 삭제하기 어렵다.
  • 큐가 가득 찼을 때 오버플로우가 발생할 수 있다.

자바스크립트 큐(Queue) 예시 코드 심층 분석

1. 배열을 이용한 기본 큐 구현

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }

  isEmpty() {
    return this.items.length === 0;
  }

  peek() {
    return this.items[0];
  }
}

// 큐 사용 예시
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log(queue.dequeue()); // 10 출력
console.log(queue.peek());    // 20 출력

• 장점: 간단하고 직관적이다.
• 단점: 배열의 shift() 메서드는 배열 전체 요소를 한 칸씩 앞으로 이동시키므로, 데이터가 많을 경우 성능 저하가 발생할 수 있다.

2. 두 개의 포인터를 이용한 큐 구현 (더 효율적)

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  enqueue(item) {
    this.storage[this.rear] = item;
    this.rear++;
  }

  dequeue() {
    const item = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;
    return item;
  }

  size() {
    return this.rear - this.front;
  }

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

• 장점: shift() 메서드를 사용하지 않아 성능이 더 좋다.
• 단점: 구현이 조금 더 복잡하다.

3. ES6 클래스와 메서드 체이닝 활용

class Queue {
  #items = [];

  enqueue(...elements) {
    this.#items.push(...elements);
    return this; // 메서드 체이닝을 위해 this 반환
  }

  dequeue() {
    return this.#items.shift();
  }

  peek() {
    return this.#items[0];
  }

  isEmpty() {
    return this.#items.length === 0;
  }
}

// 메서드 체이닝 예시
const queue = new Queue()
  .enqueue(10)
  .enqueue(20, 30);

• 장점: ES6 클래스의 문법을 활용하여 코드 가독성을 높이고, 메서드 체이닝을 통해 코드를 간결하게 작성할 수 있다.

4. 큐를 이용한 실제 예시: 브라우저 히스토리

class BrowserHistory {
  constructor() {
    this.history = new Queue();
  }

  push(url) {
    this.history.enqueue(url);
  }

  back() {
    if (!this.history.isEmpty()) {
      return this.history.dequeue();
    }
    return null;
  }
}

const history = new BrowserHistory();
history.push('https://www.example.com');
history.push('https://www.google.com');

console.log(history.back()); // https://www.example.com 출력

5. 큐를 이용한 BFS (너비 우선 탐색)

function bfs(graph, startNode) {
  const visited = new Set();
  const queue = new Queue();
  queue.enqueue(startNode);
  visited.add(startNode);

  while (!queue.isEmpty()) {
    const currentNode = queue.dequeue();
    console.log(currentNode);

    for (const neighbor of graph[currentNode]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.enqueue(neighbor);
      }
    }
  }
}

// 예시 그래프
const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: [],
  F: []
};

bfs(graph, 'A'); // A B C D E F 순으로 출력