스택으로 큐 만들기(Create Queue with Stacks)

References

아래 링크의 강의 중 Section 20. Two Become One의 내용을 추려 이번 글을 작성하였습니다.
The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy

Solution

const Stack = require("./stack");

class Queue {
  // whenever you create an instance of a queue, you will automatically generate two stacks and assign it to this queue class.
  constructor() {
    this.first = new Stack();
    this.second = new Stack();
  }

  add(record) {
    this.first.push(record);
  }

  remove() {
    while (this.first.peek()) {
      this.second.push(this.first.pop());
    }

    const record = this.second.pop();

    while (this.second.peek()) {
      this.first.push(this.second.pop());
    }

    return record;
  }

  peek() {
    while (this.first.peek()) {
      this.second.push(this.first.pop());
    }

    const record = this.second.peek();

    while (this.second.peek()) {
      this.first.push(this.second.pop());
    }

    return record;
  }
}

module.exports = Queue;

기본적인 작동원리는 위 그림과 같다. 선입선출(FIFO)의 원리를 stack에도 적용한다 보면 된다.

함께 보기

큐
큐 합치기
스택