07. 큐

‘줄을 서다’라는 뜻 (FIFO)

이런 큐의 특징을 선입선출 또는 FIFO라고 한다.

스택과 마찬가지로 큐도 삽입하는 연산을 푸쉬(Push), 꺼내는 연산을 팝(Pop)이라 한다.

큐를 사용하는 곳.

• 작업 대기열 : 네트워크 통신 할 때 서버에 작업 요청하면 서버는 들어온 순서대로 작업을 처리
• 이벤트 처리 : 어떤 application & 시스템에서 사용자의 이벤트 (키보드 입력 , 마우스 움직임)

---

큐의 ADT(추상구문트리)

• enqueue: 큐의 뒤쪽(리어)에 데이터를 추가하는 연산.
• dequeue: 큐의 앞쪽(프론트)에서 데이터를 제거하고 반환하는 연산.
• isEmpty: 큐가 비어있는지 확인하는 연산.
• isFull: 정적 배열 기반의 큐 구현 시 큐가 가득 찼는지 확인하는 연산.
• front : 앞에 데이터가 있는 위치
• rear : 뒤에 데이터가 있는 위치

---

자바스크립트로 치면 push() ,shift()입니다.

• 추가할 때 뒤에서 추가 push() | O(1)
• 삭제할 때 앞에서 삭제 shift() | O(n)

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

  // 큐의 뒤쪽에 데이터를 추가하는 메서드 (enqueue: push() 사용)
  enqueue(item) {
    this.items.push(item);
  }

  // 큐의 앞쪽에서 데이터를 제거하고 반환하는 메서드 (dequeue: shift() 사용)
  dequeue() {
    if (this.isEmpty()) {
      throw new Error("빈 큐에서 dequeue 불가여여");
    }
    return this.items.shift();
  }

  // 큐의 맨 앞 데이터를 확인하는 메서드 (삭제 없이)
  front() {
    if (this.isEmpty()) {
      throw new Error("빈 큐에서 front 불가여여");
    }
    return this.items[0];
  }

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

  // 큐 내 데이터의 개수를 반환하는 메서드
  size() {
    return this.items.length;
  }
}

// 사용 예제
const q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);

console.log("큐의 크기:", q.size());       // 출력: 큐의 크기: 3
console.log("큐의 앞 데이터:", q.front());   // 출력: 큐의 앞 데이터: 10
console.log("dequeue 결과:", q.dequeue());  // 출력: dequeue 결과: 10
console.log("큐의 크기:", q.size());       // 출력: 큐의 크기: 2

근데 이 둘을 아무리 최적화 시켜도 진짜 큐의 성능을 따라갈 순 없음.

---

큐를 사용한 3가지 방법

1. 대중적인 방법 (배열의 push()와 shift() 사용)

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

  // 뒤쪽에 데이터 추가 (push 사용)
  enqueue(item) {
    this.items.push(item);
  }

  // 앞쪽에서 데이터 삭제 (shift 사용)
  dequeue() {
    if (this.isEmpty()) {
      throw new Error("빈 큐에서 dequeue 불가");
    }
    return this.items.shift();
  }

  // 맨 앞 데이터 확인 (삭제 없이)
  front() {
    if (this.isEmpty()) {
      throw new Error("빈 큐에서 front 불가");
    }
    return this.items[0];
  }

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

  // 큐 크기 반환
  size() {
    return this.items.length;
  }
}

// 사용 예제
const queuePopular = new QueuePopular();
queuePopular.enqueue(1);
queuePopular.enqueue(2);
queuePopular.enqueue(3);
console.log("대중적 큐의 크기:", queuePopular.size()); // 출력: 3
console.log("대중적 큐의 front:", queuePopular.front()); // 출력: 1
console.log("dequeue 결과:", queuePopular.dequeue());   // 출력: 1

---

2. 배열을 이용한 방식 (앞 포인터 사용하여 shift() 없이)

class QueueArray {
  constructor() {
    this.items = [];
    this.frontIndex = 0; // 앞쪽 인덱스 관리
  }

  // 뒤쪽에 데이터 추가
  enqueue(item) {
    this.items.push(item);
  }

  // 앞쪽에서 데이터 삭제 (인덱스 이동)
  dequeue() {
    if (this.isEmpty()) {
      throw new Error("빈 큐에서 dequeue 불가여여");
    }
    const item = this.items[this.frontIndex];
    this.frontIndex++;
    // 불필요한 공간이 많으면 배열 재설정
    if (this.frontIndex > 50 && this.frontIndex * 2 >= this.items.length) {
      this.items = this.items.slice(this.frontIndex);
      this.frontIndex = 0;
    }
    return item;
  }

  // 맨 앞 데이터 확인 (삭제 없이)
  front() {
    if (this.isEmpty()) {
      throw new Error("빈 큐에서 front 불가여여");
    }
    return this.items[this.frontIndex];
  }

  // 큐가 비었는지 확인
  isEmpty() {
    return this.size() === 0;
  }

  // 현재 큐 크기 반환
  size() {
    return this.items.length - this.frontIndex;
  }
}

// 사용 예제
const queueArray = new QueueArray();
queueArray.enqueue(10);
queueArray.enqueue(20);
queueArray.enqueue(30);
console.log("배열 큐의 크기:", queueArray.size());       // 출력: 3
console.log("배열 큐의 front:", queueArray.front());       // 출력: 10
console.log("dequeue 결과:", queueArray.dequeue());        // 출력: 10

---

3. 연결리스트를 이용한 방식

// 노드 클래스 정의
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class QueueLinkedList {
  constructor() {
    this.head = null; // 큐의 앞쪽
    this.tail = null; // 큐의 뒤쪽
    this.length = 0;
  }

  // 뒤쪽에 데이터 추가
  enqueue(item) {
    const newNode = new Node(item);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // 앞쪽에서 데이터 삭제
  dequeue() {
    if (this.isEmpty()) {
      throw new Error("빈 큐에서 dequeue 불가");
    }
    const item = this.head.value;
    this.head = this.head.next;
    this.length--;
    if (this.isEmpty()) {
      this.tail = null;
    }
    return item;
  }

  // 맨 앞 데이터 확인 (삭제 없이)
  front() {
    if (this.isEmpty()) {
      throw new Error("빈 큐에서 front 불가");
    }
    return this.head.value;
  }

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

  // 큐 크기 반환
  size() {
    return this.length;
  }
}

// 사용 예제
const queueLinkedList = new QueueLinkedList();
queueLinkedList.enqueue("A");
queueLinkedList.enqueue("B");
queueLinkedList.enqueue("C");
console.log("연결리스트 큐의 크기:", queueLinkedList.size()); // 출력: 3
console.log("연결리스트 큐의 front:", queueLinkedList.front()); // 출력: A
console.log("dequeue 결과:", queueLinkedList.dequeue());        // 출력: A

 

---

• 대중적인 방법은 코드가 간단하지만, shift()로 인해 성능 이슈 있을 수 있음.
• 배열 방식은 인덱스 관리로 효율성을 높인 방법이고,
• 연결리스트 방식은 메모리 재할당 없이 깔끔하게 큐를 관리할 수 있는 방법