JavaScript의 큐 데이터 구조

이 게시물은 원래 TK's blog에 게시되었습니다.

큐 데이터 구조는 first-in first out 원칙을 따르는 항목 모음입니다. 첫 번째 추가된 요소는 대기열에서 제거되는 첫 번째 요소가 됩니다. 따라서 요소는 뒤쪽에 추가되고 앞쪽에서 제거됩니다.

비유는 다음 기차를 기다리는 사람들의 단순한 줄입니다. 소프트웨어 엔지니어링 컨텍스트에서 요청을 수신하고 응답하는 웹 서버를 예로 들 수 있습니다.

주요 API 메소드는 enqueue(추가) 및 dequeue(제거)입니다. 그러나 API 구현의 일부로 다른 메서드를 추가할 수도 있습니다. size , front , back 및 isEmpty .

대기열 구현

Queue 클래스를 래퍼로 만들고 Python 목록을 사용하여 대기열 데이터를 저장할 수 있습니다. 이 클래스는 enqueue , dequeue , size , front , back 및 isEmpty 메서드를 구현합니다.

첫 번째 단계는 클래스 정의와 항목을 저장하는 방법을 만드는 것입니다.

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

이것은 기본적으로 지금 우리에게 필요한 것입니다. 클래스와 생성자만 있으면 됩니다. 인스턴스가 생성되면 대기열 항목을 저장할 items 목록이 생성됩니다.
enqueue 메서드의 경우 목록append 메서드를 사용하여 새 항목을 추가하기만 하면 됩니다. 새 항목은 이items 목록의 마지막 색인에 배치됩니다. 따라서 대기열의 맨 앞 항목은 항상 첫 번째 항목이 됩니다.

enqueue(item) {
  this.items.push(item);
}

새 항목을 수신하여 목록에 추가합니다.
size 메서드는 length 속성을 사용하여 대기열 항목 수만 계산합니다.

size() {
  return this.items.length;
}

isEmpty 방법의 아이디어는 목록에 항목이 있는지 여부를 확인하는 것입니다. 있는 경우 false 를 반환합니다. 그렇지 않으면 true . 대기열의 항목 수를 계산하려면 이미 구현된 size 메서드를 사용하면 됩니다.

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

목록 데이터 구조의 shift 메서드를 사용하여 항목을 대기열에서 빼낼 수도 있습니다. 큐에 대해 예상되는 대로 첫 번째 요소를 큐에서 뺍니다. 첫 번째 추가 항목입니다.

dequeue() {
  this.items.shift();
}

front 메서드의 경우 items 목록의 첫 번째 요소에만 액세스할 수 있습니다.

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

항목이 하나 이상 있으면 대기열에 처음 추가된 항목인 전면을 얻습니다.
back 메서드의 경우 at 메서드를 사용하여 -1를 전달하여 마지막 요소에 액세스했습니다.

back() {
  return this.items.at(-1);
}

이 기능( .at() )은 NodeJS v17 이상에서만 사용할 수 있습니다. 이전 버전을 사용하는 경우 good-oldthis.items[this.items.length - 1] 를 사용할 수 있습니다.

항목이 하나 이상 있으면 대기열에 마지막으로 추가된 항목인 백 항목을 가져옵니다.

대기열 사용량

사용법은 다음과 같습니다.

const queue = new Queue();

queue.isEmpty(); // true
queue.size(); // 0

queue.enqueue(1); // [1]
queue.enqueue(2); // [1, 2]
queue.enqueue(3); // [1, 2, 3]
queue.enqueue(4); // [1, 2, 3, 4]
queue.enqueue(5); // [1, 2, 3, 4, 5]

queue.isEmpty(); // false
queue.size(); // 5;
queue.front(); // 1;
queue.back(); // 5;

queue.items; // [1, 2, 3, 4, 5];

queue.dequeue(); // [2, 3, 4, 5];
queue.dequeue(); // [3, 4, 5];
queue.dequeue(); // [4, 5];
queue.dequeue(); // [5];
queue.isEmpty(); // false
queue.dequeue(); // []
queue.isEmpty(); // true
queue.size(); // 0;

먼저 Queue 클래스에서 새 대기열을 인스턴스화합니다.

이제 우리는 그 공허함을 확인할 수 있습니다. 예, 그렇습니다!

크기 확인: 0.

5개의 새 항목을 대기열에 추가합니다. [1, 2, 3, 4, 5] .

비어 있음을 다시 확인하십시오. 더 이상은 아닙니다!

크기 확인: 5.

첫 번째 추가 항목이기 때문에 전면 요소를 가져옵니다. 1.

back 요소를 가져옵니다: 5는 마지막으로 추가된 항목이었기 때문입니다.

Dequeue 4 항목: 1, 2, 3, 4.

비어 있음 확인: 아직 비어 있지 않습니다!

사이즈는 1이고 앞뒷면은 같은 번호입니다: 5

나머지 항목을 대기열에서 빼십시오.

비어 있음 확인: 지금 비어 있습니다!

크기가 0으로 돌아갑니다.

전체 구현

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

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    this.items.shift();
  }

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

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

  back() {
    return this.items.at(-1);
  }

  size() {
    return this.items.length;
  }
}

런타임 및 공간 복잡성

이제 구현된 각 메서드의 공간 및 런타임 복잡성에 대해 알아보겠습니다.

공간은 상당히 심플합니다. 목록이므로 O(n)입니다. 여기서 n는 스택에 있는 현재 항목 수입니다.

각 메서드의 런타임은 O(1) , 일정한 시간입니다.

자원

Queue Data Structure: implementation

Queue Data Structure: tests