[자료구조] Queue(큐)

큐란?

먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 구조이다. 큐는 줄을 서는 것과 비슷하게 생각하면 된다. 먼저 줄 서 있는 사람이 가장 먼저 나가고 새로운 사람들 줄의 맨 끝에 선다고 생각하면 됩니다.

메소드

• Enqueue(추가): 큐의 끝에 데이터 추가
• Dequeue(제거): 큐의 맨 앞에 데이터를 제거하고 반환
• Peek(확인): 큐의 맨 앞 데이터를 반환
• isEmpty(비어 있는지 확인): 큐가 비어있는지 확인
• Size(크기): 현재 큐에 있는 요소 반환

시간 복잡도

• Enqueue: 배열의 끝에 삽입 O(1)
• Dequeue: 배열의 첫번째 요소를 제거하면 남은 요소들을 한칸씩 이동시켜야 하기 때문에 O(n) *큐를 직접 구현할 경우 O(1)
• Peek: 배열의 첫번째 요소 O(1)
• isEmpty: 배열이 비어있는지 확인 array.length === 0 O(1)

배열로 큐 구현

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

  // 큐에 요소 추가
  enqueue(element) {
    this.items.push(element);
  }

  // 큐에서 요소 제거
  dequeue() {
    if(this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items.shift();
  }

  // 큐의 첫 번째 요소 확인
  peek() {
    if(this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[0];
  }

  // 큐가 비어 있는지 확인
  isEmpty() {
    return this.items.length === 0;
  }

  // 큐의 크기 확인
  size() {
    return this.items.length;
  }
}

// 사용 예시
let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue()); // 1
console.log(queue.peek());    // 2
console.log(queue.size());    // 2

큐 직접 구현

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null; // 큐의 앞
    this.rear = null;  // 큐의 뒤
    this.size = 0;     // 큐의 현재 크기
  }

  enqueue(value) {
    const newNode = new Node(value);

    if (this.isEmpty()) {
      // 큐가 비어있으면 front와 rear 모두 새로운 노드로 설정
      this.front = this.rear = newNode;
    } else {
      // 큐가 비어있지 않으면 rear의 next를 새로운 노드로 설정
      this.rear.next = newNode;
      this.rear = newNode;
    }

    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      // 큐가 비어있으면 -1 반환
      return -1;
    }

    const dequeuedValue = this.front.value;
    this.front = this.front.next;

    if (this.front === null) {
      // 큐가 비어있으면 rear도 null로 설정
      this.rear = null;
    }

    this.size--;
    return dequeuedValue;
  }

  peek() {
    if (this.isEmpty()) {
      // 큐가 비어있으면 -1 반환
      return -1;
    }
    return this.front.value;
  }

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

  getSize() {
    return this.size;
  }
}