[자료구조] Stack 2개로 Queue 구현하기

오늘은 Stack 2개로 Queue를 구현해보자.
(어디서 면접 질문으로 나왔다는걸 본거 같음...)

idea

어떻게 구현할지 생각하기 전에 아이디어를 정리하고 가자.

우리는 Stack과 Queue 포스팅에서 각각의 특징을 봤다.

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

위의 특징에 따르면 우리는 순서가 reverse되는 자료구조를 이용해서 순서대로 나오는 자료구조를 구현하면 된다.

Stack 2개 이용하기

우리는 1, 2, 3이라고 쓰여있는 공을 순서대로 넣고 순서대로 빼고 싶다.

• 우리가 1, 2, 3 공을 Stack1에 넣는다면 위의 그림과 같은 상태일 것이다.

• Stack1에 넣은 공들을 모두 pop한 후 순서대로 줄지어보면 3, 2, 1로 빠져나올 것이다.
• 즉, reverse되어 나온다.

Stack1을 거쳐 나온 공들을 Stack2에 다시 넣는다면 어떻게 될까?

• 위의 그림처럼 아래에서부터 3 -> 2 -> 1 순서로 공이 쌓이게 된다.

그렇다면 Stack2의 공들을 pop하게 되면 어떤 순서로 공들이 나올까?

• Stack2의 공들을 pop하게 되면 1 -> 2 -> 3 순서대로 공들이 나오게 된다.
• 즉, 우리가 처음에 넣었던 공들의 순서대로 나오게된다.

그럼 이게 끝이야?!

(물론 이렇게 간단했다면 포스팅 안 했겠지...)
이런 경우에는 어떻게 할까?

2개의 Stack은 위와 같은 상태이고 우리는 4번 공을 넣고 싶다.
4번 공은 어떤 Stack에 넣으면 좋을까?

1. Stack2에 4번 공을 넣는다면 어떻게 될까?

• Stack들의 상태가 위의 그림과 같이 될 것이다.
• 즉, 우리가 공을 pop할때 4 -> 1 -> 2 -> 3과 같은 순서로 나온다.
• 하지만 이건 우리가 원하는 순서가 아니다.

2. Stack1에 4번 공을 넣는다면 어떻게 될까?

• Stack들의 상태가 위의 그림과 같이 될 것이다.
• 위와 같은 상태에서 어찌저찌 해보면 될 것 같지 않나?!ㅋㅋㅋ(나만 그런가..)

우리는 2번 Stack1에 4번 공을 넣는 것을 가지고 생각을 해볼 것이다.

Stack2가 비어있지 않을때 어떻게 순서대로 공들을 pop할 수 있을까?

우리는 Stack1은 data를 넣는 용도로만 쓰고, Stack2는 data를 빼는 용도로만 써보자.

이상태에서 어떻게 1 -> 2 -> 3 -> 4 -> 5 순서로 공을 빼보자!

• Stack2에서 pop하면 우리는 1 -> 2 -> 3까지는 얻을 수 있다.

이제 4 -> 5를 어떻게 얻을 수 있을까?

• Stack2를 data를 빼는 용도로 쓰기로 했으니 그렇게 써보자.
• Stack1에 있는 4, 5 공을 Stack2로 옮겨서 pop하면 우리가 원하는 순서로 공을 빼낼 수 있다.

다음과 같은 조건으로 정리할 수 있다.

• Stack1로는 data를 입력 받는다.
• Stack2로는 data를 pop한다.
• Stack2가 비어 있다면 Stack1에서 Stack2로 data를 옮긴다.

코드

마무리

오늘은 Stack 2개로 Queue를 구현하는 법을 알아봤다.
가끔 인터뷰에 나오는 문제이고 한 번 이해하면 쉬우므로 한 번 다뤄봤다.
그럼 이만👋