[JS/Algorithm] 큐

큐

뜻 줄을 서다

자료구조 먼저 들어간 데이터가 먼저 나오는 자료구조 (FIFO, 선입선출)

ADT

연산 

• isFull 큐에 들어 있는 데이터가 maxsize인지 확인
• isEmpty 큐에 들어있는 데이터가 하나도 없는지 확인해 boolean 값을 반환
  • front === rear인 경우
• push 큐에 데이터를 푸시
• pop 큐에서 처음에 푸시한 데이터를 팝하고, 그 데이터를 반환

상태

• front 큐에서 가장 처음에 팝한 위치를 기록
• rear 큐에서 최근에 푸시한 데이터의 위치를 기록
• data[maxsize] 큐의 데이터 배열

 

구현

1. shift 메서드 이용

const queue = [];

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

let firstItem = queue.shift(); // 큐의 맨 앞 데이터 제거

2. 배열 이용

class Queue {
  items = [];
  front = 0;
  rear = 0;

  push(item) {
    this.items.push(item);
    this.rear++;
  }

  pop() {
    return this.items[front++];
  }

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

3. 연결 리스트 이용

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 {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }
  
  pop() {
    if (!this.head) {
        return null;
    }
    this.size--;
    return removeNode.data;
  }
  
  isEmpty() {
    return this.size === 0;
  }
}