감공사

Q. 2개의 스택(Stack)으로 큐(Queue)를 만들어라.
(어떠한 array도 만들어서는 안 되며, Stack의 push(), pop(), peek() method만 이용하여 작성해야한다)

🎈 먼저, Stack의 특징인 LIFO(Last In First Out)와 Queue의 특징인 FIFO(First In First Out)를 생각해야 한다.

큐의 add()를 구성하고 싶다면, 위의 그림처럼 그냥 1번 스택에 값을 넣어주면 된다. 이건 생각하는 것에 문제가 없다.
(편의상 앞으로 a스택, b스택이라고 이름을 정하고 얘기하겠다)
하지만, remove()와 peek()을 구성할 때 순서에 문제가 생긴다.

remove()를 구성하기 전에, peek()을 먼저 생각해보자.
a스택에서 마지막에 들어간 값을(this.data[this.data.length -1]) return 해버리면 LIFO 순서로 값이 나와버린다. 
따라서, 큐의 peek()를 구성할 때 LIFO를 FIFO로 바꿔줘야 한다.
그러기 위해서 a스택의 값을 pop()하여 b스택에 push()한다고 상상해보자. 위의 그림처럼 값이 옮겨질 것이다.
이렇게 값을 옮긴 후 b스택의 마지막 값을 가져오면 Queue의 peek()과 동일한 결과를 얻어낼 수 있다.

peek()과 구성은 같으며, 값이 제거되느냐, 아니냐의 문제다.
이렇게 값을 옮긴 후 b스택의 마지막 값을 pop()해주면 Queue의 remove()와 동일한 결과를 얻어낼 수 있다.

단, peek()과 remove()에서 모두 b스택으로 옮긴 값은 원하는 처리 후 다시 a스택으로 옮겨줘야한다.

🔮 생성자(constructor)에 2개의 스택(Stack)을 생성해준다.
(단, Stack class를 가져오거나 따로 작성해둬야 한다)

add()에서는 a스택에 값을 push()한다.

remove()에서는 a스택 값을 b스택으로 옮긴 후 제거한 후, 다시 b스택 값을 a스택으로 옮겨준다.

peek()에서는 remove()와 마찬가지로 스택간 값을 옮겨주고 마지막 값을 가져온 후, 다시 값을 옮겨주면 된다.

큐와 스택 자료구조의 특성을 이해하기 좋은 예제다.

Full Code

스택의 정의(Definition of Stack)

🎈 위 그림에서 볼 수 있듯, Stack의 실행순서는 LIFO로 진행된다.
LIFO란 Last In First Out의 약자로서, 마지막으로 들어간 값이 가장 먼저 나올 수 있다. 프링글스 과자를 생각하면 쉽다.

Stack은 기본적으로 추가( push() ), 삭제( pop() ) 기능을 사용하여 다루며,
마지막 값 보기( peek() ) 기능처럼 본인이 필요한 기능을 만들어 사용하면 된다.

JavaScript의 class를 이용하여 Stack을 만들어 보겠다.

😐 위에서 볼 수 있듯, Stack의 전체 뼈대는 생성자(constructor)를 이용하여 array를 선언해준다.

add()에서는 Array.prototype.push()를 그대로 이용하여, 값이 항상 Stack의 뒤쪽으로 들어가게 구성해준다.

pop()에서도 Array.prototype.pop()를 그대로 이용하여, 항상 (나중에 들어간)마지막 값이 나올 수 있게 구성한다.

peek()에서는 index에 [this.data.length-1]을 넣어줘서 값이 있다면 마지막 값을, 없다면 undefined를 return하게 해준다.

🎉이렇게 class를 작성해주면, LIFO(Last In First Out)기능을 하는 기본 Stack을 만들어낼 수 있다.

다음 글에서는 2개의 스택(Stack)을 사용하여 하나의 큐(Queue)처럼 사용하는 큐(Queue)를 만들어보겠다.

Full Code