스택(Stack)2개로 큐(Queue) 구현하기

구현하기 전에 각각의 특성을 알아야 한다.

Stack -> 한번 들어간 요소들은 나올때 순서가 반대로 되어 나온다. (reverse)
Queue -> 한번 들어간 요소들은 나올때 들어간 순서 그대로 나온다.

먼저 내가 생각한 것은 스택은 반대로 나오니까 반대로 나온것을 또 스택에 넣어서 다시 반대로 하면 되나? 라는 생각을 했다.

그림으로 쉽게 표현해보자.

그림 처럼 여러가지 맛의 초코볼을 통안에 넣는다고 가정해보자. 그리고 그 순서를 보기좋게 기록해 놨다.

들어간 순서는 그림과 같이 1 -> 2-> 3 이렇게 된다.

그리고 pop을 이용해서 빼낸다면 이런 순서대로 나올 것이다. (reverse)

이제 이것들을 다시 스택에 push해서 넣으면 3-> 2-> 1 순서로 스택에 차곡히 쌓일 것이다. 그리고 다시 pop으로 빼낸다면?

1 -> 2 -> 3 순서대로 큐(Queue)처럼 나올 것이다.

정말 쉬운 생각이다! 이것으로 스택 두개로 큐를 구현해 봤다..... 곤 하지만 과연 이렇게 쉬울까?

만약 위 그림 과정처럼 빼낸 것들을 다시 넣었을때 초코볼을 (4번이라고 적힌) 추가한다면

4 -> 1 -> 2 -> 3

이런 순서가 될 탠데 우리가 의도한 바가 아니게 된다. 그러면 어떻게 해야할까?

결론부터 말하면 하나의 스택은 데이터를 넣는것, 다른 하나는 데이터를 빼는 용도로만 이용하면 된다.

무슨 말이지? 그림을 통해서 설명 들어가겠다.

만약 4, 5, 6번 ... 등등 더 추가로 초코볼(데이터)를 넣고 순서대로 출력하고자 한다면 이렇게 하면 된다.

왼쪽이 Stack 1 오른쪽이 Stack2 라고 가정하고 한 스택은 데이터를 넣기만 하고 다른 한쪽은 데이터를 빼내기만 하면 된다.

이때 오른쪽 스택(Stack2)이 비었을 경우에는 왼쪽 스택(Stack1)에서 오른쪽 스택에게 데이터를 추가하면 된다. 그렇게 되면 순서대로 데이터를 빼낼 수 있다.

결과적으로 1 -> 2-> 3-> (스택2가 비어있을 경우 스택1에서 스택2에 데이터 넣기) -> 4 -> 5 -> 6 으로 순서대로 뽑을 수 있다. 마치 큐(Queue)처럼.

---

결론.

1. Stack1에는 데이터를 넣기만 하고 Stack2에는 데이터를 빼내는 용도로만 쓰자.
2. 조건은 Stack2가 비어있을 경우 Stack1에 들어있는 데이터를 Stack2에 넣자.

3. 그냥 Queue 쓰자.

---

참고한 곳!