[Algorithm][1] 두 개의 큐로 스택 표현(Implement stack using two queues)

github : https://github.com/taewookimmr/Algorithm-C

현재 관심 있는 회사의 면접 후기들을 읽어보다가 

면접 때 나왔던 재미있는 문제들이 보여서 직접 구현해보고자 한다.

문제 : 두 개의 큐를 이용해서 하나의 스택을 표현하시오

제약 조건 : 큐의 index 역할을 하는 front와 rear, 동작 함수인 put(int k), get()를 제외하고는 어떤 변수, 함수도 사용할 수 없다. (단, 임시 변수는 사용할 수 있다.)

문제를 처음 딱 봤을 때, 솔직히, 답이 바로 떠오르지 않았다.

잠시 딴 생각하다가 생각난 아이디어는 다음과 같다. (어떻게든 last-in이 first-out이 되도록 하면 된다!)

0) stack이라는 객체를 만드는데 맴버로 queue 두 개를 정의한다. mainQ, tempQ라고 이름 붙인다.

1) push는 mainQ에 put하는 것으로 한다. 

2-1) pop 준비 : mainQ에 하나(last-in)가 남을 때까지, mainQ에서 get()하고 그것을 바로 tempQ에 put()한다. 

2-2) mainQ에 하나 남아있는 green(last-in)을 get()하고 이것을 result라는 변수에 잠시 저장해 둔다.

2-3) tempQ에 있는 요소들을 mainQ로 다 옮기고 result를 return한다. pop 완료

위와 같은 방식으로 stack의 pop 동작을 구현하였다.

자 그러면 현재의 틀에서 성능을 올릴 수 있는 방법을 생각해보자.

1) 2-3 단계에서 tempQ에 있는 것을 mainQ에 다시 전송하는 것은 시간 낭비이다. 

--> 그냥 mainQ와 tempQ를 swap하면 된다. 즉, 역할 변경!. 그래픽스에서 더블 버퍼링 공부한 게 생각난다.

2) 배열로 구현한 경우, 실질적으로 push할 수 있는 공간은 한 mainQ의 공간 밖에 안된다. 즉 tempQ의 공간이 놀고 있다. 

--> 다른 틀에서 생각해봐야 한다.

더 좋은 아이디어가 있다면 추가적인 글을 작성해보겠다

github : https://github.com/taewookimmr/Algorithm-C