[인터뷰 후기] Stack 2개로 Queue 구현하기

출처 : http://brogram.egloos.com/626078

[ 최소한의 스택을 이용하여 큐를 구현하기 ]

스택 2개를 사용하여 큐를 구현한다.

하나의 스택은 push 를 담당하고, 다른 하나의 스택은 pop 을 담당한다.

stack1 의 item 을 pop하여 stack2 에 담고, stack2 의 item 을 pop 하면 큐를 구현할 수 있다.

[ 소스 코드 ]

package stack.queue; import java.util.Stack; public class Queue { //stack 2개 사용 Stack<Integer> stack1=new Stack<Integer>(); Stack<Integer> stack2=new Stack<Integer>(); /** * methodname : push * comment : stack1 에 매개변수로 들어온 item 을 push 한다. * @param item */ public void push(int item){ stack1.push(item); } /** * methodname : pop * comment : stack2 에서 item 을 pop하여 반환한다. * stack2 가 비어있다면, stack1 item을 pop하여 stack2에 item을 push한다. * @return */ public int pop(){ if(stack2.size()==0){//stack2 가 비어있을 경우 while(stack1.size()>0){//stack1 이 비어있지 않을 경우 stack2.push(stack1.pop()); }//while }//if return stack2.pop(); } /** * methodname : size * comment : stack1 과 stack2 사이즈 합한 값을 반환한다. * @return */ public int size(){ return stack1.size()+stack2.size(); } public static void main(String[] args) { Queue q=new Queue(); q.push(1); q.push(2); q.push(3); q.push(4); System.out.println("***1,2,3,4 push***"); System.out.println("pop : "+q.pop()); System.out.println("size : "+q.size()); q.push(5); q.push(6); System.out.println("***5,6 push***"); System.out.println("pop : "+q.pop()); System.out.println("size : "+q.size()); q.push(7); q.push(8); System.out.println("***7,8 push***"); for(int i=0;i<3;i++){ System.out.println("pop : "+q.pop()); } q.push(9); q.push(10); System.out.println("***9,10 push***"); System.out.println("pop : "+q.pop()); System.out.println("size : "+q.size()); while(q.size()!=0){ System.out.println("pop : "+q.pop()); } }//main }

 - stack1은 push만 담당한다.

- stack2는 pop을 하는데, 자신이 비어있다면 우선 stack1에 있는 것을 모두 가져온 뒤 pop해야한다. 

사실 어려운건 아니지만, 모르는 상태에서 손코딩 면접 볼 때 조금 당황했다. stack2개로 하면 될 것 같다는 생각은 했는데

stack2에서 꺼내는 조건이 제한시간동안 머리속에서 하려니 쉽지 않았다. 

자료구조나 알고리즘을 생각할 때 항상

boundary를 잘 고려해야한다.  empty()나 full() 일 때 즉 , max와 min, 0과 size() 일 때 어떻게 되는지 잘 생각해야한다.