제약사항

큐 자료구조에서 사용하는 메서드들과 동일하게 작동하도록 구현해야한다.

---

코드없이 구현해보기

---

삽입(insert) 메서드 구현하기

queue : [ ]
stack : [ ]
만약 1,2,3,4,5 를 꽂는다고 가정해보자.
insert메서드의 경우 동일한 큐와 스택 모두 순서로 삽입할 수 있다.

queue: 1->2->3->4->5
stack: 1->2->3->4->5

---

빼기(pop) 메서드 구현하기

pop메서드의 경우 큐와 스택에서의 각각 빼기 순서를 보자

queue: [1,2,3,4,5] 선입선출 1-2-3-4-5
stack : [1,2,3,4,5] 후입선출 5-4-3-2-1
순서가 정반대이다. 때문에 큐에서 pop한 순서와 동일한 [1,2,3,4,5] 순서로 값을 추출하기 위해서는 현재 stack을 reverse(뒤집은) stack이 필요하다.

stack2를 만들어서 원본 스택에 있는 값들을 차례로 pop -> insert 한다.

즉, 큐를 스택으로 구현하기 위해서는 최소 두 개의 스택이 필요하다.

---

stack2에 옮겨진 상황(reverse)

queue : [1,2,3,4,5]
stack1 : []
stack2 : [5,4,3,2,1]

---

새로운(6,7)값을 삽입 해야 한다면?

큐나 스택에서나 삽입을 할 때는 순서가 동일하다.
queue : [1,2,3,4,5,6,7]
stack2 : [5,4,3,6,7]

---

이 상태에서 필요한 값이 있어 pop한다면?

하지만 만약 stack2에서 값 3,4,5의 차례로 필요해서 pop하게 된다면 값 7,6을 먼저 얻게 된다.

그렇다면 6,7을 stack1에 삽입한다면 어떨까?

stack1: [6,7]
stack2: [5,4,3]

이 경우에는 3-4-5의 순서를 지키며 stack2에서 pop된다

그리고 이러한 값들이 남게 될 것이다

stack1: [6,7]
stack2: []

하지만 여기에서 또 stack1에서 값들이 필요할 때 queue에서 pop하는 순서와는 반대로 값 7-6의 순서로 얻게 된다.

---

reverse

때문에 공스택인 stack2를 이용해야한다. 먼저 stack1에서 7을 pop한 후 stack2에 insert한다. 6도 동일하게 과정을 거친다.

stack2: [7,6] 이제 다시 stack2에서 6-7의 순서로 필요한 값을 추출한다.

코드로 구현하기

class QueueWithStacks {
  constructor() {
    this.in = [];	// push 하는데 이용할 stack1
    this.out = [];	// pop하는데 이용할 stack2
  }

  enqueue(val) {	// 데이터 삽입 O(1)
    this.in.push(val);
  }

  dequeue() {		// 데이터 빼기 O(n)
    if (this.out.length === 0) {	// stack2가 공스택인지 확인
      while(this.in.length > 0) {	// stack1가 공스택이 될 때 까지(0에 닿으면 멈춘다)
        this.out.push(this.in.pop()); // reversed stack만들기 pop -> push
      }
    }
    
    return this.out.pop();	// 필요한 값을 순서대로 추출
  }

  peek() {	// dequeue와 로직은 같지만 stack2에서 값을 제거하지는 않는다(훔쳐보기)   O(n)
    if (this.out.length === 0) {
        while(this.in.length > 0) {
            this.out.push(this.in.pop());
        }
    }
    
    return this.out[this.out.length - 1]; // pop된 값을 리턴하지 않고 마지막 값의 참조값을 리턴
  }

  empty() {		// 큐공 스택인지 체크하는 로직 O(1)
    return this.in.length === 0 && this.out.length === 0;		// stack 둘 다 모두 공스택일 때 true 리턴
  }
};

정리

• insert할 때는 큐나 스택의 순서가 동일한다
• pop할 때는 정반대이기 때문에 공스택 stack2를 stack1을 pop-insert 하여 reverse하는 데에 이용한다
• 큐선선(큐는 선입선출!) 스후선(스택은 후입선출)