감공사

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

Q. 값을 다르게 가지고 있는 2개의 큐(Queue)를 1개의 큐(Queue)로 만드는 weave 함수(function)을 만들어라.
(단, 값을 번갈아 넣어야하며, undefined는 없어야 한다.
또한, 어떠한 array도 만들어서는 안 되며, Queue의 add, remove, peek method만 이용하여 작성해야한다)

🎈 먼저, 값이 많이 있기 때문에 반복 작업이 필요하다. 그러니 '반복문'을 먼저 떠올려야할 것이다.
그리고 undefined가 들어가면 안 되니, 값이 있는지를 확인하는 '조건문'이 있어야한다.

값이 있는지 확인하는 peek()을 반복문의 조건으로 넣을 수 있을 것이다. 값이 있다면 '반복'해야하니까.
그리고 또한 한쪽의 값이 먼저 다 소진될 수 있으니, 반복문 안에서도 값이 있는지 또 확인하는 조건문도 필요하다.

조건이 맞는다면 해당 큐에서 값을 제거한다. remove()
그리고 새로운 큐에 값을 넣어준다. add()

위처럼 간단하게 생각하고 시작하면 된다.

🔮 가장 먼저, 새로운 큐를 만들어줘야한다. const q = new Queue();
반복문의 조건은 while( srcOne.peek() || srcTwo.peek() )을 넣어 둘 중 하나의 큐에 값이 있다면 반복한다.
조건문은 if ( srcOne.peek() ) 와 if ( srcTwo.peek() )을 넣어줘서, 둘 중 하나의 큐라도 값이 있다면 실행시킨다.
if의 내부에서는 q.add( srcOne.remove() )를 통해 기존 값을 새로운 큐(q)에 넣어준다.

이렇게 반복해주면 번갈아 값을 넣는 weave algorithm이 완성된다.

Full Code

큐의 정의(Definition of Queue)

🎈 위 그림에서 볼 수 있듯, Queue의 실행 순서는 FIFO로 진행된다.
FIFO란 First In First Out의 약자로서, 처음 들어간 값이 가장 먼저 나올 수 있다. 선입선출이라고 생각하면 쉽다.

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

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

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

add()에서는 Array.prototype.unshift()를 이용하여, 값이 항상 Queue의 앞으로 들어가게 구성해준다.

remove()에서는 Array.prototype.pop()를 이용하여, 항상 (먼저 들어간)마지막 값이 나올 수 있게 구성한다.

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

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

다음 글에서는 값이 다른 2개의 큐(Queue)를 1개의 큐(Queue)로 만들어보는 자료구조를 이용한 알고리즘에 대해 작성해보겠다.

Full Code