두 개의 스택을 이용한 큐 구현

한번 나에게 그런 문제가 주어진 적이 있었다.
스택(Stack)을 이용하여 큐(Queue)를 구현하라.

힌트는 두 개의 스택을 이용하라.
그런데 도무지 그날따라 머리속에 로직이 떠오르지가 않는 것이었다. 로직, 알고리즘이 떠오르지 않는 날은 최선책이 잘 떠오르지 않을 때가 있다. 그래서 나는 내가 문제를 푸는 과정이 조금 미숙할 때가 있지 않은가 싶다. 체계적으로 문제의 해법에 대해 접근해가야 하는데 그렇지 못한 점이 있는 것이다.

오늘 문득 그 문제를 생각하다보니 참 간단하다. 

* 두 개의 스택을 이용한 구현
중요한 점은 쌓아진 스택을 그대로 빼서 다시 스택에 쌓으면 큐의 형태로 빼낼 수 있게 됀다.
즉, 첫 번째 스택은 push()만을 담당하고, 두 번째 스택은 pop()만을 담당한다.

- 첫 번째 스택에서 두 번째 스택으로 옮기는 것은 두 번째 스택이 비어있을 경우만 한다.
   (pop()을 할 때마다 한다면 순서가 엉망이 됀다.)
- 한번 옮기고 나면 두 번째 스택이 비기 전까지 첫 번째 스택에서 옮겨오지 않는다.
- size()는 두 개의 스택에 쌓인 수를 합친다.

---

import java.util.Stack;

public class AtinQueue {

Stack<Integer> stack1 = new Stack<Integer>();

Stack<Integer> stack2 = new Stack<Integer>();

public int pop(){

if(stack2.size() == 0){

while(stack1.size() > 0){

stack2.push(stack1.pop());

}

}

return stack2.pop(); 

}

public void push(int item){

stack1.push(item);

}

public int size(){

return stack1.size() + stack2.size();

}

public static void main(String[] args) {

AtinQueue queue = new AtinQueue();

queue.push(1);

queue.push(2);

System.out.println(queue.pop());

queue.push(3);

queue.push(4);

System.out.println(queue.pop());

queue.push(5);

queue.push(6);

queue.push(7);

System.out.println(queue.pop());

queue.push(8);

queue.push(9);

while(queue.size() > 0){

System.out.println(queue.pop());

}

}

}

---

[Source 1] AtinQueue.java