자바스크립트 인터뷰 코딩 테스트 문제 8

액세스 권한이 있는 유일한 데이터 구조가 스택일 때 대기열을 생성하는 방법을 알아봅니다.
지침
두 개의 스택을 사용하여 대기열을 생성하는 함수를 작성하십시오. 이러한 twD 스택 외에 구현 시 추가 데이터 구조를 사용할 수 없습니다. enqueue , dequeue 및 size 메서드가 있어야 합니다.

시작할 때 아래 제공된 코드를 자유롭게 변경하십시오. 길잡이가 되기 위함입니다.
해결책

1   class Queue {
2     constructor() {
3       this._enqueueStorage[];
4       this._dequeueStorage[];
5     }
6
7     enqueue(1tem) (
8       this. enqueuestorage.push(item); 9  }
10
11    dequeue( ) (
12      if(this. dequeueStorage.length) (
13        return this. dequeueStorage.pop();
14  }
15
16  1f(th1s ._enqueue5torage . 1ength) (
17    while(this. enqueue5torage.length) {
18    this. dequeuestorage.push(this. enqueue5torage.pop()); 19
20
21      return this. dequeueStorage.pop(); 
22
23
24     console.warn('Attempting to dequeue from an empty queue');
25  return undefined; 26     

작동 방식
두 개의 스토리지 스택이 있습니다. 이 ._enqueueStorage 및
이것 . 큐 저장 해제 . 그들이 어떻게 상호 작용하는지 보기 위해 예를 들어 봅시다.
대기열에 넣기
큐에 5개의 요소(1, 2, 3, 4 및 s)를 넣고 싶습니다. 우리는 대기열에 넣습니다
이 모든 것들은 모두 enqueuestorage 로 들어갑니다.

대기열에 넣기: [1, 2, 3, 4, 5] 대기열에서 빼기: []

이제 항목을 대기열에서 빼려고 합니다. dequeue 함수에 대해 자세히 살펴보겠습니다.
대기열에서 빼기
dequeuestorage가 비어 있기 때문에 12행의 if 문을 건너뜁니다. 우리는 움직인다
16번째 줄에.

if 문(16행) 내에서 모든 항목을 enqueuestorage에서 꺼내서 dequeuestorage에 넣습니다. while 루프(라인 17 - 19)가 끝나면 enqueuestorage는 비어 있고 dequeuestorage에는 5개의 항목이 있지만 그 반대입니다.
대기열에 넣기: [) 대기열에서 빼기: [5, 4, 3, 2, 1]
21행에서 dequeuestorage를 팝하고 항목 i를 반환합니다.
대기열에 넣기: [] 대기열에서 빼기: [5, 4, 3, 2]
다시 대기열에서 빼려면 대기열에서 빼는 방법을 한 번 더 입력하면 됩니다. 이번에는 첫 번째 if 문으로 이동하여 dequeuestorage에서 항목을 팝하고 반환합니다.
대기열에 넣기: [] 대기열에서 빼기: [5, 4, 3]
원하는 경우 계속 대기열에서 빼낼 수 있습니다. dequeuestorage에 항목이 있는 한 마지막 항목이 제거되어 반환됩니다.
요약
이 단계를 함께 수행하면 대기열이 제대로 작동합니다. 대기열에 추가하면 항목이 하나의 스택으로 푸시됩니다. 큐에서 빼면 두 번째 스택에서 팝됩니다. 두 번째 스택이 비어 있고 큐에서 제거하려는 경우 첫 번째 스택을 두 번째 스택으로 비우고 항목 순서를 반대로 합니다.
대기열에 넣기 시간
모든 enqueue 이벤트는 스택에 대한 간단한 푸시입니다. 즉, 각 인큐의 시간 복잡도는 다음과 같습니다.
0(1)
대기열에서 빼기 시간
따라서 대부분의 경우 o(1) 을 사용하고 몇 가지 드문 경우에는 o(n) 을 사용합니다. 이를 단일 시간 복잡성으로 병합할 수 있습니다.
대기열 수명 주기
대기열에 있는 세 항목의 수명을 추적해 보겠습니다. 빈 대기열에서 시작하여 i , 2 및 3 을 대기열에 넣습니다. 이렇게 하면 첫 번째 스택에 놓입니다.
대기열에 넣기: [1, 2, 3] 대기열에서 빼기: []
지금까지 3가지 작업을 수행했습니다. 각 항목을 스택에 삽입합니다.
세 항목을 모두 대기열에서 빼봅시다. 먼저 enqueuestorage의 모든 항목은
dequeuestorage 로 전송됨 .
대기열에 넣기: [] 대기열에서 빼기: [1, 2, 3]
우리는 전이가 1 Dperation이라고 말할 것입니다. 이것은 또 다른 총 3개의 작업으로, 우리를 6개로 만듭니다.