두 개의 Stack으로 하나의 Queue를 구현하라.

알고리즘 매니아(?) 사이에서는 유명한 문제라고 한다. 물론 나는 스터디에서 처음 봤지만.

문제는 간단하다. LIFO의 특성을 갖는 스택 두 개로 FIFO의 특성을 구현하면 된다.

푸는데 약 3~5분정도 걸렸던 것 같다. 머릿속에서만 계산하니까 처음에 계속 헷갈리다가 손에 펜과 노트를 쥐는 순간 풀었다.

답을 그림으로 나타내면 다음과 같다.

각 스택의 명칭을 임의로 Stack for EnQueue, Stack for DeQueue로 지었다. (편하게 인큐스택, 디큐스택으로 부르겠다.)

상황 A. 데이터를 EnQueue 할 때.

1. 디큐스택이 비어있는지 확인한다.

2. 디큐스택이 비어있지 않다면 디큐스택에 있는 모든 데이터를 pop해서 인큐스택에 push한다.

3. EnQueue할 데이터를 인큐스택에 하나씩 push한다.

상황 B. 데이터를 DeQueue할 때.

1. 인큐스택이 비어있는지 확인한다.

2. 인큐스택이 비어있지 않다면 인큐스택의 Bottom에 있는 데이터를 제외한 모든 데이터를 pop해서 디큐스택에 push한다.

3. 인큐스택에 남아있는 하나의 데이터를 리턴한다.

코드로는 작성하지 않겠다. 주의할 점은 사용자가 EnQueue기능이나 DeQueue기능을 끝마쳤을 때 두 스택 모두에 데이터가 있으면 안된다. 반드시 둘 중 하나의 스택에만 데이터가 있거나, 모두 비어있어야만 한다.