하나의 스택을 사용하여 대기열 생성

최근 Google은 지원자에게 단일 스택만 사용하여 대기열을 구성하도록 요청했다고 밝혔습니다.
이것은 불가능해 보일 수 있지만 약간의 속임수를 사용하면 가능합니다. 부담 없이 직접 사용해 보세요.

힌트
이것은 좋은 시간 복잡성을 갖지 않을 것입니다.
배열이나 객체를 사용하지 않고 어떻게 정보를 저장할 수 있을지 생각해 보십시오.

class Queue {   
  constructor() {   
  this._storage = [];
    // Your code    here

  enqueue(Item)  (  
      // Your  code here
  } 

  dequeue() (   
    // Your code    here
  } 

  get  size()  (    
    // Your  code   here
  } 
}

해결책

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

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

  dequeue() {
    if(this._storage.length > 1) {
      const lastltem = this._storage.pop();
      const firstItem = this.dequeue();
      this.enqueue(lastltem);
      return firstItem;
    } else if(this._storage.length === 1) {
      return this._storage.pop();
    } else {
      console.warn('Attempt1ng to dequeue from an  empty  queue');
    }
  }
}

생성자에서는 단일 배열만 생성합니다. 이것은 우리의 스택이 될 것입니다.
enqueue() 함수는 받은 항목을 저장소로 전달합니다.

dequeue() 작동 방식

이 재귀 방법은 재미있는 부분입니다. 기본 사례에 대해 논의하는 것으로 시작하겠습니다. 16행부터는 대기열이 비어 있으면 경고를 인쇄하고 아무 작업도 수행하지 않음을 나타냅니다. 하나의 항목이 있으면 팝하고 반환하십시오.

저장소에 둘 이상의 항목이 있는 경우 11-15행을 볼 수 있습니다.

스토리지 스택의 값이 순서대로 1, 2, 3이라고 가정합니다.

첫 통화에서

12행에 도달하면 lastItem은 3이고 대기열에는 3이 있습니다.
제거됨:
[1, 2]

더 많은 항목이 있다는 것을 알고 있으므로(저장소에 여러 항목이 있는 경우이므로) dequeue() 메서드를 재귀적으로 호출합니다.

두 번째 부름에 들어가기

기능을 다시 입력합니다. 길이는 이제 2이므로 동일한 케이스인 11 - 15행을 입력합니다. 다시 큐에서 제거합니다. 이 호출에서 lastItem은 2와 같습니다. 대기열은 또 다른 값을 잃습니다.
[1]

다시 함수를 호출합니다.

세 번째 부름에 들어가기

이번에는 1개 항목만 있습니다. 우리는 그것을 팝 오프하고 반환하고 두 번째 호출에서 다시 끝납니다. 대기열이 비어 있습니다.
[]

두 번째 통화로 돌아가기

이제 14번째 줄에 있는 두 번째 호출로 돌아갑니다. lastItem은 2이고 firstItem은 1입니다.

14행에서 lastItem 또는 2를 대기열에 넣습니다.
[2]

1을 반환하고 첫 번째 호출로 돌아갑니다.

첫 번째 통화로 돌아가기

처음으로 돌아왔습니다. 1astItem은 3이고 firstItem은 1입니다. 3을 대기열에 넣습니다.
[2, 3]

1을 반환합니다.

대기열에서 빼기 시간

dequeue()의 시간 복잡도는 다음과 같습니다.

에)

하나를 제외한 모든 항목을 팝하고 다시 삽입해야 하기 때문입니다.

대기열에서 빼기 공간

dequeue()의 공간 복잡도는 다음과 같습니다.

0(엔)

함수를 호출해야 하기 때문에

모든 항목에 대해 한 번 더.