큐

큐 개념

제일 먼저 들어간 데이터가 제일 먼저 나오는 자료구조.

• FIFO(선입선출): 먼저 들어간 것이 먼저 나오는 규칙
• push: 큐에 삽입하는 연산
• pop: 큐에서 꺼내는 연산

큐의 정의

큐의 특성을 활용하는 분야

1. 작업 대기열: 네트워크 처리시 클라이언트에서 서버에 작업을 요청할때 먼저 요청된 작업부터 처리함.
2. 이벤트 처리: 애플리케이션이나 시스템에서의 사용자의 이벤트 EX)키보드의 입력 or 마우스의 움직임

큐의 ADT

ADT: 추상자료형. 인터페이스는 존재하나 실제로 구현은 되지 앟는 자료형. 일종의 자료형의 설계도.

큐에 필요한 정의

연산
1. push: 큐에 데이터를 푸시
2. pop: 큐에서 데이터를 팝 하고 데이터를 반환
3. isFull: 큐에 들어있는 데이터 갯수가 가득차있는지 가득찼다면 true 아니면 false
4. isEmpty: 큐에 데이터가 하나라도 들어있는지 들어있다면 false 없다면 true

상태
5. front: 큐에 가장 처음에 팝한 위치를 기록
6. rear: 큐에서 최근에 푸시한 데이터의 위치를 기록
7. data: 큐의 데이터를 관리하느 배열

큐의 세부동작

데이터를 추가 시

1. push() 호출
2. 내부적으로 isFull()을 수행해 data 배열에 데이터가 가득찼는지 확인
3. rear 에 +1을 한 다음 rear가 가르키는 위치에 push

데이터를 제거 시

1. pop() 호출
2. 내부적으로 isEmpty()을 수행해 data 배열에 데이터가 존재하는지 확인
3. 데이터가 존재 할 경우 front에 +1을 함

계속해서 추가 할 경우

1. 연속해서 값을 추가 할 경우 isFull 연산을 통해 큐가 가득 찼는지 검사.
2. 큐가 가득찼을 때 계속해서 추가할 경우 maximize-1 이 될며, isFull이 true가 되므로 push 불가

큐 구현하기

shift()메서드 사용하기

주의: push 와 shift를 사용해서 큐의 선입선출을 흉내 낼수 있으나 시간 복잡도가 O(1)이 아니기 때문에 진짜 큐는 아님

const queue = [];

//큐에 데이터 추가
queue.push(1);
queue.push(2);
queue.push(3);

// 큐의 맨 앞 데이터 제거
let firstItem = queue.shift();
console.log(firstItem); // 출력: 1

//큐에 데이터 추가
queue.push(4);
queue.push(5);

// 큐의 맨 앞 데이터 제거
let firstItem = queue.shift();
console.log(firstItem); // 출력: 2

배열을 이용하기

const Queue {
  items = [];
  fornt = 0;
  rear = 0;
  push(item) {
  	this.items.push(item);
    this.rear++;
  }
  
  pop(item) {
  return.this.items[];
  this.rear++;
  }

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

위 방식은 rear 와 front 가 계속해서 증가하는 문제가 있음.

연결 리스트를 이용하기

연결리스트를 이용하여 큐를 구현할 수 있음. 자바스크립트는 연결리스트를 제공하지 않기에 직접구현 필요.

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;
    } else {
      // 현재 tail의 next를 새 노드로 설정 후 tail 업데이트
      this.tail.next = newNode;
      this.tail = newNode;
    }

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

  pop() {
    if (!this.head) {
      return null; // 큐가 비어있을 경우
    }

    const removeNode = this.head;
    this.head = this.head.next;

    if (!this.head) {
      // 큐가 비었으면 tail도 null로
      this.tail = null;
    }

    this.size--; // 큐 길이 감소
    return removeNode.data; // 삭제된 요소 반환
  }

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

위 방식이 배열 방식보다 효율적이나, 실전시 생각이 안난다면 배열로 풀 것.