Stack 2개로 Queue, Queue 2개로 Stack 만들기

Stack 2개로 Queue를, Queue 2개로 Stack을 만드는 방법과, 그 시간복잡도에 대해 알아보겠다. 

 

1. Stack 2개로 Queue 만들기 

아이데이션

inStack과 outStack이 있다. inStack의 입구가 Qin이 되고, outStack의 출구가 Qout이 된다. 

enqueue 호출 시 

1, 2, 3번 공이 순서대로 Stack1에 입력된다. 위에서부터 [3, 2, 1]

 

dequeue 호출 시 

outStack이 비어있으면, inStack의 모든 항목을 outStack으로 이동. inStack에서 하나씩 pop해서 outStack에 push한다. 완료되면 outStack은 위에서부터 [1, 2, 3]이 되고, dequeue 호출 시 가장 위에 있는 1부터 제거된다. (그 후의 dequeue는 outStack이 빌 때까지 계속 pop)

 

구현

class Stack {
    constructor() {
      this.arr = [];
    }
    push(item) {
      this.arr.push(item);
    }
    pop() {
      if (this.isEmpty()) {
        return null;
      }
      return this.arr.pop();
    }
    isEmpty() {
      return this.arr.length === 0;
    }
}

class QueueUsingTwoStacks {
    constructor() {
      this.inStack = new Stack();
      this.outStack = new Stack();
    }
    enqueue(item) {
      this.inStack.push(item);
    }
    dequeue(item) {
      if (this.outStack.isEmpty()) {
        while (!this.inStack.isEmpty()) {
          this.outStack.push(this.inStack.pop());
        }
      }
      return this.outStack.pop();
    }
}

const queue = new QueueUsingTwoStacks();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue()); // 1
console.log(queue.dequeue()); // 2
queue.enqueue(4);
console.log(queue.dequeue()); // 3
console.log(queue.dequeue()); // 4

시간복잡도

enqueue는 inStack에 item을 추가하는 것이기 때문에 O(1)이다. 

dequeue는 outStack이 비어있지 않을 경우, 그냥 pop하면 되기 때문에 O(1)이지만, outStack이 비어있을 경우 inStack에 있는 n개의 요소를 outStack으로 옮겨야 하므로 O(n) 시간 복잡도를 가진다. 

즉, inStack에 5개의 요소가 있고, dequeue를 5번 한다면, O(n) -> O(1) -> O(1) -> O(1) -> O(1) 이므로, 분할 상환 방식으로 계산하면 평균적인 시간복잡도는 O(1)에 가깝다. 

---

2. Queue 2개로 Stack 만들기

아이데이션

하나는 mainQueue, 하나는 tempQueue이다. 1, 2, 3, 4가 순서대로 mainQueue에 들어갔을 때, 4 먼저 나와야 하므로, 4를 제외한 나머지를 tempQueue에 옮긴 후 4를 제거한다. 그 후 temp에 있는 모든 요소를 main에 옮긴다. 

구현

   class Queue {
    constructor() {
      this.arr = [];
    }
    enqueue(item) {
      this.arr.push(item);
    }
    dequeue() {
      if (this.isEmpty()) {
        return null;
      }
      return this.arr.shift();
    }
    isEmpty() {
      return this.arr.length === 0;
    }
  }

  class StackUsingTwoQueues {
    constructor() {
      this.mainQueue = new Queue();
      this.tempQueue = new Queue();
    }
    push(item) {
      this.mainQueue.enqueue(item);
    }
    pop() {
      if (this.mainQueue.isEmpty()) return null;
      while (this.mainQueue.arr.length > 1) {
        this.tempQueue.enqueue(this.mainQueue.dequeue());
      }
      const result = this.mainQueue.dequeue();
      [this.mainQueue, this.tempQueue] = [this.tempQueue, this.mainQueue];
      return result;
    }
  }

  const stack = new StackUsingTwoQueues();
  stack.push(1);
  stack.push(2);
  stack.push(3);
  console.log(stack.pop()); // 3
  console.log(stack.pop()); // 2
  console.log(stack.pop()); // 1

시간복잡도

push할 때는 mainQueue에 하나씩 요소를 넣는 작업이므로 O(1)

pop할 때는 n개의 요소를 tempQueue로 옮기는 작업이 필요하므로 O(n)

 

 

 

---

예외 제보 환영 ^^7