[JavaScript] 연결 리스트로 큐(Queue) 구현하는 방법

큐(Queue)란?

큐는 데이터를 일시적으로 저장하는 자료구조 중 하나로, 먼저 입력된 데이터가 먼저 출력되는 "선입선출(FIFO: First-In-First-Out)" 원칙을 따릅니다.

 

큐(Queue)의 구현 방법 2가지

큐는 배열(Array)이나 연결 리스트(Linked List)를 사용하여 구현할 수 있습니다.

1️⃣ 배열

배열을 사용할 경우, 크기가 고정되어 있어서 데이터의 추가 및 제거에 제한이 있을 수 있지만, 연산 속도가 빠릅니다.

2️⃣ 연결 리스트

연결 리스트를 사용할 경우, 크기에 제한이 없어서 데이터를 유동적으로 추가 및 제거할 수 있지만, 연산 속도가 느립니다.

 

🧐 배열로 큐(Queue)를 구현해도 되지만 굳이 ? 연결 리스트로 구현해야 하는 이유 

JavaScript에서 배열을 사용하여 큐(Queue)를 구현하는 것은 가능하지만, 배열의 맨 앞에서 데이터를 제거하는 것은 비효율적입니다. 이는 배열의 모든 요소를 한 칸씩 이동시켜야 하기 때문입니다. (시간 복잡도 O(n)) 반면에 스택(Stack)은 배열의 맨 끝에서 데이터를 삽입 및 제거하기 때문에 효율적으로 구현할 수 있습니다.

 

📝 연결 리스트로 큐(Queue) 구현하는 방법

class Node {
  constructor(data) {
    // 노드 값
    this.data = data;
    // 다음 노드에 대한 참조를 저장
    this.next = null;
  }
}

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

  enqueue(data) {
    // 새로운 노드 생성
    const newNode = new Node(data);

    // 큐가 비어있을 경우 head와 tail을 모두 새 노드로 설정
    // 그렇지 않으면 현재 tail의 next 속성을 새 노드로 설정하고 tail이 새 노드를 가리키도록 업데이트
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.size++;
  }

  dequeue() {
    // 큐가 비어있을 경우 null 반환
    // 그렇지 않으면 head를 큐의 두 번째 요소로 설정하고 제거된 노드의 data를 반환
    if (!this.head) {
      return null;
    }

    const removeNode = this.head;
    this.head = this.head.next;
    if (!this.head) {
      this.tail = null;
    }

    this.size--;

    return removeNode.data;
  }
  // 큐가 비어있을 경우 true 반환, 그렇지 않으면 false 반환 
  isEmpty() {
    return this.size === 0;
  }
}

const Q = new Queue();
Q.enqueue(1);
Q.enqueue(2);
Q.dequeue();
console.log(Q);

 

🧑🏻‍💻 대단한 실력자가 아닌 공부를 하고 있는 취준생입니다. 틀린 부분이 있다면 과감하게 댓글로 혼쭐내주시기 바랍니다❗️